Re: Looking through a modulo operation

2008-07-23 Thread lists
Matt Ball matt.ball ieee.org 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) ((sc)d) ^ (((s a) ^ s)b) state-s1 = TAUSWORTHE(state-s1, 13,

Re: Looking through a modulo operation

2008-07-22 Thread Matt Ball
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

Re: Looking through a modulo operation

2008-07-22 Thread David Wagner
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

Re: Looking through a modulo operation

2008-07-21 Thread 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

Re: Looking through a modulo operation

2008-07-21 Thread David Wagner
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

Re: Looking through a modulo operation

2008-07-21 Thread Victor Duchovni
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

Looking through a modulo operation

2008-07-20 Thread Florian Weimer
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}