Re: [PATCH 4/5] tsc: wire up entropy generation function

[Matt Mackall <mpm@selenic.com>]

On Mon, 2011-06-13 at 15:36 -0700, H. Peter Anvin wrote:
> On 06/13/2011 03:27 PM, Venkatesh Pallipadi wrote:
> > On Mon, Jun 13, 2011 at 3:06 PM, Jarod Wilson <jarod@redhat.com> wrote:
> >> TSC is high enough resolution that we can use its low-order byte to
> >> stir new data into the random number generator entropy pool.
> > 
> > From what I vaguely remember from years past, rdtsc, especially last
> > few bits of it are not very good as random number source. As they are
> > based on lower bus frequency and a multiplier. May be things have
> > changed these days. Adding Peter and Suresh for comments.

Well the issue is that samples are going to be roughly aligned to some
multiple of the bus frequency. If an interrupt occurs on bus cycle X,
this code will be hit at roughly TSC cycle X*M+d.

> This is correct; at the very least I would multiply the low 32 bits of
> the TSC with a 32-bit prime number before mixing.

This multiply doesn't actually accomplish anything. Mixing known values
into the pool is harmless because the mixing function is fully
reversable. ie:

 unmix(sample, mix(sample, pool)) = pool

If you didn't know the contents of pool before, you can't guess it
after.

The danger comes if you (a) already know pool and (b) can narrow sample
to a tractable set of values. Then you can calculate a set of possible
pool' values and compare the resulting output to confirm the actual
state of pool' (aka state extension attack). Sticking a constant
multiplier on sample doesn't affect this attack at all.

> However, the big issue with this is that it's recursive... what causes
> this to be invoked... probably an interrupt, which is going to have been
> invoked by a timer, quite possible the TSC deadline timer.  Oops.

..and the sampling function already mixes in a TSC timestamp with the
provided timestamp.

-- 
Mathematics is the supreme nostalgia of our time.