Encrypting odd sized buffers
in [Cryptography]
|
From: unruh on 23 Jun 2010 03:58 On 2010-06-23, 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. split input into input1 input2 each 54 bits long (Actually padding out to 56 bits would probably be far more convenient)(however you want to do so) Define a round as inputs are c1, c2 d1=Tmd5(key1+c1)^c2 d2=Tmd5(key2+d1)^c1 c1=d1 c2=d2 repeat N times. Start out with c1=input1, c2=input2 End up with c1,c2 as the encryptede output. Decrypt round input=c1,c2 d1=Tmd5(key2+c1)^c2 d2=Tmd5(key1+d1)^c1 repeat N times Tmd5 is md5 truncated to 54 (56)bits, ^ is xor, + is concatenation. key1, key2 are two keys ( could be the same as each other, could depend on the round number) Could be as long as you want. Not going to be terribly fast. > >> There was also the Hasty Pudding Cipher, a variable-sized block cipher >> from the original AES competition. > Thanks, I am looking at this as an option. > >> What is the application, if you can say? A block cipher may not be what >> you want. > It is to generate a unique set of random numbers, but I need > to generate millions of them. I want to take advantage of > the one to one mapping of input to output that a block > cipher can provide. Perhaps there are specialized PRNGs for > this, but I am not aware of any. > > >If you just want unique 108 bit numbers, you're better off >> using plain random numbers and accepting the very low chance of an >> collision through an accident of nature, than trying to generate them >> from a sequence, and ending up with the much higher chance of using the >> same seed twice through the likelier error of some human. > Normally this would suffice, but for this application the > algorithm must offer a strong guarantee that the sequence is > unique. What is a "strong guarentee". And how many unique ones do you need? For a random function, the chances of repeating are essentiall 1-(2^108!/(2^108-N)!2^(108N)) which is really really small until N gets of order 2^54. (You say you need millions. Lets take N=10^9, a billion,=2^30 Then the probability of repeats is roughly 1-exp(-(N(N+1))/2^109) for N<2^100) so this is 2^(-50)=10^(-15) Ie after you have issued a billion numbers, the probability of repeats is far less than the probablility that civilization will be destroyed by an asteroid strike in the next year. Is that a sufficeintly "strong guarentee" It is certainly far far far far less than the probablility that your company will go out of business or that eveyone in management will be killed at once due to some accident.
From: Tran Ngoc Duong on 23 Jun 2010 04:13 On Jun 22, 1:40 pm, Ross MacGregor <ross__macgre...(a)hotmail.com> wrote: > Is there a symmetric block encryption algorithm that can > encrypt a 108 bit buffer using a key and output a 108 bit > buffer? > > I'd like to feed it a sequential range of numbers > (1001,1002,1003,1004...) and have the algorithm generate for > me a pseudo-random sequence of numbers that are guaranteed > to be unique. This is why it is important that I only encode > the 108 bits of data as this is the size of the random > number I need to generate. > > I've been searching for days for a bit level encryption > algorithm but everything seems to be based on byte sized > buffers. Here is a 108-bit block cipher that I've just crafted specifically for your need. It is a 54-round Feistel structure and it uses the function f(x) = (x*(2*x+1)) <<< 18 (over 54-bit numbers). #define ML54 ((1<<54)-1) #define ML36 ((1<<36)-1) #define U54( x ) (x & ML54) #define ROTL18( x ) (( (x & ML36) << 18) ) | ((x & ~ML36)>>36) ) unsigned x0, x1, t, Z[54]; // Assume 64-bit unsigned expand key into Z[]; (x0, x1) = plaintext; for(i = 0; i<53; i++) { t = x0+Z[i]+i; x1 ^= ROTL18(U54(t*(2*t+1))); swap x0, x1; } ciphertext = (x0, x1);
From: Kristian Gj�steen on 23 Jun 2010 04:20 Ross MacGregor <ross__macgregor(a)hotmail.com> wrote: >I am a senior software >developer but without much cryptographic experience. > >Paul Rubin wrote: >>[...] >> There was also the Hasty Pudding Cipher, a variable-sized block cipher >> from the original AES competition. >Thanks, I am looking at this as an option. Use Hasty Pudding. I don't think Luby-Rackoff is a fail-safe construction. If a system contains a Luby-Rackoff cipher cobbled together by a non-cryptography, that system should fail at the first security review. Alternatively, use AES(k,.) truncated to 108 bits (or truncated SHA-2(k || .) or ...), which will most likely be a permutation as long as you don't evaluate it at too many points. -- kg
From: Maaartin on 23 Jun 2010 04:49 On Jun 23, 10:20 am, Kristian Gj steen <kristiag+n...(a)math.ntnu.no> wrote: > Use Hasty Pudding. I don't think Luby-Rackoff is a fail-safe > construction. If a system contains a Luby-Rackoff cipher cobbled > together by a non-cryptography, that system should fail at the first > security review. Why? The following is orders of magnitude simpler than HPC, so how can be the error-rate higher? for (int i=0; i<6; ++i) { x ^= truncateTo54bits(hash(concat(y, key[i]))); swap(x, y); }
From: Mok-Kong Shen on 23 Jun 2010 04:56
Ross MacGregor wrote: > > Mok-Kong Shen wrote: >> Ross MacGregor wrote: >> What do you exactly mean by 'byte sized buffers' above? Do you simply >> want a more or less good bijective mapping that transforms 108 bits to >> 108 bits > Yes, this is all I am looking for. I was just trying to say that all the > block cyphers I've seen use fixed sized buffers. I realize that my question was not absolutely unambiguous. Could you concretely state the properties you expect of such a mapping? M. K. Shen |