Message-ID: <20131113060641.GA8043@ringworld.MIT.EDU>
Date:	Wed, 13 Nov 2013 01:06:41 -0500
From:	Greg Price <price@....EDU>
To:	"H. Peter Anvin" <hpa@...or.com>
Cc:	"Theodore Ts'o" <tytso@....edu>, linux-kernel@...r.kernel.org,
	Jiri Kosina <jkosina@...e.cz>
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.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Powered by blists - more mailing lists