`On Tue, Nov 12, 2013 at 08:51:18PM -0800, H. Peter Anvin wrote:> On 11/12/2013 08:37 PM, Greg Price wrote:> > I'm thinking only of boot-time blocking.  The idea is that once> > /dev/urandom is seeded with, say, 128 bits of min-entropy in the> > absolute, information-theoretic sense, it can produce an infinite> > supply (or something like 2^128 bits, which amounts to the same thing)> > of bits that can't be distinguished from random, short of breaking or> > brute-forcing the crypto.  So once it's seeded, it's good forever.> > And, pray tell, how will you know that you have done that?> > Even the best entropy estimation algorithms are nothing but estimations,Indeed.  We do our best, but we can't be sure we have as much entropyas we think.The status quo here is that /dev/urandom will cheerfully answerrequests even when, by our own estimates, we only have a small amountof entropy and anything we return will be guessable.  What Ted and Iare discussing in this thread is to have it wait until, as best we canestimate, it has enough entropy to give an unpredictable answer.  Thestatus quo has the same effect as an arbitrarily too-optimisticestimate.The key point when it comes to the question of going *back* toblocking is that even if the estimates are bad and in reality theanswer is guessable, it won't get any *more* guessable in the future.If we think we have 128 bits of input min-entropy but we only have(say) 32, meaning some states we could be in are as likely as 2^(-32),then once an attacker sees a handful of bytes of output (*) they cancheck a guess at our input and predict all our other output with asfew as 2^32 guesses, depending on the distribution.  If the attackersees a gigabyte or a petabyte of output, they have exactly the sameability.  So there's no good reason to stop.On the other hand, because our estimates may be wrong it certainlymake sense to keep feeding new entropy into the pool.  Maybe a laterseeding will have enough real entropy to make us unpredictable fromthen on.  We could also use bigger and bigger reseeds, as a hedgeagainst our estimates being systematically too low in someenvironment.Does that make sense?  Do you have other ideas for guarding againstthe case where our estimates are low?Greg(*) Math note: the attacker morally needs only 32 bits.  They actuallyneed a little more than that, because some of the (at least) 2^32possible states probably correspond to the same first 32 bits ofoutput.  By standard probability bounds, for any given set of 2^32possible input states, if the generator is good then probably no morethan ln(2^32) = 22 or so of them correspond to the same first 32 bits.About 37 bits of output is enough to probably make all the outputsdifferent, and with even 64 bits = 8 bytes of output it becomesoverwhelmingly likely that all the outputs are different.  If thereare more than 2^32 possible states because the min-entropy is 32 butsome inputs are less likely, then the attacker needs even less outputto be able to confirm the most likely guesses.`