entropy depletion

[John Kelsey]

>From: "Steven M. Bellovin" <smb at cs.columbia.edu>
>Sent: Jan 11, 2005 10:58 AM
>To: cryptography at metzdowd.com
>Subject: Re: entropy depletion 

>Let me raise a different issue: a PRNG might be better *in practice* 
>because of higher assurance that it's actually working as designed at 
>any given time.

This is a good point.  In the ANSI X9.82 work we've been doing (working on a standard for random number generation for cryptography), we kind-of make a continuum:

PRNGs seeded once --> PRNGs with live entropy sources --> full entropy PRNGs 

The idea here is that you can use a PRNG algorithm in a mode where it's seeded once at the factory and runs forever, or where it has access to an entropy source but has to produce output bits faster than the entropy source can, or where it produces outputs that include as many bits of entropy as bits of output.  Any good PRNG algorithm can be run in all three of these modes, with a bit of thought.  (We have our own terminology for all this in X9.82; we call a PRNG a "DRBG" and a random bit generator producing full entropy an "NRBG".)  

We also distinguish among full-entropy RNGs that include a strong PRNG and those that are pure hardware based.  When you're running the PRNG in a full-entropy mode (we give constructions for this) you get a guaranteed fallback to a secure PRNG even if your entropy source fails.  If you're using a pure hardware-based RNG and the hardware fails, you're out of luck.  

>To me, the interesting question about, say, Yarrow is not how well it 
>mixes in entropy, but how well it performs when there's essentially no 
>new entropy added.  Clearly, we need something to see a PRNG, but what 
>are the guarantees we have against what sorts of threats if there are 
>never any new true-random inputs?  

If there's really no entropy ever entered, then no PRNG algorithm can help you.  If we ever get to an unguessable state, then Yarrow should (barring some clever cryptanalysis) stay in a secure state for as long as we need to use it.  The tricky bits seem to happen in the middle--when the entropy trickles in at a slower rate than expected.  That's what Yarrow's two pool reseeding strategy is for, and what Niels Ferguson's Fortuna design does in a pretty-close-to-optimal way.  I think these strategies are interesting, but as I've worked on X9.82, I have become a lot more concerned with getting the PRNG to a secure starting point than with recovering later.  Recovering is important, too, but a lot of real-world systems use their first PRNG state to generate their high-value signing key, or the session key used to communicate their high-value secrets to some server, or whatever.    

>		--Prof. Steven M. Bellovin, http://www.cs.columbia.edu/~smb

--John Kelsey

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com