Re: monitoring entropy
Malcolm Beattie (mbeattie@sable.ox.ac.uk)
Wed, 15 Oct 1997 16:14:56 +0100 (BST)
Ingo Molnar writes:
>
> On Tue, 14 Oct 1997, Colin Plumb wrote:
>
> > Well, it depends on what you mean by "freeze the pool". If you mean
> > somehow make all writes to the memory silently fail, then you're right,
> > you'll get constant output from /dev/random. But every time you read
> > from /dev/random, it adds the current time to the pool, hashes the pool
> > to produce some output, adds the outpuyt back into the pool, and
> > returns half of the hash output. (Repeat as often as necessary to fill the
> > number of bytes requested in the read.) Thus, reading alters the pool.
> > The expected cycle length is something on the order of 2^2048, so
> > the "periodic" part isn't a big concern.
>
> if by 'current time' you mean the cycle counter, the value of it is pretty
> much predictable. It adds no real entropy to the pool. Thus you over and
> over again sample the pool, thus you will be able to follow it's state
> more or less reliably.
>
> the basic problem is that attackers are allowed to sample the pool at
> unlimited speed. Provided that even a mediocre P5 can handle thousands of
> read() requests per second, the information 'flux' should not be
> underestimated.
>
> This is just like those timing based DES attacks (delta-attacks), even
> (limited!) timing information gives away too much of internal state. Such
> unlimited output IMO basically gives away the whole internal pool.
>
> > Not at all. First of all, notice what I said... just reading the pool is
> > completely *harmless* unless you *do* something with the data that is read.
>
> oh yes, an attacker does.
>
> > All that someone can do is gather information to help them predict the
> > future output, i.e. to guess what it's going to be. You have to read
> > /dev/urandom and then put in a lot of hard thinking.
>
> it's not 'reading once an MD5 hash'. It's 'reading it unlimited times'. Do
> you consider this safe, especially as victims use the very same interface
> to get 'random data' as well?
As I understand it, the difference between data coming from /dev/random
and /dev/urandom is analogous to the difference between (1) generating
initial PGP keys one after another, each with perfect randomness and (2)
generating a cryptographically strongly random stream of numbers from a
random initialisation vector by repeatedly applying a cryptographic hash.
The second is roughly how PGP encrypts an actual message: by taking a
random initialisation vector and using IDEA as a hash (you could just as
well use MD5, crypt(3) or suchlike, modulo their "crackability") to
generate a stream of bits which are then XOR'd with the plaintext.
Looking at it in these terms, reading /dev/random corresponds to reading
the contents of a one-time pad; reading /dev/urandom corresponds to
reading bytes from a cryptographically strongly random stream of data
with an unknown initialisation vector. Deducing information about that
stream of data (for example, predicting future bits) depends on
attacking the security of the crypto hash algorithm used to generate
that stream. The Linux /dev/urandom uses MD5 as its crypto hash so
predicting future bits from /dev/urandom is about as hard as breaking MD5.
More precisely, breaking MD5 would probably let you predict future bits
from /dev/urandom but there might be a different attack which would let
you predict future bits without being able to produce MD5 collisions.
Nevertheless, an attack on using MD5 in this way as a random number
generator would be worthy of publication and gain an awful lot of
world-wide interest and surprise many in the crypto field. *That's*
what Colin means by "hard".
--Malcolm
--
Malcolm Beattie <mbeattie@sable.ox.ac.uk>
Unix Systems Programmer
Oxford University Computing Services