Re: Bug in random32.c: all-zero outputs with probability 1/2^32, other seeding bugs

Re: Bug in random32.c: all-zero outputs with probability 1/2^32, other seeding bugs

[Andrew Morton]

On Wed, 2 Jul 2008 01:19:27 +0200
Benoit Boissinot <bboissin@gmail.com> wrote:

> [who maintains random32.c ?]

ah.  I think it's ancient net code which was recently hoisted into lib/.
So: not really anybody.

I've been hopefully cc'ing Matt and Ted in the hope of fooling them
into looking at it.  But a netdev cc is appropriate also.

> On Thu, Jun 19, 2008 at 5:30 PM, Jack Lloyd <lloyd@randombit.net> wrote:
> > Hi,
> >
> > There appears to be an error in how random seeding is done in the
> > random32.c RNG. I am looking at 2.6.25.7.
> >
> [snip]
> >
> > An easy and straightforward fix for this that doesn't require changing
> > any interfaces is to add
> >  s &= 0xFFFFFFFF;
> > before the check in __set_random32, which ensures this condition will
> > be caught by the check. Alternately, you could replace the check for
> > s == 0 with some logic like:
> >  if((s & 0xFFFFFFFF) == 0)
> >     s += 1;
> > since just chopping the seed to 32 bits does throw away some of your
> > seed input (with sizeof(long) == 8, at least; doesn't make any
> > difference for sizeof(long) == 4)
> >
> 
> I think it is cleaner to change the interface to account for long != u32
> 
> The rest of your patch (ensuring values are big enough) looks valid to me.
> 
> Signed-off-by: Benoit Boissinot <benoit.boissinot@ens-lyon.org>
> 
> diff -r ced66ca0044f lib/random32.c
> --- a/lib/random32.c	Mon Jun 30 08:58:09 2008 -0700
> +++ b/lib/random32.c	Wed Jul 02 01:13:12 2008 +0200
> @@ -56,7 +56,7 @@
>  	return (state->s1 ^ state->s2 ^ state->s3);
>  }
> 
> -static void __set_random32(struct rnd_state *state, unsigned long s)
> +static void __set_random32(struct rnd_state *state, u32 s)
>  {
>  	if (s == 0)
>  		s = 1;      /* default seed is 1 */
> @@ -84,7 +84,7 @@
>   */
>  u32 random32(void)
>  {
> -	unsigned long r;
> +	u32 r;
>  	struct rnd_state *state = &get_cpu_var(net_rand_state);
>  	r = __random32(state);
>  	put_cpu_var(state);
> @@ -122,7 +122,7 @@
> 
>  	for_each_possible_cpu(i) {
>  		struct rnd_state *state = &per_cpu(net_rand_state,i);
> -		__set_random32(state, i + jiffies);
> +		__set_random32(state, (u32) i + jiffies);
>  	}
>  	return 0;
>  }
> @@ -135,7 +135,7 @@
>  static int __init random32_reseed(void)
>  {
>  	int i;
> -	unsigned long seed;
> +	u32 seed;
> 
>  	for_each_possible_cpu(i) {
>  		struct rnd_state *state = &per_cpu(net_rand_state,i);

Re: Bug in random32.c: all-zero outputs with probability 1/2^32, other seeding bugs

[Matt Mackall]

On Tue, 2008-07-01 at 17:34 -0700, Andrew Morton wrote:
> On Wed, 2 Jul 2008 01:19:27 +0200
> Benoit Boissinot <bboissin@gmail.com> wrote:
> 
> > [who maintains random32.c ?]
> 
> ah.  I think it's ancient net code which was recently hoisted into lib/.
> So: not really anybody.
> 
> I've been hopefully cc'ing Matt and Ted in the hope of fooling them
> into looking at it.  But a netdev cc is appropriate also.

I did look at it, and it looks reasonable. So:

Acked-by: Matt Mackall <mpm@selenic.com>

Stephen Hemminger is responsible for the original code, I believe. I've
been tempted to slurp this functionality into random.c but keep getting
side-tracked into theoretical investigations of better functions, as I'm
not a big fan of the current one from either a performance or strength
perspective.

-- 
Mathematics is the supreme nostalgia of our time.

Re: Bug in random32.c: all-zero outputs with probability 1/2^32, other seeding bugs

[Stephen Hemminger]

On Tue, 01 Jul 2008 22:22:31 -0500
Matt Mackall <mpm@selenic.com> wrote:

> 
> On Tue, 2008-07-01 at 17:34 -0700, Andrew Morton wrote:
> > On Wed, 2 Jul 2008 01:19:27 +0200
> > Benoit Boissinot <bboissin@gmail.com> wrote:
> > 
> > > [who maintains random32.c ?]
> > 
> > ah.  I think it's ancient net code which was recently hoisted into lib/.
> > So: not really anybody.
> > 
> > I've been hopefully cc'ing Matt and Ted in the hope of fooling them
> > into looking at it.  But a netdev cc is appropriate also.
> 
> I did look at it, and it looks reasonable. So:
> 
> Acked-by: Matt Mackall <mpm@selenic.com>
> 
> Stephen Hemminger is responsible for the original code, I believe. I've
> been tempted to slurp this functionality into random.c but keep getting
> side-tracked into theoretical investigations of better functions, as I'm
> not a big fan of the current one from either a performance or strength
> perspective.
> 

Yes, I took it from gnu scientific lib it for use in netem.  The seeding
fixes make sense.

Note: this should not be a security issue since this routine is explicitly
not intended for cryptographic use.