[Cryptography] [RNG] /dev/random initialisation

[Jerry Leichter]

On Oct 30, 2013, at 4:32 PM, "James A. Donald" <jamesd at echeque.com> wrote:
> No source of entropy can ever be harmful. The worst that can happen is that it is entirely predictable to the adversary, in which case it does little good, but can never do harm.

Are you so sure?

Consider a Linux-style RNG.  Suppose I know that all the existing sources produce k bits/second of randomness.  If I draw k bits/second of data out of it, after a while, it has no "spare" randomness inside - it's giving me exactly what it has.  If I draw j >> k bits/second out of it, it quickly "runs out".  It may block, effectively rate-limiting me; or it may stretch what it had.

Now suppose I inject j >> k bits of my own, controlled data, declaring that it represents j bits of entropy - all the while continuing to draw j bits out.  The generator now has plenty of entropy - or thinks it does - so never blocks.  But eventually it must be the case that I'm getting way more bits out than the real entropy going in.  If I can't predict the bits I'm getting out, it can only be because of the lingering entropy from the other sources.  (If j is much larger than k, then most of the bits I get out are computed without any bits other than my own going in.)

But this is an odd state of affairs.  If the assumption is that the results remain unpredictable, no matter how much larger j is than k, then why should the generator *ever* block because it's output more bits than it got in?  After all, that situation is effectively indistinguishable from it having gotten all 0 bits at some very high rate.

So:  For extra sources to always be harmless, it must be the case that the bits are unpredictable *even if no new entropy arrives*.  All that matters, in effect, is that the internal state be unknown and unpredictable *once*.  BBS has this property, as (on different assumptions) do crypto-based PRNG's like Yarrow.  But this has a performance cost, and I'm not sure that a Linux-style generator does.  If you have it ... why would you need to allow additional (allegedly random) sources?
                                                        -- Jerry