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)<<d) ^ (((s <<a) ^ s)>>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 MAIL Morgan Stanley confidentiality or privilege, and use is prohibited. --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]