[Cryptography] /dev/random is not robust

[Adam Back]

On Wed, Oct 16, 2013 at 10:12:14PM -0400, Theodore Ts'o wrote:
>In the Linux Pseudo Random Number Generator Revisited paper
>(http://eprint.iacr.org/2012/251.pdf), the authors sampled and
>analyzed the various real-life entropy sources, and found the entropy
>estimation to be pretty good, and if it erred, it erred on the side of
>convervatism, which is as designed.  

I think the more worrying case is a freshly imaged rack mount server,
immediately generating keys or outputting random numbers to the network or
in response to network queries.

The initial entropy is known (ie 0) and if what little entropy there is is
added in brute-forceable chunks, then an attaker able to observe or get
responses including RNG outputs over the network can keep in step with the
RNG state.  (Eg say 20-bits of entropy at a time, and needing 10-bits of
guessing to account for only seeing one in 1000 of the RNG outputs, then you
can for small cost of 2^32 per interval keep up.)

A similar issue could arise with a VM rollback (to a previous un-initialized
state, or repeating the same random outputs to different messages - eg
breaking DSA without the deterministic k=H(d,m) defense.

Yarrow, and the replacement Fortuna try to address this problem by
accumulating entropy and adding it in bigger lumps..

Adam