Looking through a modulo operation

[Victor Duchovni]

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 majordomo at metzdowd.com