* 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 hash function (SHA-256) and a
block cipher (AES-256).  Where a specific size is mentioned, it should be taken
as a multiple of the cipher 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 hash a counter (incremented every
output), the value of a high resolution timer, and the entire pool. The
resulting hash is XORed into the output buffer (wrapping as needed), and the
output buffer is then encrypted with AES, producing 16 bytes of output.

After every 8 blocks (128 bytes) have been produced, we mix the pool. To do
this, we first rekey our AES object with the hash of the current pool. 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 as described above.

Every time randomness is added to the PRNG (which is done by XORing it with the
current pool contents), we remix the pool. If the randomness is longer than 256
bytes, it is broken into multiple pieces which are sequentially XORed against
the pool (which is then mixed). The reason for limiting each mixing pass from
affecting no more than half the pool is to make sure that it is impossible to
affect or control the entire internal state at once.

The use of the counter and timestamp means that the hash will change every time
(even if the timestamp somehow becomes frozen). Even if, somehow, both values
became frozen, the output would still appear random because it is XORed against
the previous output and then encrypted with a block cipher.

* 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 implemnetation has been checked against known 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.

