[Cryptography] [RNG] /dev/random initialisation

[Peter Todd]

On Wed, Oct 30, 2013 at 05:00:33PM -0400, Jerry Leichter wrote:
> 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?

This is why the Linux RNG allows anyone to add data to the pool as an
unprivileged operation, but requires root to change the estimates of how
much entropy is in the pool.

Try it: cat /dev/zero > /dev/random

-- 
'peter'[:-1]@petertodd.org
0000000000000005fc0cffa2f1c60362ad998d2a6dd92ab69c34235a0e0b064f
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 685 bytes
Desc: Digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20131030/9a8e36f9/attachment.pgp>