# Evaluating the entropy gathering in a PRNG

I'm reviewing the random number generator (expected to be of cryptographic quality) on an embedded device. My point of view here is the operating system and crypto library implementer. I'm particularly concerned about entropy gathering. I've identified a few points to look over:

• How is the initial state of the PRNG is generated?
• When should the PRNG refuse to deliver until it gets more entropy?
• There is an API call to inject more entropy, how well does it mix the new entropy with the existing state?

(In my case, there is a hardware RNG, too slow to use systematically, but we can get entropy from it.)

If my implementation is good, what should the answers to these questions look like? What other questions should I try to answer?

-

"Entropy" is a measure of what some data element could have been. We say that we have n bits of entropy in a bunch of bits if those bits could have, collectively, assumed 2n distinct values with uniform probability (there is a whole lot of complexity which hides under the "uniform" term). To make a cryptographically secure PRNG, you have to:

1. Gather enough data from random sources so as to reach at least 128 bits of entropy. The idea is that it should not be feasible, for an attacker, to "try" a non-negligible part of the space of 2n possible internal states. n=80 used to be the traditional value for that, but given the technological advances since the 80s', we now prefer n=128, which is a power of two, hence Blessed by the Gods.
2. Use that entropy-laden seed in a proper stream-cipher-like function: this is a function which outputs pseudo-random bits, based on an initial key; here, the key will be derived from the seed through a one-way function with a fixed-length output (i.e. a hash function). The security characteristics you look for here is that it should not possible, given a sequence of successive output bits, to be able to guess any other past or future output bit with success probability substantially better than 0.5. Mind the "future bits" part: this is not as immediate as you might think.

The second point is not easy. As a basic rule, if the stream-cipher-like function is not a published construction which has been precisely described in some standard, and analyzed by dozens of cryptographers, then you should consider the PRNG as being of dubious quality. A homemade PRNG is as bad as a homemade block cipher: it could be strong, but many homemade PRNG are not strong, and there is no sure test for cryptographic strength.

NIST published a complete description of some "approved" PRNG. If the PRNG you use is one of those, then that's good. Otherwise, you should really raise a warning flag.

• The initial PRNG state should be gathered from "good alea sources" which means that the source should not only produce "changing" data, but also in a way such that an attacker cannot observe the changes. For instance, sending "ping" requests to an external network host, and measuring the time it took for the response to come back, is not a good source: it sure looks random, but one has to assume that the attacker can observe your outgoing ICMP requests and the corresponding answers, and thus obtain the same timing measures. For a more detailed treatment of such questions, have a look at this answer (yes, I am quoting myself).

• The injection of additional entropy is very similar to the injection of the initial state: the "random data" used as seed if often bulky, hence there should be some mixing step to yield a high-entropy, short sequence. The tool here is any secure hash function. To make things simple, the injection should look like this: we take the current internal state, we concatenate the additional "entropy", and we hash the whole thing; the hash output is the new state. Beware: this kind of thing relies on security properties that are not exactly guaranteed for any given hash function. What I mean here is that being secure for such a usage is not a consequence as being collision or preimage resistant. Hence, there is a kind of leap of faith when using a hash function for that (although you could do worse than using SHA-256, for instance). In the NIST PRNG, I recommend having a good look at HMAC-DRBG, which uses HMAC for that kind of job. HMAC is a Message Authentication Code which uses an underlying hash function in a way which allows better "security proofs" for similar reasons.

• The idea of a PRNG refusing to deliver more data until it gets more entropy is a bit of a voodoo ritual: it is important only if you believe in it. If you initialized your PRNG with a random enough initial seed, and then used a proper data-generation function, then there should be no security issue in producing petabytes of pseudo-alea from it. However, it makes some people nervous, hence many PRNG implementations include a blocking behaviour, in which the PRNG will refuse to output more than, say, 1 MB of data from 128 bits of initial entropy. In practice, a blocking PRNG (beyond initialization -- it is necessary to block until enough initial entropy has been gathered) leads to deployment issues (e.g. a Linux OS automatic installation which blocks on a server, when it comes to generating the SSH key, because there is no keyboard or mouse to gather entropy from the user). As a rule:

a. do as the PRNG standard states (see NIST SP 800-90);

b. unless the standard explicitly states otherwise, do not ever block, as long as you got a complete initial seed.

Note that Linux's `/dev/random` and `/dev/urandom` both fail at that: `/dev/random` will block way too often, and `/dev/urandom` never blocks at all, even if it did not get a good initial seed. Fortunately, any decent Linux distribution will make sure that `/dev/urandom` is initialized with a good enough seed as part of the boot scripts (including keeping a random seed in a hidden file, generated at the previous shutdown). FreeBSD's `/dev/urandom` behaves in the way I describe, and that's good.

-
Thank you for this very interesting answer. Regarding expiration of entropy, would your opinion change if the data-generation function isn't as proper as it could be? In my case, I'm afraid I am stuck with RC4 in the short term, and entropy gathering is slow but not blocking: should I recommend for or against periodic entropy injection? – Gilles Mar 18 '11 at 15:00
Periodic entropy injection does not harm security (if it is done properly, i.e. with a secure hash function with a large enough output size -- think SHA-256 here). It may harm performance if it leads you to block. If you can inject entropy with little performance impact, then there is no problem in doing it -- except that this may lead you to a false sense of security, something which is not recommended. Periodic entropy injection will not really help you with regards to currently known RC4 shortcomings. – Thomas Pornin Mar 18 '11 at 15:20