[Cryptography] RNG design principles

John Denker jsd at av8n.com
Wed Nov 23 19:19:10 EST 2016


On 11/23/2016 07:55 AM, Salz, Rich wrote some stuff.....

I changed the Subject:, for the time-honored reason that we should
be discussing the ideas, not the person who put forth the ideas.

>> Everything that matters about randomness can be summarized in four bullet points:

No.  It's quite a bit more complicated than that.

> Is it a reasonable design point to use for OpenSSL's next CSPRNG?

No.

>> 1. You need two things: an entropy source, and a whitener. No entropy
>> source is perfect, so you need a whitener no matter what. 

As always, I don't want to argue about terminology.  If the terminology
isn't helping, we should choose different terminology.  That's a problem
here, because in this context the word "entropy" has been thrown around
so carelessly that it's a struggle to figure out what anybody means by
it.  That's sad, because in other contexts, e.g. in physics, there is an
agreed-upon, very precise, extraordinarily useful meaning.

Indeed in kernel sources and elsewhere, one can find the word thrown
around as an all-purpose synonym for randomness, applied to things that
have no positive lower bound on the actual entropy content, according
to any definition that makes sense to me.

What's worse is that (depending on what you're trying to accomplish)
the physics entropy was probably never what you wanted anyway.

	 *High entropy does not imply high unpredictability.*

Entropy is just one property of the distribution, and there are other
properties that (usually) matter more directly. The Rényi functionals
(Hα) come to mind, and H∞ in particular.  I call H∞ the /adamance/.  It
is possible to construct distributions where the physics entropy is
infinite, but the adamance is less than 2 bits.  I would not recommend
using such a distribution for crypto purposes.

Some people call the Rényi functionals a form of «generalized entropy»,
but if you do that, especially if you plan to use it as the basis for
future design work, that's a problem, because nobody will know what you
mean by it.

Again:  I don't want to argue about terminology, but even so, it's not
safe to use unexplained and oft-abused terms as the basis for future
design work.

>> You don't have to
>> do anything fancy in your whitener. Any cryptographically secure hash
>> function (like SHA512) will do.

That's a separate assertion.  It should be enumerated separately.

It's not quite correct.  We agree that the detailed innards of the
whitener don't matter, but the gross black-box properties (such as
word width) do matter somewhat.

>> 2. Since you need a whitener no matter what, it doesn't really matter how
>> good your entropy source is, except insofar as it might take a long time to
>> collect enough entropy from a very poor source. All that matters is that you
>> have an accurate lower bound for how much entropy your source actually
>> provides,

I agree with that in spirit.

>> and this is the case no matter how good (or bad) your source
>> actually is. As long as you feed >N bits of entropy into your whitener, you can
>> safely extract N bits of true randomness out of it.

Actually, not quite.  Whiteners aren't perfect either.  The laws of
statistics don't permit them to be.  To do things properly, you need
to feed slightly more than N bits in, to get N bits out.  Fortunately,
this is not much of a problem, because the excess is quite affordable,
especially when N is not very small.

This touches back to item (1), insofar as it depends on properties
of the whitener.

In any case, if we are going to write down a short list of pithy
commandments, and use them as the basis for future design work, we
ought to get the details right.

>> 3. You don't need more than a few hundred bits of randomness. 128 bits is
>> enough, 256 is a comfortable margin, 512 is serious overkill. Seed a
>> cryptographically secure PRNG with a few hundred bits of entropy and you
>> can safely extract gigabytes of key material out of it.

That's more-or-less kinda usually true, although once again I would
not promote it to the status of an axiom or commandment.

Again it touches back to item (1), insofar as if you are using SHA512,
then 512 bits of input is definitely not overkill.

More importantly, at some point, you have to address the re-seeding issue.

I'll let them speak for themselves, but there are people on this list
who would vehemently object to item (3).  They have spent years building
PRNGs that constantly re-seed themselves, to the point where the PRNG
becomes in effect a denial-of-service attack on the HRNG.

==============

There is also a metric truckload of issues that have not been mentioned
in this thread heretofore, including:

*) What to do with a newly-booted (or worse, newly-created) system that
 needs a RNG right away but has not had time to accumulate the adamance
 called for in item (1).

*) How to calibrate that this-or-that piece of hardware, so as to obtain
 the required lower bound on the amount of unpredictability it produces.

*) et cetera.



More information about the cryptography mailing list