* PRNG Design Document

A good PRNG is necessary for secure crypto, and is in many ways a single point
of failure. I feel the code implementing Botan's RNGs (Randpool and ANSI X9.32)
is pretty clear, so it should be fairly easy to understand the algorithms
directly. Just in case additional explanation is desired, I wrote this.

* Randpool

Randpool has an internal state called pool, which is 512 bytes long. This is
where entropy is mixed into and extracted from. There is also a small output
buffer (called buffer). It is based around a MAC and a block cipher (which are
currently HMAC(SHA-256) and AES-256). Where a specific size is mentioned, it
should be taken as a multiple of the cipher's block size. For example, if a
256-bit block cipher were used instead of AES, all of the sizes internally
would double.

Every time some new output is needed, we compute the MAC of a counter and a
high resolution timer. The resulting MAC is XORed into the output buffer
(wrapping as needed), and the output buffer is then encrypted with AES,
producing 16 bytes of output.

After 8 blocks (or 128 bytes) have been produced, we mix the pool. To do this,
we first rekey both the MAC and the cipher; the new MAC key is the MAC of the
current pool under the old MAC key, while the new cipher key is the MAC of the
current pool under the just-chosen MAC key. We then encrypt the entire pool in
CBC mode, using the current (unused) output buffer as the IV. We then generate
a new output buffer, using the mechanism described in the previous paragraph.

To add randomness to the PRNG, we compute the MAC of the input and XOR the
output into the start of the pool. Then we remix the pool and produce a new
output buffer. The initial MAC operation should make it very hard for chosen
inputs to harm the security of Randpool, and as HMAC should be able to hold
roughly 256 bits of state, it is unlikely that we are wasting much input
entropy (or, if we are, it doesn't matter, because we have a very abundant
supply).

* X9.32 RNG

This is the standard issue X9.32 Appendix A PRNG, though using AES-256 instead
of 3DES (since using AES instead of 3DES in this PRNG is allowed by FIPS
140-2). This PRNG implementation has been checked against official X9.32 test
vectors.

Internally, the PRNG holds a pointer to another PRNG (typically Randpool). This
internal PRNG generates the key and seed used by the X9.32 algorithm, as well
as the date/time vectors. Each time entropy is added to the X9.32 PRNG, this is
mixed in with the internal PRNG, and then a new key and seed are
generated. This PRNG considers itself seeded as soon as the internal PRNG is
seeded.

As of version 1.4.7, the X9.32 PRNG is by default used for all random number
generation.

* Entropy Estimation

The entropy estimation techniques used are not terribly clever. The estimation
is done in the function entropy_estimate in src/util.cpp

Essentially, if the input is less than 5 bytes long, we say that the input had
no entropy. This is just to simplify the rest of the code, since the algorithm
assumes it has a sequence of bytes to work on. Typically the inputs are 64-256
bytes long, so this isn't a problem.

The entropy is estimated using first, second, and third level deltas, with a
difference metric of XOR. The entropy of the byte is estimated to be the
Hamming weight of the smallest of the three deltas. The sum of each byte's
entropy is taken to be the entropy estimate. We then return (estimate/2), so we
are (hopefully) underestimating the actual entropy. This lowered entropy
estimate means that often a single slow poll (from a single entropy source)
will not collect enough entropy to fully seed the PRNG. This was done
intentionally so that multiple polls (hopefully from multiple sources) will
always been done. The exception is if /dev/urandom is available, as often a
single poll from it is sufficient to seed the PRNG. This is probably fine, and
users who are feeling especially paranoid can always call
Global_RNG::seed(true, 0) to force a slow poll from all available entropy
sources.

We used to do two different estimates, one as above, and another using a
difference metric (additive difference), and then return the smaller of the
two. But in fact the addition-based estimate was always much larger, so we
don't bother with that anymore.

The estimates seem to make some amount of sense. For example, the outputs of
/dev/urandom and EGD will appear to have about the same amount of entropy,
which makes sense as they are both hashed with SHA-1. In contrast, less random
data, like ASCII strings, will get a significantly lower entropy rating. For
example, the typical string which is used to initialize the OpenSSL PRNG will
not come close to satisfying the RNGs.
