Encrypting odd sized buffers
in [Cryptography]
|
From: Paul Rubin on 24 Jun 2010 20:33 Ross MacGregor <gordonrossmacgregor(a)gmail.com> writes: > Yes, the key will be secured from users/attackers. The input for a > generated set of numbers will start with a random 108 bit number that > will be incremented (+1 likely) for each number generated. This input > value will also be secured from users/attackers. OK. Now your security rests on two things: 1) secrecy of the key, and 2) pseudo-randomness of the permutation. Your SHA-based block cipher handles the permutation acceptably, I think. But now you've got a key management problem (what are you going to do to ensure that the key doesn't get loose), that may become an issue at your audit. Without knowing your application I don't know how relevant this is. You might look at the FIPS 140-2 and 140-3 standards to see what's expected of crypto hardware. > The ability of our users to collect past elements is very restricted > and total elements generated will be in the order of 30 million. If this is for something like software serialization, that may be sufficient. Otherwise, preventing users from communicating with each other doesn't sound feasible in general (maybe it's possible for your specific application). By "past elements", though, I was imagining that you were using these numbers as encryption keys, which means an attacker who gets even a single past element can decrypt any traffic they recorded that was encrypted under that key. Generating them deterministically as you're proposing in that case creates the possibility of an attacker getting -all- the keys.
From: Mok-Kong Shen on 25 Jun 2010 08:04 Ross MacGregor wrote: > On Jun 24, 1:13 am, Mok-Kong Shen<mok-kong.s...(a)t-online.de> wrote: >> Just a question out of curiosity: What's the problem of using the >> simplest PRNG f(x)=a*x+b mod 2^108 (a odd) in your application? > > Sorry, I haven't been very clear with what I am looking for. We have > an existing application that uses a similar scrambling function, but > there are concerns that you can predict the sequence if you know the > function. This is why I am interested in the encryption approach and > using a key to encode the output. A secure solution would be best. Since there is 'some' security concern in your application, using a block encryption would be in order. Despite my humble knowledge, I'll venture to make a concrete sketch of a scheme employing the well-known technique of Feistel. (I hope to be able herewith to learn something from the group, in case my layman's design turns out to be defective or even highly wrong.) I assume 32 bit unsigned long int. The 108 bit input is first evenly separated into 4 words W1, W2, W3, W4, right adjusted. At the end of the computations below, 27 lower order bits of each word will be masked out to be assmebled to become the output. fi_j(x) designates a polynomial whose coefficients satisfy some constraints to be stated below. There will be a number of rounds. In the i-th round, one does the following: W2 = fi_12(W1) ^ W2; W1 = fi_21(W2) ^ W1; W4 = fi_34(W3) ^ W4; W3 = fi_43(W4) ^ W3; W3 = fi_13(W1) ^ W3; W1 = fi_31(W3) ^ W1; W4 = fi_24(W2) ^ W4; W2 = fi_42(W4) ^ W2; fi_j(x) is chosen to be a 2nd degree polynomial fi_j(x) = c_0 + c_1*x + c_2*x^2 whose coefficients are successive outputs from a PRNG: x_(i+1) = F(x_i) adjusted to satisfy: c_0 = 1 mod 2 c_1 = 1 mod 4 c_2 = 0 mod 4 F(x) is chosen to be a 3rd or 4th degree polynomial F(x) = C_0 + C_1*x + C_2*x^2 + C_3*x^3 + C_4*x^4 whose coefficients are to be randomly chosen by the application (this is the 'key', of 128 or 160 bit length) adjusted to satisfy: C_0 = 1 mod 2 C_1 = 1 mod 4 C_2 = 0 mod 4 C_3 = 0 mod 4 C_4 = 0 mod 4 As to the number of rounds needed, I have no exact idea but think that 5 rounds probably may well be sufficient for your application. M. K. Shen
From: Tran Ngoc Duong on 25 Jun 2010 09:40 On Jun 25, 7:04 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > I assume 32 bit unsigned long int. The 108 bit input is first evenly > separated into 4 words W1, W2, W3, W4, right adjusted. At the end > of the computations below, 27 lower order bits of each word will be > masked out to be assmebled to become the output. fi_j(x) designates > a polynomial whose coefficients satisfy some constraints to be > stated below. There will be a number of rounds. In the i-th round, one > does the following: > > W2 = fi_12(W1) ^ W2; W1 = fi_21(W2) ^ W1; > W4 = fi_34(W3) ^ W4; W3 = fi_43(W4) ^ W3; > W3 = fi_13(W1) ^ W3; W1 = fi_31(W3) ^ W1; > W4 = fi_24(W2) ^ W4; W2 = fi_42(W4) ^ W2; > > fi_j(x) is chosen to be a 2nd degree polynomial > > fi_j(x) = c_0 + c_1*x + c_2*x^2 > > whose coefficients are successive outputs from a PRNG: x_(i+1) = F(x_i) > adjusted to satisfy: > > c_0 = 1 mod 2 c_1 = 1 mod 4 c_2 = 0 mod 4 > > F(x) is chosen to be a 3rd or 4th degree polynomial > > F(x) = C_0 + C_1*x + C_2*x^2 + C_3*x^3 + C_4*x^4 > > whose coefficients are to be randomly chosen by the application (this > is the 'key', of 128 or 160 bit length) adjusted to satisfy: > > C_0 = 1 mod 2 C_1 = 1 mod 4 C_2 = 0 mod 4 > C_3 = 0 mod 4 C_4 = 0 mod 4 > > As to the number of rounds needed, I have no exact idea but think that > 5 rounds probably may well be sufficient for your application. > It doesn't seem clear to me how can a high order bit of a plaintext word affect low order bit of the same word of the ciphertext.
From: Mok-Kong Shen on 25 Jun 2010 10:25 Tran Ngoc Duong wrote: > It doesn't seem clear to me how can a high order bit of a plaintext > word affect low order bit of the same word of the ciphertext. You have quickly picked out a big error of mine. Thank you very much. Let me propose a certainly criticizable fix: One rotates the lower-order 27 bits of the words by some randomly determined amounts, say, after each update. M. K. Shen
From: Maaartin on 26 Jun 2010 06:50
On Jun 24, 9:01 am, Ross MacGregor <ross__macgre...(a)hotmail.com> wrote: > You guys are awesome, thanks for all the help! > > unruh wrote: > > 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. > > Thank for algorithm. I coded this up today and it works! I > used sha2 instead of md5. Although md5 is broken, I don't think it shouldn't be used here. Using md5 you could do about twice as much rounds in the same time and it could be more secure - just an idea, await the expert's comments. > I'm curious why the algorithm is written like this and not > more like Maaartin's and Tran Ngoc Duong's algorithm below. > It seems better expressed that way. Is it done like this to > only use two keys? I've got no idea why this is written like this. It's the same except for doing twice as much work in one round. I'd suggest using different key in each iteration, most probably it's for free (you derive all keys from the master key, don't you). > When they say that 5 rounds should be enough to sufficently > scramble the output, do they me 5 iterations of the above > algorithm or the ones below? There are papers pointed in this thread, one of them proves something for 4 rounds and one proves something for 7 rounds. I haven't read them carefully enough to be able to claim what to do. |