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]
