Re: RND_TYPE_RNG question concerning rate of random bits production

["Perry E. Metzger" <perry%piermont.com@localhost>]

On Sat, 18 Jan 2014 13:44:21 -0500 Thor Lancelot Simon
<tls%panix.com@localhost> wrote:
> On Sat, Jan 18, 2014 at 01:10:19PM -0500, Perry E. Metzger wrote:
> > On Wed, 15 Jan 2014 20:28:17 -0500 Thor Lancelot Simon
> > > 
> > > You can arrange to be polled for entropy when it's needed.
> > > Have a look at the hifn, amdpm, or bcm2835 RNG drivers.
> > 
> > Note that there has been recent work on formal analysis of CPRNGs
> > like the ones used by various Unix kernels. They tend to indicate
> > that proper entropy estimation is not as important as rendering
> > the generator robust against bad entropy estimates. See, for
> > example:
> > 
> > http://www.cs.nyu.edu/~dodis/ps/rng.pdf
> 
> The NetBSD RNG machinery goes to considerable effort to do what it
> recommended by that and other related papers, and in some cases
> more.

The paper presents a proof of a particular construction which is not
the same as the construction currently in use, which does not
have a similar proof. (I'm unaware of other constructions with proofs
under similar dual adversary models.)

BTW, I'm not familiar with any more recent related papers, and I
heard an overview talk on the area on Tuesday at a conference on such
topics so I'm pretty sure I would have heard some mention of it.

> As for everyone else, the real problem is acquiring initial entropy
> at boot -- and knowing that you've acquired it.

Partially. The other problem is preventing good entropy from being
overwhelmed by bad. The paper assumes an adversarial model in which
one tries to make sure that it is okay if a bad guy injects arbitrary
amounts of state into the system from a bad source.

So long as enough good entropy is already in the system, it will not
be overwhelmed by the bad. This makes entropy estimation less
necessary or important, since once one has crossed the line it will
no longer be possible for a second adversary under a bounded
computation model to predict subsequent output. (Note that if you can
protect against an adversary controlling one of your entropy sources,
problems like unintentional failure or misestimation of entropy are
automatically covered -- it is the most robust model for a proof.)

The paper demonstrates that some constructions do not have this
robustness against adversarial models for entropy sources, which
makes it harder to live in a world where entropy estimation is in
practice largely a matter of guessing.

Getting enough entropy at boot time is of course a serious problem
and I don't mean to belittle that. It is a major source of attack
these days, and the construction in question will not fix that as
such.

Perry
-- 
Perry E. Metzger                perry%piermont.com@localhost