[PYTHON-CRYPTO] CSPRNG schemes : Any comments?

[Andrew Archibald]

On Thu, Feb 15, 2001 at 11:37:56PM -0500, Bryan Mongeau wrote:
> > Hmm.  Well, here's another terminological quibble:  the literature in
> > general seems to use "cryptographically strong pseudo-random number
> > generator" to mean a deterministic process which produces numbers which are
> > computationally infeasible to distinguish from randomness without knowing
> > the seed data.  (See Schneier's Applied Cryptography, p. 45, for example).
> >
> > On the other hand, (drawing from the same source) a real random number
> > generator is one which produces genuinely unpredictable output, no matter
> > how much computational power is brought to bear.  Most sources are not
> > acutally completely random (disk timings) but do contain a few bits of
> > genuine unpredictability.
>
> Ah, well in a perfect world, every motherboard would come with a builtin
> hardware RNG and this whole issue would become academic. :)

IIRC, they do (the Intel i810 random number generator; the Linux kernel has
a driver).  Nobody trusts them, Intel, you know...

>                                                              As for CSPRNG
> schemes, aren't we all striving towards the same goal of unpredictability? I
> would merely like to show that predicting the outcome of race conditions is
> harder than predicting other traditional entropy sources (keyboard, ps aux,
> etc.)

Hmm.  No, it's an important distinction between two very different goals:
information-theoretic unpredictability and computational unpredicatbility.
To get the first, you really need all these weird hacks that talk to
hardware, and you need some way of knowing how random they are.  Look at
yarrow, perhaps as implemented in pisces.
(http://www.cnri.reston.va.us/software/pisces/manual/module-pisces.yarrow.html)

To get the second goal, you should use some well-understood bit-maching
scheme such as a stream cipher or block cipher in OFB mode.  You need to
feed it real randomness at regular intervals, just like you need to re-key
connections at regular intervals; for this you need real randomness.  You
might as well let the real randomness collect in a hash context (as yarrow
does).

> > To get an unpredictable random number generator, you should use a CSPRNG
> > (using Schneier's terminology) and seed it with a genuine random number
> > generator.  And re-seed it, periodically, at controlled intervals and in
> > controlled amounts.
>
> Hmmm, if I had a real RNG at my disposal, I wouldn't bother feeding a CSPRNG.
> These crypto cards can crank out a crapload of numbers by measuring
> electrical noise, why the overhead of a CSPRNG?

Most real RNGs (lavarand, disk seek latency, keyboard intervals, etc.)
provide far too few random bits to use straight except for the most
demanding applications.  So you would be feeding them into a CSPRNG anyway.
If all you want is a CSPRNG, run AES in OFB mode.

> This is an issue I am currently struggling with. Do you know of any resources
> for entropy estimation routines and guidelines? Everything I have seen just
> takes guesses.

That is because it is really hard to know how predictable a source is.  It
is easier (almost to the point of being doable) if the source is
well-understood (e.g., keyboard latencies, disk seek times, analog input
to a high-fidelity sound card); then you can use your own estimate of how
much entropy there should be, and weight it down using an automatic entropy
estimator that looks for patterns.  Look in pisces, for example, they have
one based on zlib.  These help a little, but you really need to know how
much unpredictability you can hope for in your application.  Network
timings, for example: dare you trust them?  Who knows whether the adversary
can mess with your network timings?  Only your application writer can tell
for sure.

Andrew