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,

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

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

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

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

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

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}