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: 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: 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: 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]
Re: Decimal encryption
At Wed, 27 Aug 2008 17:05:44 +0200, 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? 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. For a modern proposal to make this a NIST mode, see: http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/ffsem/ffsem-spec.pdf -Ekr Full Disclosure: Terence Spies, the author of the FFSEM proposal, works for Voltage, Voltage has a product based on this technology. and I'm on Voltage's TAB and have done some work for them. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Decimal encryption
=?ISO-8859-15?Q?Philipp_G=FChring?= [EMAIL PROTECTED] writes: 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? I posted a description of how to perform encryption in limited subranges to sci.crypt about ten years ago, http://groups.google.com/groups?hl=enlr=ie=UTF-8threadm=5c8sin%24piv%40scream.auckland.ac.nzrnum=1prev=/groups%3Fq%3D%2B%2522ASCII%2522%2Bgroup:sci.crypt%2Bauthor:Peter%2Bauthor:Gutmann%26hl%3Den%26lr%3D%26ie%3DUTF-8%26as_drrb%3Db%26as_mind%3D12%26as_minm%3D5%26as_miny%3D1996%26as_maxd%3D17%26as_maxm%3D7%26as_maxy%3D1998%26selm%3D5c8sin%2524piv%2540scream.auckland.ac.nz%26rnum%3D1, the code and a cleaned-up description is also in Building Secure Software by John Viega and Gary McGraw. Peter. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Decimal encryption
On Wed, 27 Aug 2008 17:05:44 +0200 Philipp G__hring [EMAIL PROTECTED] 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? Do you want a stream cipher or a block cipher? For the former, it's easy. Use something like rc4, which produces a sequence of keystream bytes. Retrieve the low-order N bits from each key stream byte, where N is large enough for the base you're using. If the value is greater than or equal to the base you're using, discard that byte and try again. For your example, you'd use the low-order 4 bits, but discard any bytes whose value is = 10. Add this value, discarding the carry, to the digit to be encrypted. You're running RC4 at 5/8 efficiency; unless you have a *lot* of data, that almost certainly doesn't matter. --Steve Bellovin, http://www.cs.columbia.edu/~smb - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Decimal encryption
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? The short answer is no, nobody knows a secure algorithm that would work as a decimal stream cipher AND would not extend the message size for some form of key material reference data (or salt or IV ...). If you have room for such message-specific reference data, it should be easy to design a decimal stream cipher for short messages. -- - Thierry Moreau - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Decimal encryption
Philipp Gühring wrote: Hi, G'day Philipp, 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? There is a fairly standard technique for handling things like this. 1. encode your number N into a 133-bit string S 2. encrypt S with your favourite 133-bit block cipher (see below) 3. decode S to a number N' 4. if N' = 10^40, goto 2 (that is, re-encrypt until it is in range) 5. N' is your answer. This is uniquely invertible, although a little slow (since on average it will take 8.9% or so more encryptions because of the inner loop, and some side-channel information leaks when it does the extra encryptions. Decryption is exactly the same operation except step 2 uses decryption mode of the block cipher. 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). To decrypt, do decryptions in the reverse order, obviously. It's easy to see that this is a secure permutation if AES itself is, depending on your definition of secure; if you add a third step, to re-encrypt the first 128 bits, it is truly secure. (Without the third step, tweaking a bit in the first 5 bits will often leave the last 5 unchanged on decryption, which is clearly a distinguishing attack; the third encryption makes it an all-or-nothing transform.) I believe the above gives you a secure enough block cipher on 40 digit strings, and if you only ever encrypt single chunks, ECB mode should be fine... of course that depends on the real threat analysis of your system. It does about 2.19 AES encryptions per 40 digits, should be fast enough. hope that helps, Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Decimal encryption
Philipp Gühring writes: 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. Right, although as an American I was confused for a moment until I remembered the European convention of using comma for the decimal point, while we use period. But you are right and it was my mistake. 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. This is a very common question. Unfortunately the state of the art in cryptography does not as far as I know have a good answer. The most recent analysis I found is http://www.cs.ucdavis.edu/~rogaway/papers/subset.pdf from CT-RSA 2002 by Black and Rogaway. Basically they propose what is called a Luby-Rackoff construction, related to another construction called a Feistel network. Unfortunately their analysis does not show that this is secure, but I believe that by adding more steps it can be made so. The idea is to start with your 40 digit number and split it into two parts of 20 digits. Call the left part L and the right part R. Then repeatedly execute the following steps: L = (L xor AES(R)) mod 10^20 (L,R) = (R,L) (i.e. interchange L and R) After doing this a certain number of steps, interchange L and R one last time, and concatenate L and R to get your output. (Equivalently, skip the interchange of L and R on the last step.) Now, it is important in doing this that AES have a different key for each round or step. You can start with a single key K, and generate the round keys as K0 = AES(K,0), K1 = AES(K,1), K2 = AES(K,2), and so on. To decrypt, the same basic process is used. But this time, use the round keys in the reverse order. Instead of K0, K1, K2, use K2, K1, K0. Black and Rogaway analyzed for just 3 rounds, and they found basically that for your case, this construction would only have about 32 bits of strength; that is, after encrypting about 4 billion numbers, you would be losing security. If you are only ever encrypting many fewer numbers than this (with a given key), it should probably be OK. The other possibility is to increase the number of rounds. The paper hints that this will help but does not offer any specific analysis. I saw a speculative comment online that 8 rounds would be strong. I believe that going back to the Luby-Rackoff paper may offer some guidance, but I don't have time to do that now. Note that this unfortunately does not get the benefit you were hoping for from being so close to the AES block size. While there are some known tricks for dealing with being a little shorter than the cipher block, I couldn't find any good ones for being a few bits longer. Hal Finney - 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 17:05:44 +0200, 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? 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. 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. For a modern proposal to make this a NIST mode, see: http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/ffsem/ffsem-spec.pdf -Ekr Full Disclosure: Terence Spies, the author of the FFSEM proposal, works for Voltage, Voltage has a product based on this technology. and I'm on Voltage's TAB and have done some work for them. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Decimal encryption
Philipp Gühring wote: 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. English readers normally use . as the decimal point - you had me confused for a few seconds and maybe it wasn't only me. Regardless of the calculated bit-equivalent you aren't storing these strings in 132.877 bits - but possibly 40*8 bits, 40*4 bits or in some other way. 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). I don't think that's a feature of the encryption as such. 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. This sounds like possible confusion over block length and key size. Then you get involved in padding and storage of a slightly larger ciphertext. 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? It sounds as if you want a stream cipher arrangement that you could make out of a normal binary stream cipher by: read a byte of the keystream if 9 reject it and take the next one (aiming for uniform distribution) if the value is [0-9] add it to the current plaintext digit mod 10 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Decimal encryption
On Wed, 27 Aug 2008 09:34:15 -0700 Greg Rose [EMAIL PROTECTED] wrote: So, you don't have a 133-bit block cipher lying around? No worries, I'll sell you one ;-). Also see Debra Cook's PhD dissertation on Elastic Block Ciphers at http://www1.cs.columbia.edu/~dcook/thesis_ab.shtml --Steve Bellovin, http://www.cs.columbia.edu/~smb - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Decimal encryption
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? 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 suppose it depends what you mean by small and large. A lot of the relevant values are things like SSNs, CCNs, etc. which fall in the 10-20 digit category, where the Luby-Rackoff approach is efficient. As I understand the situation, the cycle following approach is efficient as long as the set is reasonably close to the L-R block size. As far as dictionary attacks go, for any small domain permutation you have to worry about table construction attacks. The only defense I know of is randomized encryption which defeats the non-expansion requirement. WRT to the security of the L-R construction, Spies claims that I believe that Patarin's 2004 result [0] is relevant here, but I'm not qualified to evaluate it. Anyway, the reference I provided earlier [1] provides a summary of the claimed security properties of L-R + Cycle Following. -Ekr [0] Jacques Patarin. Security of random feistel schemes with 5 or more rounds. In Matthew K. Franklin, editor, CRYPTO, volume 3152 of Lecture Notes in Computer Science, pages 106?122. Springer, 2004. [1] http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/ ffsem/ffsem-spec.pdf - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Decimal encryption
I like Greg Rose's solution best: There is a fairly standard technique for handling things like this. 1. encode your number N into a 133-bit string S 2. encrypt S with your favourite 133-bit block cipher (see below) 3. decode S to a number N' 4. if N' = 10^40, goto 2 (that is, re-encrypt until it is in range) 5. N' is your answer. This is Rich Schroeppel's trick from his Hasty Pudding cipher, a somewhat under-rated AES submission IMO. HPC originated not only this trick, but also the idea of tweakable encryption, which has turned out to be important for disk encryption. The Black-Rogaway paper referenced earlier has a proof of security of this construction. 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). I didn't understand this at first, but I finally saw that the point is to do the encryptions in-place; step 1 replaces the first 128 bits of the data with the encryption, and similarly for step 2. This is equivalent to doing CBC mode with a fixed IV of 0, and ciphertext stealing for the final partial block of 5 bits. To decrypt, do decryptions in the reverse order, obviously. It's easy to see that this is a secure permutation if AES itself is, depending on your definition of secure; if you add a third step, to re-encrypt the first 128 bits, it is truly secure. (Without the third step, tweaking a bit in the first 5 bits will often leave the last 5 unchanged on decryption, which is clearly a distinguishing attack; the third encryption makes it an all-or-nothing transform.) I am not familiar with the security proof here, do you have a reference? Or is it an exercise for the student? Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Decimal encryption
Hal Finney 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). I didn't understand this at first, but I finally saw that the point is to do the encryptions in-place; step 1 replaces the first 128 bits of the data with the encryption, and similarly for step 2. This is equivalent to doing CBC mode with a fixed IV of 0, and ciphertext stealing for the final partial block of 5 bits. Yes, I guess it is... hadn't thought of it that way. But yes, I confirm that I meant to do the encryptions in place. To decrypt, do decryptions in the reverse order, obviously. It's easy to see that this is a secure permutation if AES itself is, depending on your definition of secure; if you add a third step, to re-encrypt the first 128 bits, it is truly secure. (Without the third step, tweaking a bit in the first 5 bits will often leave the last 5 unchanged on decryption, which is clearly a distinguishing attack; the third encryption makes it an all-or-nothing transform.) 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. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
