Will entropy be lost by using a DRBG?

Question

Lets assume we have a DRGB (deterministic random bit generator) which is seeded by a good true RBG (random bit generator). Before any bit has been read from the DRBG, the entropy is clearly the number of bits of the seed.

But is entropy lost, when I read out the bits of the DRBG? From an information theoretical point , one could say that entropy will diminish by 1 with every bit I read from the DRBG. But how could this be defined from a complexity theoretic point? Does there exist a precise mathematical definition of a "complexity theoretic entropy measure" ?

Maybe that question sounds a bit philosophical, but it also has practical impact, because one can decide when its time to reseed.

Answer 1

A Deterministic Random Bit Generator (DRBG) would typically be used, when you have entropy input that is either

• biased,
• inefficiently generated, or
• both of the above.

If you have a True Random Bit Generator that outputs unbiased bits efficiently, there is no apparent reason to use a DRBG in the first place. This is particularly true in case you require information theoretic security. Using a DRBG means you get pseudo random bits with computational security, typically expressed in the conventional way as 128-bits of security, 256-bits of security, etc.

This means that reseeding of DRBG, such as NIST SP 800-90A, should not be expected to be designed to address loss of entropy in the information theoretic sense, but only in a practical sense. It is done to reduce the risks (not eliminate the risks) associated with internal states being compromised through side channel attacks, etc.

Answer 2

From a practical point of view, what matters is not the entropy but the time an attack would take.

A brute force attack would be dependent on the entropy of the input, since it works by guessing the seed. This is true regardless of the number of outputs observed. Typically a key/state recovery attack on DRBGs should not become easier with more outputs, since they are based on strong primitives like ciphers or hashes for which such attacks would be huge breaks.

However, an attack does not have to be able to recover the state, only to make predictions about future output. In the case of some DRBGs there could be such attacks if you reseed too seldom. For example, with CTR_DRBG every output from the block cipher is different from the earlier ones (while the state only increments) so a long stream of outputs without updating the key would be biased. Any finite state DRBG would also eventually end up in cycles if you did not reseed.

You cannot really say anything about appropriate reseed intervals without considering the exact DRBG algorithm. NIST's DRBG recommendations (pdf) come with suggested maximum intervals defined for each algorithm, though they are very conservative and probably have more to do with regaining security in case the state has somehow leaked, as Henrick Hellström explains in the other answer.