[Cryptography] randomness +- entropy

[John Kelsey]

On Nov 10, 2013, at 4:48 AM, Yaron Sheffer <yaronf.ietf at gmail.com> wrote:

> My original comment was not a general statement about consuming bits from the PRNG. I said that consuming PRNG bits *before the PRNG is fully seeded* is a double problem:
> 
> - The consumer gets low-quality randomness.
> - The *next* consumer's entropy is lower, because the first consumer might broadcast the randomness he had just received.

If we're talking about a PRNG (which /dev/urandom is), then there are really two cases of interest:

a.  The PRNG has accumulated too little entropy[1] to be in a secure state.  

b.  The PRNG has accumulated enough entropy to be in a secure state--say 128 or more bits.

In case (b), if the PRNG is secure, there can be no harm in anyone seeing lots of outputs from it. Initializing your PRNG with 200 bits of entropy and then outputting a million bits leaves you perfectly fine in security terms.  

In case (a), you have a big problem.  If your PRNG has accumulated 37 bits of entropy and you generate an output, you've lost all 37 bits of entropy, because I can guess the PRNG's state, and if my guess is right, I will be able to predict the outputs correctly.  This sets up the situation where you do something like

Feed in 50 bits of entropy
Generate an output
Feed in another 50 bits of entropy
Generate another output
Feed in another 50 bits of entropy
Generate another output
...

And you never get to a secure state, even though you've fed in 150 bits of entropy.  This is why Yarrow does catastrophic reseeding.  

[1] I use "entropy" here in the sense of information not known to any attacker, not in the sense of fundamentally unknowable information like how many nuclei decayed in a given period of time.  Also, if you're computing the entropy, the right measure to use is min-entropy, not Shannon entropy.  That's -lg( P[max] ) where P[max] is the maximum probability of any possible input to the PRNG.    

> Thanks,
>    Yaron

--John