[Cryptography] randomness +- entropy

Jerry Leichter leichter at lrw.com
Tue Nov 12 16:24:40 EST 2013


On Nov 11, 2013, at 2:07 PM, John Kelsey <crypto.jmk at gmail.com> wrote:
> 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.    
This is why the continuous reseeding model is so insidious, and so difficult to understand.

For a CSPRNG with k bits of internal state, I would say there are two possible modes:

1.  Uninitialized.  The k bits have not yet been set to values chosen from a large enough set of possibilities.  (In general, we assume they ultimately get chosen uniformly at random from the set of all possible k-bit strings.  If you really want to consider the general case, the internal state might not be a k-bit string - it could be a value mod some large N, for example.  But this doesn't change anything fundamental.)  Once state has been set of k "unpredictable" bits, we transition to mode 2.
2.  Initialized, safe.  Those k bits have been set, and we assume an attacker has no knowledge of their values.

In mode 1, it's *impossible* to deliver useful outputs.  Any games that say things like "oh, I have k/2 bits in my internal state properly initialized so I'll only deliver k/4 bits of output and that should be safe" are just making things up as they go along.  Maybe one can design a system in which this is safe, but I haven't seen one yet.  A proper design *must not* deliver any outputs when it's in mode 1.

When a properly designed generator is in mode 2, it can deliver some reasonable fraction of 2^k output bits before its internal state is *computationally* no longer safe.  *You can't use an entropy measurement here!*  Entropy is concerned with absolute security:  Can an opponent with unbounded computation power determine the state.  It is almost certainly the case that once you've output k generated bits, the internal state is uniquely determined.  An unbounded Turing machine can simply enumerate all 2^k possible starting state values and see which produces the k outputs actually seen.  It will almost always find that there is exactly one starting state.  (If there are a couple, a few more outputs will certainly determine the starting state.  This is just a counting argument.)  From the point of view of entropy, every bit of output reduces the internal entropy by one bit.  What a CSPRNG guarantees (modulo assumptions about the crypto primitives used) is that no *polynomially bounded* (probabilistic) TM can gain any significant advantage over guessing the next bit, or working backwards to previous states.  If the primitives used are exactly the ones you're going to use elsewhere in the system, then you have exactly as much reason to trust them there as you do to trust them within the CSPRNG.

After some fraction of 2^k outputs, a CSPRNG *must* move back to mode 1 and somehow get another k bits of "unknowable" state - regardless of any possible compromise.  In the event of a possible compromise of the state, the generator must also transition back to mode 1.

But ... how can we know if a compromise was possible?  Continuously reseeding generators just start with the assumption that a compromise of the internal state *could* occur at any time.  If compromises an occur as fast as the CSPRNG can produce outputs, then it's not contributing anything:  It will have to fully re-seed between every two successive output bits, so it's just burning through the random bits used to seed it k bits at a time.  Better to simply output the true random bits as they arrive!  The obvious *safe* way to do this is to wait for k good random bits to accumulate, then replace the entire state of the CSPRNG, completely eliminating any previous knowledge an adversary might have had.  What's dangerous - and you've illustrated the problem - is to add a few bits of "good randomness" into a compromised state.  I don't see any way to avoid this problem.  (In the paper about the security of the Linux generator that Theodore Tso forwarded a link to earlier, there's a result showing that its pool combination and stirring is a "mixing function", in the sense that the result has at least much entropy as either of the inputs.  But that doesn't help in the case of a state compromise, since in that case the entropy of the internal state is 0.)

How often should we reseed?  There's no certain way to know without knowing how a state compromise might occur.  You'd like to reseed at an interval short enough that a compromise during that interval is "unlikely enough".

If you assume that there is no correlation between how fast bits are drawn from the CSPRNG and how likely a compromise is at any point in time, there are simple relationships that let you say something like:  Assuming can generate r true random bits/second, the chance of a state compromise is one every c seconds, and the total demand on the CSPRNG is d bits/second, and I've drawn n bits, the chance that m of them were compromised is no more than p.  If I can't increase r, I can make p lower by limiting d (by blocking if the demand rate is too high).

This suggests a very simple design:  There's a CSPRNG with k bits of internal state that's the source of random numbers for virtually all purposes.  There's a source of "true random" bits.  The CSPRNG blocks until it receives (either from the "true random" generator or from a previously-saved and assumed to be uncompromised) k seed bits; then it delivers those bits freely, with a possible rate cap to limit d as suggested above.  In parallel, we continue to gather bits from the true random generator; when we have k of them, we completely replace all k seed bits.

As far as I can see, this is (a) as safe as possible within constraints you can manipulate as you like (k, d, r, p); (b) simple, hence "obviously correct".  It's perfectly OK to allow access to the "true random number generator" so long as you reserve the assumed r bits/second for the CSPRNG, which almost everyone should be using.

What advantages do other approaches offer?  ("Not blocking" in favor of returning values that may not be safe is not a good option.  Except for initial startup, you can manipulate what you think is safe well enough, rather than just going by a hope and a prayer.  There's simply nothing you can to at startup if you don't have sufficient true random bits to get started, and you're not doing anyone a favor by trying.
                                                        -- Jerry



More information about the cryptography mailing list