Encrypting odd sized buffers
in [Cryptography]
|
From: rossum on 23 Jun 2010 14:44 On Tue, 22 Jun 2010 23:34:49 -0700, Ross MacGregor <ross__macgregor(a)hotmail.com> wrote: >Thanks everyone for giving me the better search terms. > >Paul Rubin wrote: >> If you don't care about speed, the simplest thing to do is chop the 108 >> bits in half and make a Feistel cipher using some standard cryptographic >> hash function as the round function. >Sounds interesting, can anyone point me to some code to help >me implement such a thing? What would be a "standard >cryptographic hash function?" I am a senior software >developer but without much cryptographic experience. The Wikipedia article is helpful. The nice thing about Feistel is that you can put anything (reasonable) you want into the F function, it does not have to be reversible. That gives you a lot of flexibility. Hash functions are covered in Wikipedia under 'Cryptographic Hash Functions'. Use SHA-1, SHA-256, SHA-512, MD-4 or MD-5. SHA-1 and MD-4 are not completely secure, but if you have no security requirement then this will not matter. The main problem you are likely to have is fitting 108/54 bits into your program. You also don't say if you require that the block cypher you use has to be secure, i.e. does it matter if someone can reverse your algorithm to get back to the original counter that you encrypted in the first place? I get the impression that this aspect is not very important; you just want provably unique random numbers. Here is my amateur attempt at an insecure 108 bit block Feistel cypher. You do not state a language preference so I will use pseudocode. rossum // --- Pseudocode --- // int64 mask54 <- (1 << 54) - 1 // Four is the minimum number of rounds you should use. int32 numRounds <- 4 function int128 encrypt(int128 plaintext, int128 key) // Split plaintext into two 54 bit halves int64 rightHalf <- plaintext AND mask54 int64 leftHalf <- (plaintext >> 54) AND mask54 // Do the rounds for (int32 count <- 0; count < numRounds; ++count) do // No swap on first round if (count > 0) then // Swap left and right int64 temp <- rightHalf rightHalf <- leftHalf leftHalf <- temp endif rightHalf <- rightHalf XOR F(leftHalf, key) endfor // Reassemble halves int128 cyphertext <- (leftHalf << 54) + rightHalf return cyphertext endfunction // You have a lot of flexibility with function F // what I have written is just a suggestion function int64 F(int64 halfBlock, int128 key) // MD5 hash returns 128 bits int128 temp <- MD5(halfBlock XOR key) // Preserve (some) high bits temp <- temp XOR (temp >> 64) // Ensure 54 bit return return (temp AND mask54) endfunction
From: Francois Grieu on 23 Jun 2010 18:32 This thread drifted to exploring the suitability of r rounds of Feistel cipher with an independent PRF at each round, for building a PRP of an input of n bits. <http://en.wikipedia.org/wiki/Feistel_cipher> Unless otherwise noted, n is even, each PRF has n/2 bits of input and output (symmetric Feistel cipher), we focus on n<=8. My understanding is that Luby & Rackoff have proven that for r>=4, breaking the PRP requires work exponential in n, even under choosen-plaintext and choosen-ciphertext attack. This is an asymptotic result, NOT applicable to the small n that we consider. Each PRFs is uniquely defined by n*(2**(n/2-1)) bits, and there are 2**(r*n*(2**(n/2-1))) possible choices of PRFs. The number of permutations of the n-bit message space is (2**n)! When r>=3, any reachable permutation corresponds to at least 2**(n/2) different sets of PRFs for r=3, at least 2**n for r=4. [proof hint: XORing the output of the first PRF with any constant can be compensated by XORing the input of the second PRF and output of the third PRF with that same constant] Worse, some permutations are reached more often than that. For r=3, a permutation that reduce to inversion of the two halves and XOR with a constant K is reached exactly 2**(n*(2**(n/2-1))) times [proof hint: the first PRF can be chosen arbitrarily, the second and third PRF are then uniquely defined by K and the first PRF]. For r = 4, any of the 2**n permutations reducing to XOR with a constant can be reached if either the first or second PRF is constant. For example, for n = r = 4, we have 4294967296 choices of PRF versus 20922789888000 permutations, each reachable permutation is reached at least 16 times (at least 2032 times for some), thus less than one permutation in 77943 can be reached. Since 77943 > 8!, knowing the output of the permutation for half of the 16 distinct input values is generally more than enough to predict the output for all the other input values. Francois Grieu
From: Maaartin on 23 Jun 2010 19:28 On Jun 24, 12:32 am, Francois Grieu <fgr...(a)gmail.com> wrote: > My understanding is that Luby & Rackoff have proven that for > r>=4, breaking the PRP requires work exponential in n, even > under choosen-plaintext and choosen-ciphertext attack. This is > an asymptotic result, NOT applicable to the small n that we > consider. So you say, we have nothing for small n, right? We could use more rounds and this would help against your argument (I mean your counting of achievable permutations etc.), but still we have no security proof whatsoever, right? So there's only HPC left, but I've got the feeling, nobody took it seriously, so do we have nothing at all?
From: Paul Rubin on 23 Jun 2010 20:34 Maaartin <grajcar1(a)seznam.cz> writes: > So there's only HPC left, but I've got the feeling, nobody took it > seriously, so do we have nothing at all? Patarin has a bunch of papers on multi-round Luby-Rackoff including one in Crypto 2003 that I've been wanting to read: http://www.iacr.org/archive/crypto2003/27290510/27290510.pdf Bellare did something called VIL mode which is apparently patented: http://cseweb.ucsd.edu/~mihir/papers/lpe.pdf There is a wikipedia article "format preserving encryption" on the general subject: http://en.wikipedia.org/wiki/Format-preserving_encryption For the OP's original question (108 bits) I think 4 rounds of Luby-Rackoff / SHA should do a reasonable job (somebody has already posted sample code). If overkill is desired, use more rounds.
From: Ross MacGregor on 23 Jun 2010 22:29
Mok-Kong Shen wrote: > [Addendum] I meant that the wordings of your previous posts leave open > a (IMHO at least 'minutely') possible interpretation that security might > not be a requirement for you and what you seek was only randomness, in > which case the solution would have been rather simple. > > M. K. Shen Yes, randomness is what I am seeking. I am actually trying to build a non-repeating PRNG to fit a 108 bit number space. |