* RNG 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.17)
is pretty clear, so it should be fairly easy to understand the algorithms
directly. Just in case additional explaination is desired, I wrote this.

Randpool is designed to provide the maximum possible assurance that the PRNG is
safe. The X9.17 generator (actually a modified X9.17) is significantly faster,
but somewhat more risky for general use. For this reason, Randpool is used for
generating keys, and the X9.17 generator is relegated to generating nonces and
the like.

If you think of any kind of attack on either RNG design, please contact me so I
can fix it.

Randpool

Randpool has an internal state called pool, which is 1024 bytes long. This is
where entropy is mixed into and extracted from. There is also a small buffer
(called output) from which the output is taken.

Every time some new output is needed, we hash (with SHA-1): 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, 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 key AES using the contents of the current output buffer (this
key is not used directly as output, for obvious reasons). We then encrypt the
entire pool in CBC mode, using the last block of the pool as the IV. Finally,
we re-encrypt the output buffer using the new key. Every time randomness is
added to the PRNG, we remix the pool, and also include several (at least 2)
timer values into the mix.

The use of the counter and timestamp means that the resulting 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.

The pool mixing strategy is a bit more questionable. In particular, keying the
cipher using what would have been the output, encrypting the output using that
cipher, and then using it for output, is a rather strange thing. However,
unless AES is much weaker than anyone thinks, it should not be a problem.
Perhaps a stronger strategy is needed here. The mixing function itself
(AES/CBC) should work quite well for distributing entropy across the entire
state - 16 bytes of information is pretty decent.

The reason for using the last block of the pool as the IV when encrypting the
pool in CBC mode is so that changes in the middle of the pool will affect the
end of the pool, and then using the end as the IV will affect the entire pool
the next time. We always mix at least twice when adding entropy, so this should
be OK.

When adding entropy, the Randpool object estimates how much entropy is in the
input buffer. If less than 256 bits of (estimated) entropy have been provided
as input, Randpool will refuse to produce output. When mixing in provided
entropy, we XOR the input against at most half of the pool (this is done
repeatedly if needed).  After each XOR against the pool, the generation
algorithm is run, followed by a pool mixing. We follow up with another pool
mixing at the end. While this is rather expensive, no more than a few tens of
kilobytes will ever be provided as input to a Randpool, so it is not much of an
issue. 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 the entire
internal state.

X9.17 RNG

This is essentially the standard issue X9.17 appendix C PRNG, with the
following changes:

 * AES is used instead of TripleDES
 * The timestamp is encrypted in CBC mode instead of ECB
 * Every 16 iterations, we do a rekeying of the cipher, taking the new key
   from some internal state.

Entropy is added by XOR'ing the input into one of the state buffers, then
generating new output (which is discarded). This is felt to be sufficient,
because in Botan the entropy provided to the X9.17 generator is the output of a
Randpool generator. In addition, the fact that the X9.17 generator is only used
to generate nonces means attacking it is not likely to be terribly fruitful
anyway.

The X9.17 generator will refuse to work unless it believes that at least 96
bits of entropy have been provided. This should be more than sufficient for
nonce generation.

Entropy Estimation

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

Essentially, if the input is less than 5 bytes long, we say that the input had
that many bits of entropy (ie, a 1 byte input is marked as having 1 bit of
entropy). This is just to simplify the rest of the code; it may be better to
say anything less than 5 bytes has no entropy at all.

In any case, the entropy is estimated using first, second, and third level
deltas. The deltas are computed as the binary difference (ie XOR) rather than
additive difference. The hamming weight of the smallest delta is computed, and
then divided by two (in the spirit of general paranoia). This value is added to
the entropy estimate. This is not a particularly clever technique, but it tends
to underestimate the provided entropy, which in this case seems like a good
thing.

The estimation seems fairly accurate. 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 RNG will not come close
to satisfying the RNGs.
