Re: Looking through a modulo operation
"Matt Ball" wrote > Here is a C implementation of __random32: > > typedef unsigned long u32; > struct rnd_state { u32 s1, s2, s3; }; > static u32 __random32(struct rnd_state *state) > { > #define TAUSWORTHE(s,a,b,c,d) ((s&c)<>b) > > state->s1 = TAUSWORTHE(state->s1, 13, 19, 4294967294UL, 12); > state->s2 = TAUSWORTHE(state->s2, 2, 25, 4294967288UL, 4); > state->s3 = TAUSWORTHE(state->s3, 3, 11, 4294967280UL, 17); > > return (state->s1 ^ state->s2 ^ state->s3); > } I see TAUSWORTHE (briefly tested with the above constants) isn't a permutation of the 32-bit input state and is going to get very dull when s is 0. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Looking through a modulo operation
Matt Ball writes: >Another attacking avenue is the 32-bit initial seed. If the >implementation re-seeds frequently, or leaks to you the first outputs >after initialization, then you only have to brute-force the 32-bit >seed space, times the number of samples since reseeding. Well, that's good and broken then, isn't it? No ifs about it. It doesn't matter whether the implementation re-seeds frequently or rarely. It doesn't matter whether it leaks to you the first outputs after initialization or only later ones. If it's using a 32-bit seed, this sucker is just plain broken, period. The attack is trivial -- it's just exhaustive keysearch. Attack: Given ~ 3 known outputs from the RNG, try all possible 32-bit seeds. You'll be able to recognize when your guess at the seed is correct because the output from your guessed seed will match the observed output. This assumes you know the offsets of your outputs (how many times the RNG has been cranked before producing your known outputs), but even if you only have partial information about that you can still make a variant of this attack work. The exhaustive search attack has to try only 2^32 possibilities, so I'm guessing this attack should only take minutes (at worst, hours) on a fast computer. My earlier email about fancy attacks on this scheme is irrelevant. There's no need to bother with fancy attacks, when the PRNG only uses a 32-bit seed -- that's just blatantly insecure. This is a textbook error, one of the oldest mistakes in the book. (For example, look here: http://www.cs.berkeley.edu/~daw/papers/ddj-netscape.html) Using this PRNG for security-critical purposes would not be wise. I'll include your code snippet for seeding the PRNG below. Note: I'm assuming, per your comments, that "unsigned long" is a 32-bit type. >Here is the function that performs the initial seeding, based on a 32-bit seed: > >static void __set_random32(struct rnd_state *state, unsigned long s) >{ >if (s == 0) >s = 1; /* default seed is 1 */ >#define LCG(n) (69069 * n) >state->s1 = LCG(s); >state->s2 = LCG(state->s1); >state->s3 = LCG(state->s2); >/* "warm it up" */ >__random32(state); >__random32(state); >__random32(state); >__random32(state); >__random32(state); >__random32(state); >} - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Looking through a modulo operation
On Mon, Jul 21, 2008 at 8:33 AM, Matt Ball <[EMAIL PROTECTED]> wrote: > >"If someone uses the __random32 function as defined in the 2.6.26 > Linux kernel, and leaks to you the result of taking successive outputs > modulo 28233 (= 9 * 3137), can you determine the probable 96-bit > internal state with fewer than 1000 outputs and with modest processing > power (e.g., a laptop computer running less than a day)?" > Another attacking avenue is the 32-bit initial seed. If the implementation re-seeds frequently, or leaks to you the first outputs after initialization, then you only have to brute-force the 32-bit seed space, times the number of samples since reseeding. Here is the function that performs the initial seeding, based on a 32-bit seed: static void __set_random32(struct rnd_state *state, unsigned long s) { if (s == 0) s = 1; /* default seed is 1 */ #define LCG(n) (69069 * n) state->s1 = LCG(s); state->s2 = LCG(state->s1); state->s3 = LCG(state->s2); /* "warm it up" */ __random32(state); __random32(state); __random32(state); __random32(state); __random32(state); __random32(state); } For those who want to get cleaver, I suspect there is an optimization for running __random32 six times. -- Thanks! Matt Ball, IEEE P1619.x SISWG Chair M.V. Ball Technical Consulting, Inc. Phone: 303-469-2469, Cell: 303-717-2717 http://www.mvballtech.com http://www.linkedin.com/in/matthewvball - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Looking through a modulo operation
On Mon, Jul 21, 2008 at 12:03:50PM -0400, Victor Duchovni wrote: > On Sun, Jul 20, 2008 at 04:14:33PM -0600, Matt Ball wrote: > > > >From a little bit of off-line discussion, I think I've got a restatement of > > the problem that is more suitable to those with a stronger programming > > background than mathematical background: > > > > "If someone uses the __random32 function as defined in the 2.6.26 Linux > > kernel, and leaks to you the result of taking successive outputs modulo > > 28233 (= 9 * 3137), can you determine the probable 96-bit internal state > > with fewer than 1000 outputs and with modest processing power (e.g., a > > laptop computer running less than a day)?" I skipped over this part when reading the original message. Expecting per Florian's original message the outputs to be a "linear" function of the inputs, but they are not. > After any consecutive 96 outputs, the 97th is a fixed linear function of > those just observed. It is not necessary to determine the internal state. This of course applies to the 32-bit output of the RNG. The operation of reducing the 32-bit output modulo 28333, is not "linear" (over the F_2 bit string vector-space). While: x_96 = c_95 * x_95 + ... c_0 * x_0 this is only true bitwise modulo 2. It is not obvious how one might recover the full 32-bit outputs from the truncated outputs. -- /"\ ASCII RIBBON NOTICE: If received in error, \ / CAMPAIGN Victor Duchovni please destroy and notify X AGAINST IT Security, sender. Sender does not waive / \ HTML MAILMorgan Stanley confidentiality or privilege, and use is prohibited. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Looking through a modulo operation
Florian Weimer writes: > I've got a function f : S -> X x S where S = (Z/2Z)**96 and > X = (Z/2Z)**32. Suppose that s_0 is fixed and (x_i, s_i) = f(s_{i-1}). > (f implements a PRNG. The s_i are subsequent internal states and the > x_i are results.) > > Now f happens to be linear. I know the values of x_i, x_{i+1}, ..., > x_{i+k} modulo N, [where N = 28233]. > Is it possible to recover s_i with reasonable effort (better than brute > force, and k should be in the hundreds, not thousands)? Yes. I will show two attacks. The results: Attack #1 is a straightforward improvement to exhaustive search, and takes 2^52 work (~ 10-20 CPU-years?). Attack #2 is a more sophisticated meet-in-the-middle attack, and takes 2^37 work and 2^35 space; the best instantiation I've found looks like it would involve 16GB of RAM and a few days or weeks of computation. Both attacks recover the entire state of the PRNG, given only a handful of known outputs. It's possible there may be other, better attacks. My conclusion is that this PRNG is not cryptographically strong and should not be used anywhere that you may face an adversary who is motivated to break the PRNG. In short, this PRNG is broken. Attack #1: Given x mod N, there are only about 2^32/28233 = 2^17.2 possibilities for x, and it's easy to enumerate them all. Suppose we know x_1 mod N, x_2 mod N, ..., x_7 mod N. Enumerate all (2^17.2)^3 = 2^51.6 possibilities for x_1, x_2, and x_3. For each such possibility, you know 96 bits of output from a linear system, and there are 96 unknowns, so you can solve for s_0. Given s_0, you can compute the predicted value of x_4, .., x_7 and compare them to the observed values of x_4 mod N, etc. If everything matches, you've found the original seed s_0 and broken the PRNG. This requires trying 2^51.6 possibilities, so it's a bit less than 2^51.6 work. That's already a small enough number that the system is not cryptographically secure. This can be sped up slightly by noting that x_4 is a linear function of x_1,x_2,x_3. We can precompute the form of that linear function and express it as a 32x96 matrix. The best approach I can see will take something like 500 CPU cycles to compute x_4 from x_1,..,x_3, so I'd expect the total number of CPU cycles needed at something like 2^60.6 or so. On a 4GHz machine, that's like 13 CPU-years. Of course it is trivially parallelizable. Attack #2: If we were given inferred values of x_1, x_2, x_3, and x_4, we could check them for consistency, since they represent 128 equations in 96 unknowns. In particular, we can find a linear function g from 128 bits to 32 bits such that g(x_1,x_2,x_3,x_4) = 0 if x_1,..,x_4 are consistent with having been produced by this PRNG. In fact, this can be broken down further, so that if x_1,..,x_4 are consistent, they will satisfy this equation: h(x_1,x_2) = h'(x_3,x_4). Call this the check equation. Here h,h' are linear functions from 64 bits to 32 bits, so if x_1,..,x_4 are not consistent, they have only a 2^-32 chance of satisfying this check equation. Suppose we are given x_1 mod N, .., x_8 mod N. We'll enumerate all 2^34.4 possibilities for x_1,x_2, compute h(x_1,x_2) for each, and store them in a hash table or sorted list keyed on the 32-bit value of h(x_1,x_2). Once that table is built, we'll enumerate all 2^34.4 possibilities for x_3,x_4, compute h'(x_3,x_4) for each, and find all occurrences in the table where h(x_1,x_2) = h'(x_3,x_4). On average, we expect to find about 2^34.4/2^32 = 2^2.4 matches. For each such match, compute the predicted value of x_5 as a function of x_1,..,x_4 and see whether it agrees with the observed value of x_5 mod N, etc., to weed out false matches. In total, you'll need to explore 2^34.4 + 2^34.4*2^2.4 ~= 2^37 possibilities, and you'll need space for 2^34.4 entries in the table. We can store the table as a sorted list. This list will take up about 1600 GB, and you could buy enough hard disks for that at ~ $2000, say. You can add an index in memory that tells you, for each value of h(x_1,x_2), which block or sector on disk those entries of the list is found at. You'll need to make 2^34.4 random seeks into this hard disk array. With good disk head scheduling algorithms you might be able to get the seek time down a bit, but even optimistically we're probably still talking about a year of computation. Fortunately, we can trade time for space. With 16GB of RAM, we can store 1/128th of the list: namely, all values where the low 7 bits of h(x_1,x_2) are some fixed value V. We cycle through all choices of V, repeating the attack once for each V. With this choice, I expect the amount of time spent waiting for RAM to be comparable to the CPU cost of the attack. For each V, we have to evaluate a linear function 2^35.4 times. It looks to me like this will take a few CPU-days. Disclaimers: I have not checked any of the above analysis. I have not implemented it to test whether these attacks actually work. Eve
Re: Looking through a modulo operation
On Sun, Jul 20, 2008 at 04:14:33PM -0600, Matt Ball wrote: > >From a little bit of off-line discussion, I think I've got a restatement of > the problem that is more suitable to those with a stronger programming > background than mathematical background: > > "If someone uses the __random32 function as defined in the 2.6.26 Linux > kernel, and leaks to you the result of taking successive outputs modulo > 28233 (= 9 * 3137), can you determine the probable 96-bit internal state > with fewer than 1000 outputs and with modest processing power (e.g., a > laptop computer running less than a day)?" > > Here is a C implementation of __random32: > > typedef unsigned long u32; > struct rnd_state { u32 s1, s2, s3; }; > static u32 __random32(struct rnd_state *state) > { > #define TAUSWORTHE(s,a,b,c,d) ((s&c)<>b) > > state->s1 = TAUSWORTHE(state->s1, 13, 19, 4294967294UL, 12); > state->s2 = TAUSWORTHE(state->s2, 2, 25, 4294967288UL, 4); > state->s3 = TAUSWORTHE(state->s3, 3, 11, 4294967280UL, 17); > > return (state->s1 ^ state->s2 ^ state->s3); > } After any consecutive 96 outputs, the 97th is a fixed linear function of those just observed. It is not necessary to determine the internal state. The internal state is s_n = (A**n)(s_0) for a fixed 96x96 matrix A (the fact that it is a direct product of 3 32-bit matrices is not important). This matrix has a minimum polynomial of degree at most 96. A**96 = c_95 * A**95 + c_94 * A**94 ... + c_0 * I The 32-bit output then also satisfies: x_96 = c_95 * x_95 + c_94 * x_94 ... + c_0 for the same coefficients. -- /"\ ASCII RIBBON NOTICE: If received in error, \ / CAMPAIGN Victor Duchovni please destroy and notify X AGAINST IT Security, sender. Sender does not waive / \ HTML MAILMorgan Stanley confidentiality or privilege, and use is prohibited. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Looking through a modulo operation
On Sun, Jul 20, 2008 at 4:50 AM, Florian Weimer wrote: > I've got a function f : S -> X x S where S = (Z/2Z)**96 and > X = (Z/2Z)**32. Suppose that s_0 is fixed and (x_i, s_i) = f(s_{i-1}). > (f implements a PRNG. The s_i are subsequent internal states and the > x_i are results.) > > Now f happens to be linear. I know the values of x_i, x_{i+1}, ..., > x_{i+k} module N, for a fixed, known N. N is odd (but divisible by 9). > Is it possible to recover s_i with reasonable effort (better than brute > force, and k should be in the hundreds, not thousands)? And if yes, how? > Prediction of candidates for x_{i+k+1} with high probability would be > helpful, too. > > (Obviously, using f as an unpredictable PRNG is not a good idea. But if > there's a real attack I can present, convincing the authors to replace > it would be so much easier.) > >From a little bit of off-line discussion, I think I've got a restatement of the problem that is more suitable to those with a stronger programming background than mathematical background: "If someone uses the __random32 function as defined in the 2.6.26 Linux kernel, and leaks to you the result of taking successive outputs modulo 28233 (= 9 * 3137), can you determine the probable 96-bit internal state with fewer than 1000 outputs and with modest processing power (e.g., a laptop computer running less than a day)?" Here is a C implementation of __random32: typedef unsigned long u32; struct rnd_state { u32 s1, s2, s3; }; static u32 __random32(struct rnd_state *state) { #define TAUSWORTHE(s,a,b,c,d) ((s&c)<>b) state->s1 = TAUSWORTHE(state->s1, 13, 19, 4294967294UL, 12); state->s2 = TAUSWORTHE(state->s2, 2, 25, 4294967288UL, 4); state->s3 = TAUSWORTHE(state->s3, 3, 11, 4294967280UL, 17); return (state->s1 ^ state->s2 ^ state->s3); } __random32: See http://git.kernel.org/?p=linux/kernel/git/torvalds/linux-2.6.git;a=blob;f=lib/random32.c;h=ca87d86992bdb7bfd6bb30d4dbe6dcefe2bab7b9;hb=bce7f793daec3e65ec5c5705d2457b81fe7b5725 Cheers, -Matt -- Thanks! Matt Ball, IEEE P1619.x SISWG Chair M.V. Ball Technical Consulting, Inc. Phone: 303-469-2469, Cell: 303-717-2717 http://www.mvballtech.com http://www.linkedin.com/in/matthewvball - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Looking through a modulo operation
I've got a function f : S -> X x S where S = (Z/2Z)**96 and X = (Z/2Z)**32. Suppose that s_0 is fixed and (x_i, s_i) = f(s_{i-1}). (f implements a PRNG. The s_i are subsequent internal states and the x_i are results.) Now f happens to be linear. I know the values of x_i, x_{i+1}, ..., x_{i+k} module N, for a fixed, known N. N is odd (but divisible by 9). Is it possible to recover s_i with reasonable effort (better than brute force, and k should be in the hundreds, not thousands)? And if yes, how? Prediction of candidates for x_{i+k+1} with high probability would be helpful, too. (Obviously, using f as an unpredictable PRNG is not a good idea. But if there's a real attack I can present, convincing the authors to replace it would be so much easier.) - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]