Re: [PATCH 2/6] random: use xor for mixing

[Theodore Tso <tytso@mit.edu>]

On Sat, Dec 08, 2007 at 05:20:16PM -0600, Matt Mackall wrote:
> random: use xor for mixing
> 
> With direct assignment, we can determine the twist table element used
> for mixing (the high 3 bits of the table are unique) and reverse a
> single step of mixing. Instead, use xor, which should also help
> preserve entropy in a given pool slot.
> 
> Signed-off-by: Matt Mackall <mpm@selenic.com>
> 
> diff -r bc336762cfdb drivers/char/random.c
> --- a/drivers/char/random.c	Wed Dec 05 17:20:02 2007 -0600
> +++ b/drivers/char/random.c	Sat Dec 08 13:27:34 2007 -0600
> @@ -496,7 +496,7 @@ static void __add_entropy_words(struct e
>  		w ^= r->pool[(i + tap4) & wordmask];
>  		w ^= r->pool[(i + tap5) & wordmask];
>  		w ^= r->pool[i];
> -		r->pool[i] = (w >> 3) ^ twist_table[w & 7];
> +		r->pool[i] ^= (w >> 3) ^ twist_table[w & 7];
>  	}

In the original design of add_entropy_words(), in order to provably
not lose any entropy, you want add_entropy_words() to be reversible if
you mix in all zero's.  So the fact that you can determine the twist
table element used from looking at the high bits was deliberate.  The
mixing done in add_entropy_words() is *not* intended to be
cryptographic, but merely to smear the bits around as they are added
and then to permute the pool so that when you use SHA in the output
stage, enough bits are changing that even if there are weaknesses
discovered in the crypto hash algorithm, it won't help the attacker.

The internals of the pool are never exposed, so an attacker should
never gain direct access to the entropy pool; hence worry about
whether someone can "reverse" the mixing isn't particuarly a worry;
indeed, in order to make sure we preserve entropy, the whole *point*
of the mixing algorithm is that it is reversible.

(note: credit for this design should go to Colin Plumb, who worked
with me on this aspect of the design.  Colin was responsible for the
original random number generator in PGP....)

					- Ted