[Discuss] How do I add entropy?

[blu at nedharvey.com (Edward Ned Harvey (blu))]

> From: Kent Borg [mailto:kentborg at borg.org]
> 
> Logically, if the crypto is good, entropy accounting should not matter,

That's not true.  Take for example, Fortuna.  Bruce Schneier says (I paraphrase because I don't have the book in front of me right now) "The way we eliminate problems with entropy estimation is to eliminate entropy estimation."  He goes on to say Fortuna is an AES block cipher mode prng, and describes the size of the initial key, and how often it needs to be rekeyed.  This would tend to suggest agreement with your statement - that entropy accounting doesn't matter - But he doesn't say anything about where the initial key material, or the re-key material comes from, or how to estimate that you've got sufficient entropy in your key material.  (Kind of a glaring oversight).

Just imagine if ThreadedSeedGenerator was being used as the seed for Fortuna.  Then it would be completely broken.  In fact, ThreadedSeedGenerator *was* being used as the seed for bouncy castle SecureRandom.  And it *was* completely broken, despite the fact that it's a good PRNG like Fortuna (but different).

Additionally, unless you define "crypto is good" to mean nothing has ever been penetrated and everything remains ideal, you have to think about prng robustness, including the ability to recover to a good state after the internal state has been compromised.  Suppose at some point, some or all of the PRNG internal state is compromised, and you continually feed entropy into it, one byte at a time.  Then it's easy for the adversary to continually adapt and follow state, because it's only 256 guesses max (128 typically) at each new entropy junction.  In order to be robust, you have to add entropy to your internal state in fairly large chunks - say 128 bits at a time or higher.  Just in case some or all of your internal state has been compromised, this is necessary to shake off the adversary.  And naturally, this requires at *least* lower-bound entropy accounting, even for a good PRNG.

So how could you aggregate a whole bunch of weak entropy sources to generate one good key for a PRNG?  You would probably have a cyclic buffer, or a buffer with a mixing function of some kind, and you'll aggregate bits for a long time until you figure "I've got at *least* 32 bytes of entropy in there now" and then you hash the buffer to extract a key from it.  Sound familiar?  Like the linux entropy pool?    ;-)   I cannot say of course, first-hand, this is what MS does or anybody else, but it's extremely likely that they're doing something very similar to generate the key for Fortuna or whatever PRNG.

So for all the above, you may not need strict entropy accounting, but you need strict lower bound entropy accounting to ensure you are feeding strong key material into your PRNG.  It's inescapable even for good PRNG's.


> I think it is reasonable for the Linux kernel to have an RNG, but the
> kernel will never define a large enough boundary to really know its
> entropy sources.

True dat.  I was surprised that in order for dieharder to statistically measure randomness characteristics to a confidence level of 2^-256, it requires TB's worth of data, which means the PRNG cranks out bytes as fast as all the CPU's in the system can run, for hours on end.  There is absolutely no way you'll ever collect this much entropy in your kernel (linux or anything else) in order to prove the entropy source is statistically random.


> Being strict about entropy sources logically reduces to
> removing Linux's hybrid entropy-pool/cryptographic RNG altogether.

No it doesn't.  Same as Fortuna and SecureRandom and everything else - linux's random is just an entropy gathering engine connected to a prng.  They all require an entropy gathering pool, and they all must estimate at least a lower bound on available entropy (even if they say they don't), and whack the prng with entropy material occasionally.


> Anyone who is marching down that logical path is the wrong person to
> maintain random.c.

Quite a conclusion to jump to, having not listened to his explanations or justifications.  As you might have gathered from me writing this message and other messages, there are at *least* plausible explanations which are extremely valid and relevant to having better security.