PRNG design document?

[John S. Denker]

On 08/29/2003 03:43 PM, Tim Dierks wrote:

 > Allow me to clarify my problem a little. I'm commonly engaged to
 > review source code for a security audit, some such programs include a
 > random number generator, many of which are of ad-hoc design. The
 > nature of such audits is that it's much more appealing to be able to
 > say "here are three accepted guidelines that your generator violates"
 > rather than "I haven't seen that before and I don't like it, you
 > should replace it with something else".

That's a very helpful clarification.

 > So I'm interested in such design guidelines, if they're available,
 > which such a generator could be tested against. While the resources
 > provided have been useful, it's only led me to where I was: that the
 > only way to do so is to attempt to analyze the system for
 > vulnerability to a collection of known flaws.

That dissatisfaction is wise. Checking for
known flaws is far from sufficient. It is
possible to do much better.

 > I know a bunch of basic, obvious things that I can state (have a
 > large enough internal state, generate output with a secure hash,
 > etc.) and a bunch of other fuzzier notions that are harder to
 > concretize (output should be dependent on a sufficient quantity of
 > the internal pool, reseeding should affect a sufficent quantity of
 > the internal pool, etc.). But I don't have a resource which attempts
 > to canonically define minimal requirements for all these elements.
 > (If I have missed such a list in skimming the broad resources
 > available, I'd appreciate a note.)

First, as is so common in this business, a lot
depends on the threat model.

-- If some scientist is doing Monte Carlo integrations,
almost anything will be "random enough". I recommend
using a long-period counter feeding MD5; that is
sufficiently random and sufficiently efficient that
it's probably not worth considering alternatives.

-- At the other extreme, for some high-stakes
adversarial applications, such a nationwide lottery
or military crypto, *none* of the fuzzy concepts
mentioned above come anywhere near being sufficient.

Also keep in mind that many of the biggest threats
against a PRNG do not attack the algorithm itself,
but rather attack the *seed*. The state must be
initialized (which is hard) and protected forever
after (which is hard).

I know the Subject: of this thread mentions PRNG, but
I would not use a pseudo-random number generator for
any high-stakes adversarial application.

In particular, if anybody cares enough to hire you,
asking you whether the PRNG is good enough, the
answer almost certainly is no.

Also note that I have made it very easy to use a
hardware random number generator. For any high-stakes
adversarial situation, I strongly recommend using
that.

For details, see
   http://www.av8n.com/turbid/

If you want some "principles" that are "violated"
by typical RNGs, start with this:  the RNG needs
to come with a proof of correctness. In particular,
this should include some sort of guaranteed lower
bound on the entropy density of the generated symbols.
In the case of any RNG with persisent state, there
should be a proof that the seed is random and the
state remains secure for all time.

That's not a complete list of principles, but it
should suffice to disqualify most of the junk
that is out there.


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com