Messages in this thread |  | | Date | Wed, 13 Nov 2013 01:06:41 -0500 | From | Greg Price <> | Subject | Re: [PATCH 00/11] random: code cleanups |
| |
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 entropy as we think.
The status quo here is that /dev/urandom will cheerfully answer requests even when, by our own estimates, we only have a small amount of entropy and anything we return will be guessable. What Ted and I are discussing in this thread is to have it wait until, as best we can estimate, it has enough entropy to give an unpredictable answer. The status quo has the same effect as an arbitrarily too-optimistic estimate.
The key point when it comes to the question of going *back* to blocking is that even if the estimates are bad and in reality the answer 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 can check a guess at our input and predict all our other output with as few as 2^32 guesses, depending on the distribution. If the attacker sees a gigabyte or a petabyte of output, they have exactly the same ability. So there's no good reason to stop.
On the other hand, because our estimates may be wrong it certainly make sense to keep feeding new entropy into the pool. Maybe a later seeding will have enough real entropy to make us unpredictable from then on. We could also use bigger and bigger reseeds, as a hedge against our estimates being systematically too low in some environment.
Does that make sense? Do you have other ideas for guarding against the case where our estimates are low?
Greg
(*) Math note: the attacker morally needs only 32 bits. They actually need a little more than that, because some of the (at least) 2^32 possible states probably correspond to the same first 32 bits of output. By standard probability bounds, for any given set of 2^32 possible input states, if the generator is good then probably no more than 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 outputs different, and with even 64 bits = 8 bytes of output it becomes overwhelmingly likely that all the outputs are different. If there are more than 2^32 possible states because the min-entropy is 32 but some inputs are less likely, then the attacker needs even less output to be able to confirm the most likely guesses.
|  |