"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:
- 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.
- 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.
As for your exact questions:
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.