Re: Decimal encryption
I wrote: Looking a little more closely, I found this paper by Patarin from Crypto 2005 which describes security bounds for higher round Feistel constructions: http://www.springerlink.com/content/gtcabev3ucv8apdu/ I was wrong, this was from Crypto 03. And as Eric Rescorla has already pointed out, Patarin had an improved the result the following year where he showed that 6 rounds was sufficient for security. Greg Rose wrote: So, you don't have a 133-bit block cipher lying around? No worries, I'll sell you one ;-). Actually that is easy too. Take a trustworthy 128-bit block cipher like AES. To encrypt, do: 1. Encrypt the first 128 bits (ECB mode) 2. Encrypt the last 128 bits (also ECB mode). Hal Finney wrote: I am not familiar with the security proof here, do you have a reference? Or is it an exercise for the student? It's a degenerate case of Rivest's All-or-nothing transform (which applies to larger, multi-block blocks, if you know what I mean :-) ). I believe he gave a security proof, some 6ish years ago. But I could be confabulating. Hmmm, looking at Rivest's package transform which was his original proposal for an AONT, that seems to be different and actually expanded the message size. I haven't been able to find an AONT which is quite like this. One limitation with this proposal is that it appears that it will only be as strong as the size of the overlapping region. However in this case the overlap is 128-5 or 123 bits, so the birthday bound will be about 2^62 rather than the ideal 2^64, and that is hardly noticeable. So it does seem like it could be a good choice here. Doing a little over 3 AES encryptions will be much better than the 6 which seem to be necessary for the Feistel approach. However such a substantial improvement certainly makes a proof of security more interesting. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Decimal encryption
- Jonathan Katz [EMAIL PROTECTED] wrote: But he probably wants an encryption scheme, not a cipher. Jon, I'm not sure I understand what you mean. If I am reading his message correctly, the original poster seems to be asking for a format-preserving encryption over a domain with 10^40 elements. Format-preserving, it seems to me, implies [a family of keyed] functions that are one-to-one and deterministic. In other words, the best security we can hope for is a PRP on that domain, and this is what B-R gives, starting from a PRP over a somewhat larger domain. In this setting, what is the difference between an encryption scheme and a cipher? Also, correct me if I am wrong, but Black and Rogaway's approach is not efficient for large domains. But if you use their approach for small domains then you open yourself up to dictionary attacks. I think the dependency depends on the amount by which the domain of the constructed PRP is smaller than the domain of the starting PRP. A 133-bit B-R would indeed be inefficient to construct from a 256-bit block cipher like Rijndael, and one would need a different starting point; but these could be constructed using a Feistel of appropriate size. Is the dictionary attack problem any more severe than for any other PRP over a small domain? The best one can hope for is a security guarantee for a number of queries approaching the size of the domain -- or to ensure that in practical deployment access to the encryption and decryption functionality is constrained. Yours -- Hovav. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: road toll transponder hacked
Steven M. Bellovin writes, in part: -+--- | There's a limit to how far they can go with that, because of the fear | of people abandoning the transponders. | snip | As for usage-based driving -- the first question is the political will | to do so. | snip | Finally, the transponders may not matter much longer; OCR on license | plates is getting that good. | I don't think whether it is a transponder or not actually matters, Steve, since, as you say, OCR of the license plates makes whether a transponder is in place totally irrelevant. As to public resistance -- look at the revenue coming in to, say, Chicago from the red-light cameras and tell me that this won't spread. Similarly, per-mile road-use pricing will be all about revenue enhancement but it will be painted DHS-faireness-green (So as to fairly fund the maintainance of this State's critical infrastructure, this Act converts the funding mechanisms over to a fairer road-use policy but, at the same time, it leaves in place the State gasoline tax, thereby penalizing the people who continue to drive gas guzzlers). Which leads back to the recording of travel and the handling of those recordings. When New Jersey signed up with EZ-Pass it required the company involved to retain toll records for ten years (as an aid to law enforcement). Since that is the same company in lots of states even if it is called something else (like FastLane in Massachusetts), the rational thing for the company to do is to just keep everything forever. With disk prices falling as they are, keeping everything is cheaper than careful selective deletion, that's for sure. --dan - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: road toll transponder hacked
The relationship to this list may then be thin excepting that the collection and handling of such data remains of substantial interest. Actually, it points to cash settlement of road tolls. That's not unknown. On the Niagara Falls toll bridges, they have an ETC system where you buy your transponder for cash at a toll booth and refill it with cash. I suppose they could take your picture and link it to your license plate, but they can do that if you throw quarters into the bin, too. R's, John - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Decimal encryption
Eric Rescorla [EMAIL PROTECTED] writes: There are a set of techniques that allow you to encrypt elements of arbitrary sets back onto that set. ... and most of them seem to be excessively complicated for what they end up achieving. Just for reference the mechanism from the sci.crypt thread of more than a decade ago was: KSG_RANGE = ( 256 / RANGE ) * RANGE; do val = ksg(); while( val = KSG_RANGE ); The worst-case scenario is when RANGE = 129, when nearly 50% of the ksg() output will be discarded. A more typical case when RANGE = 96 (ASCII text) loses 25% of the output, and RANGE = 10 (digits) loses 2% of the output. The full process then becomes: encrypt: do val = ksg(); while( val = KSG_RANGE ); cipher = ( ( ( plain - BASE ) + val ) % RANGE ) + BASE; decrypt: do val = ksg(); while( val = KSG_RANGE ); plain = ( ( ( cipher - BASE ) - val ) % RANGE ); while( plain 0 ) plain += RANGE; plain += BASE; This takes any cipher (block or stream) and, by using it as a KSG, allows encryption of arbitrary (including discontinuous) data ranges. Another advantage of the KSG use is that you can precalculate the key stream offline, the implementation I used at the time pre-generated 4K of keystream and then used it to encrypt bursty text messages with real-time constraints that didn't allow for pauses to run the cipher. (The thread contains lots of tweaks and variations of this). Peter. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Decimal encryption
At Thu, 28 Aug 2008 17:32:10 +1200, Peter Gutmann wrote: Eric Rescorla [EMAIL PROTECTED] writes: There are a set of techniques that allow you to encrypt elements of arbitrary sets back onto that set. ... and most of them seem to be excessively complicated for what they end up achieving. Just for reference the mechanism from the sci.crypt thread of more than a decade ago was: [Description of reduced-range stream cipher elided] Another advantage of the KSG use is that you can precalculate the key stream offline, the implementation I used at the time pre-generated 4K of keystream and then used it to encrypt bursty text messages with real-time constraints that didn't allow for pauses to run the cipher. (The thread contains lots of tweaks and variations of this). There's noting inherently wrong with this mechanism, but like all stream ciphers, it can't be used if you want to encrypt multiple independent values, e.g., credit cards in a database--without a randomizer (which implies expansion) you have the usual two-time pad problems. A B-R style block cipher can, albeit with lookup table issues. -Ekr - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: road toll transponder hacked
On 27 aug, Steven M. Bellovin wrote: Finally, the transponders may not matter much longer; OCR on license plates is getting that good. As has already been mentioned, the 407 ETR road in Toronto already relies on this to some extent; it won't be too much longer before the human assist is all but unneeded. We are already there. The London congestion charges are as far as I know completely based on OCR. The same goes for the congestion charge in Stockholm. In Stockholm they initially gave out transponders but they have stopped doing that, probably because the OCR technology is good enough. I think that the primary reason they are going for systems like that is that it is much cheaper to install and run than distributing a lot of transponders or building and staffing toll-booths. The tracking capabilities is merely an added bonus. In Göteborg they have a system with cameras which looks at license plates at different locations and through that measure how long it takes to drive certain routes. This system is still under construction but there are some information billboards where they show the current driving time to various targets. They say that they mask out the last digit of the plate and destroy the information after a short while, but who knows. /MaF -- Martin Forssen [EMAIL PROTECTED] Development Manager Phone: +46 31 7744361 AppGate Network Security AB - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: road toll transponder hacked
On Wed, Aug 27, 2008 at 12:16:23PM -0400, Steven M. Bellovin wrote: Finally, the transponders may not matter much longer; OCR on license plates is getting that good. As has already been mentioned, the 407 ETR road in Toronto already relies on this to some extent; it won't be too much longer before the human assist is all but unneeded. http://en.wikipedia.org/wiki/Toll_Collect is in operation in entire Germany. It does OCR on all license plates (also used for police purposes in realtime, despite initial vigorous denial) but currently is only used for truck toll. -- Eugen* Leitl a href=http://leitl.org;leitl/a http://leitl.org __ ICBM: 48.07100, 11.36820 http://www.ativel.com http://postbiota.org 8B29F6BE: 099D 78BA 2FD3 B014 B08A 7779 75B0 2443 8B29 F6BE - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Viruses on the International Space Station...
Apropos the recent discussion of Fake UIs and the problem of people most needing sensitivity to the dangers being most insensitive: ISS laptops found to be infected with Gammima.AG virus; apparently not the first infection on the ISS. What's worth noting about this story is that the laptops carried by astronauts into space *** DO NOT *** contain any anti-virus software. I was just following *NASA* 'best practices'... http://news.bbc.co.uk/2/hi/technology/7583805.stm http://www.spaceref.com/news/viewnews.html?id=1305 via http://science.slashdot.org/science/08/08/27/1231224.shtml -- | || ||| || ||| || ||| || ||| || ||| || ||| || ||| Charles McElwain 33 Vernon Street Somerville, MA 02145 617-628-5542 (home) 617-501-1591 (cell) [EMAIL PROTECTED] | || ||| || ||| || ||| || ||| || ||| || ||| || ||| - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: road toll transponder hacked
On Thu, 28 Aug 2008 10:49:20 +0200 Eugen Leitl [EMAIL PROTECTED] wrote: On Wed, Aug 27, 2008 at 12:16:23PM -0400, Steven M. Bellovin wrote: Finally, the transponders may not matter much longer; OCR on license plates is getting that good. As has already been mentioned, the 407 ETR road in Toronto already relies on this to some extent; it won't be too much longer before the human assist is all but unneeded. http://en.wikipedia.org/wiki/Toll_Collect is in operation in entire Germany. It does OCR on all license plates (also used for police purposes in realtime, despite initial vigorous denial) but currently is only used for truck toll. How well does that actually work? There were many articles in RISKS Digest about problems with the early deployment. And -- turning the topic back to crypto -- is there a cryptographic solution to license plates? Put another way, what are the legitimate needs of various parties, and can these be satisfied in a privacy-preserving way? (Note: I do not regard put a digital cash wallet in the transponder as a solution to the license plate problem, since it doesn't handle the problem of toll evaders, people who aren't members of the system, and many other things that license plates are used for.) --Steve Bellovin, http://www.cs.columbia.edu/~smb - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Decimal encryption
On Wed, 27 Aug 2008, Eric Rescorla wrote: At Wed, 27 Aug 2008 16:10:51 -0400 (EDT), Jonathan Katz wrote: On Wed, 27 Aug 2008, Eric Rescorla wrote: At Wed, 27 Aug 2008 17:05:44 +0200, There are a set of techniques that allow you to encrypt elements of arbitrary sets back onto that set. The original paper on this is: John Black and Phillip Rogaway. Ciphers with arbitrary ?nite domains. In CT-RSA, pages 114?130, 2002. But he probably wants an encryption scheme, not a cipher. Hmm... I'm not sure I recognize the difference between encryption scheme and cipher. Can you elaborate? A block cipher is a primitive that can be used, in particular, to construct encryption schemes. But you can construct encryption schemes without block ciphers, and you can use block ciphers to construct other things besides encryption. Moreover, good encryption should generally be randomized, while a block cipher is deterministic. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Decimal encryption
On Wed, 27 Aug 2008, Hovav Shacham wrote: - Jonathan Katz [EMAIL PROTECTED] wrote: But he probably wants an encryption scheme, not a cipher. Jon, I'm not sure I understand what you mean. If I am reading his message correctly, the original poster seems to be asking for a format-preserving encryption over a domain with 10^40 elements. Format-preserving, it seems to me, implies [a family of keyed] functions that are one-to-one and deterministic. In other words, the best security we can hope for is a PRP on that domain, and this is what B-R gives, starting from a PRP over a somewhat larger domain. In this setting, what is the difference between an encryption scheme and a cipher? Yes, I can see this might cause confusion. Just to clarify: I had emailed the original poster off-line and he told me that he was willing to use other information already being sent in the clear as a non-repeating IV. Given this, secure (and, in particular, non-deterministic) encryption is possible. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: road toll transponder hacked
Sherri Davidoff [EMAIL PROTECTED] writes: [EMAIL PROTECTED] wrote: Look for general tracking to appear everywhere. Anonymous travel is dead. Even for subway riders who still use tokens and citizens that bicycle around town, the proliferation of cameras, facial recognition technology, biometrics and RFID tagging will render anonymity obsolete within a generation. Cryptography affords an alternative. Cryptography enables untraceable persistent pseudonyms created and maintained via chains of anonymizing remailers and broadcast replies. In the nightmare scenario that you describe, untraceable nyms may be the only way that one can live as a responsible adult, rather than a subject of a nanny state. -- StealthMonger [EMAIL PROTECTED] [EMAIL PROTECTED] -- stealthmail: Scripts to hide whether you're doing email, or when, or with whom. mailto:[EMAIL PROTECTED] Finger for key. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: road toll transponder hacked
http://en.wikipedia.org/wiki/Toll_Collect is in operation in entire Germany. It does OCR on all license plates (also used for police purposes in realtime, despite initial vigorous denial) but currently is only used for truck toll. How well does that actually work? There were many articles in RISKS Digest about problems with the early deployment. That's true wrt to early deployment. Given that the Toll Collect system has been up and running since January 2005 it (technically) runs surprisingly well. They have improved tremendously and are likely to sell their technology to other european countries. Cheers, Stefan. Symposium Wirtschaftsspionage 03.09.2008 KA/Ettlingen http://www.symposium-wirtschaftsspionage.de/ - Stefan Kelm Security Consulting Secorvo Security Consulting GmbH Ettlinger Strasse 12-14, D-76137 Karlsruhe Tel. +49 721 255171-304, Fax +49 721 255171-100 [EMAIL PROTECTED], http://www.secorvo.de/ PGP: 87AE E858 CCBC C3A2 E633 D139 B0D9 212B Mannheim HRB 108319, Geschaeftsfuehrer: Dirk Fox - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: road toll transponder hacked
On Thu, 28 Aug 2008 17:55:57 +0200 Stefan Kelm [EMAIL PROTECTED] wrote: http://en.wikipedia.org/wiki/Toll_Collect is in operation in entire Germany. It does OCR on all license plates (also used for police purposes in realtime, despite initial vigorous denial) but currently is only used for truck toll. How well does that actually work? There were many articles in RISKS Digest about problems with the early deployment. That's true wrt to early deployment. Given that the Toll Collect system has been up and running since January 2005 it (technically) runs surprisingly well. They have improved tremendously and are likely to sell their technology to other european countries. I confess that from a privacy perspective, I'd prefer if it didn't work that well... Thanks. --Steve Bellovin, http://www.cs.columbia.edu/~smb - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: road toll transponder hacked
everything forever. With disk prices falling as they are, keeping everything is cheaper than careful selective deletion, that's for sure. I disagree. We've been helping the German Toll Collect system (as discussed in this thread as well) setting up and implementing their data privacy concept. This concept requires Toll Collect to delete almost any data after a certain (quite short, actually) amount of time. Even with disk prices falling they save lots and lots of money (even compared to what we charged them for telling them... :-) ). Cheers, Stefan. Symposium Wirtschaftsspionage 03.09.2008 KA/Ettlingen http://www.symposium-wirtschaftsspionage.de/ - Stefan Kelm Security Consulting Secorvo Security Consulting GmbH Ettlinger Strasse 12-14, D-76137 Karlsruhe Tel. +49 721 255171-304, Fax +49 721 255171-100 [EMAIL PROTECTED], http://www.secorvo.de/ PGP: 87AE E858 CCBC C3A2 E633 D139 B0D9 212B Mannheim HRB 108319, Geschaeftsfuehrer: Dirk Fox - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
privacy in public places
There has been a lot of talk on the list recently about the privacy issues associated with various toll and fare collecting systems, but others have been pointing out, correctly I think, that this matters less and less because of other technological developments. New York City recently announced plans to use license plate OCR to produce and keep records of every car entering and leaving the city and to keep those records for years. Very little attention was paid to this, but I think it is the mark of things to come. Although the huge infestations of video cameras in our cities have had almost no impact on crime, once they are combined with sufficiently potent image recognition software, it will become possible to track people's movements and keep records of those movements essentially forever. It also seems to me that almost anything that can be done will in fact happen in the current opposing the wish lists of the police is the same as being in favor of terrorism environment. Given this, I think the time for focusing on the privacy implications of payment transponders and fare cars is over. Not carrying a cell phone will not help you avoid tracking when your environment is saturated with cameras. Digital cash toll collection systems will not avoid records being kept of your car's movements when cameras are reading and recording license plates anyway. Unfortunately, I don't see anything technological that people can reasonably do here to provide more privacy, at least short of everyone going everywhere on foot while wearing a burqa and periodically attempting to confuse the cameras. The solutions, if any exist at all, appear to be non-technical. Perry -- Perry E. Metzger[EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: road toll transponder hacked
On Thu, Aug 28, 2008 at 06:03:14PM +0200, Stefan Kelm wrote: We've been helping the German Toll Collect system (as discussed in this thread as well) setting up and implementing their data privacy concept. This concept requires Toll Collect to delete almost any data after a certain (quite short, actually) They (not Toll Collect, though) do a realtime query against a reasonably long list of license plates in some German states, I recall reading. http://www.heise.de/newsticker/Hessische-Polizei-hat-seit-Maerz-eine-Million-Kfz-Kennzeichen-gescannt--/meldung/99197 amount of time. Even with disk prices falling they save lots and lots of money (even compared to what we charged them for telling them... :-) ). Given where things are headed in Germany, I guarantee you Toll Collect will be required by law to do data retention for at least a year or two in less than 5 years. http://www.heise.de/newsticker/Debatte-um-Zugriff-auf-LKW-Mautdaten-fuer-Fahndungen-geht-weiter--/meldung/76321 -- Eugen* Leitl a href=http://leitl.org;leitl/a http://leitl.org __ ICBM: 48.07100, 11.36820 http://www.ativel.com http://postbiota.org 8B29F6BE: 099D 78BA 2FD3 B014 B08A 7779 75B0 2443 8B29 F6BE - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Decimal encryption
Hello, Actually, block ciphers encrypting blocks of *decimal* numbers exist: - TOY100 [1] encrypts blocks of 32 decimal digits - DEAN18 [2] encrypts blocks of 18 decimal digits - DEAN27 [3] encrypts blocks of 27 decimal digits TOY100 is (almost) broken by the generalized linear cryptanalysis described in [2]. Both versions of DEAN are based on a substitution permutation network very close to that of the AES and are provably secure against linear cryptanalysis. These ciphers are only toy ciphers. Consequently, there is no official implementation (no test- vector, etc.). Here are the references: [1] Granboulan, Levieil, Piret: Pseudorandom Permutation Families over Abelian Groups. FSE 2006: 57-77 [2] Baignères, Stern, Vaudenay: Linear Cryptanalysis of Non Binary Ciphers. Selected Areas in Cryptography 2007: 184-211 (available here: http://lasecwww.epfl.ch/~tbaigner/papers/groupLC.pdf ) [3] Baignères (PhD Thesis): Quantitative Security of Block Ciphers: Designs and Security Tools (to be published) I hope this helps. I'm of course available for any question regarding DEANxx. Best regards, Thomas Baignères -- http://lasecwww.epfl.ch/~tbaigner On Aug 27, 2008, at 5:05 PM, Philipp Gühring wrote: Hi, I am searching for symmetric encryption algorithms for decimal strings. Let's say we have various 40-digit decimal numbers: 2349823966232362361233845734628834823823 3250920019325023523623692235235728239462 0198230198519248209721383748374928601923 As far as I calculated, a decimal has the equivalent of about 3,3219 bits, so with 40 digits, we have about 132,877 bits. Now I would like to encrypt those numbers in a way that the result is a decimal number again (that's one of the basic rules of symmetric encryption algorithms as far as I remember). Since the 132,877 bits is similar to 128 bit encryption (like eg. AES), I would like to use an algorithm with a somewhat comparable strength to AES. But the problem is that I have 132,877 bits, not 128 bits. And I can't cut it off or enhance it, since the result has to be a 40 digit decimal number again. Does anyone know a an algorithm that has reasonable strength and is able to operate on non-binary data? Preferrably on any chosen number-base? Best regards, Philipp Gühring - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Decimal encryption
One of the earlier messages (I lost it) said that Philipp said that there was information that could be used as a nonce. In that case, I would recommend a stream cipher used to generate 133 bits at a time; if the lump of bits represents an integer in the correct range, add it modulo 10^40... otherwise generate more bits. This is about as simple as it gets. Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
