Weakness of Hash_DRBG when entropy is mixed in gradually

Question

NIST SP800-A states (Appendix C p. 89):

There are known problems with Hash_DRBG when the DRBG is instantiated with insufficient entropy for the requested security strength, and then later provided with enough entropy to attain the amount of entropy required for the security strength, via the inclusion of additional input during a generate request. However, these problems do not affect the DRBG’s security when Hash_DRBG is instantiated with the amount of entropy specified in this Recommendation.

There is no such warning about HMAC_DRBG.

What are those known problems? The publication does not give a reference for this.

This may or may not be related to weaknesses in an early draft of Hash_DRBG. The concern is the same, but those weaknesses are supposed to have been fixed, so there shouldn't be any remaining “known problem”.

I know that HMAC_DRBG may be preferable for “theoretic” reasons — Hash_DRBG relies on much stronger assumptions about the underlying hash. But weakness in the face of an entropy source of worse quality than expected is a practical concern in many scenarios. In what way is Hash_DRBG weak when initially instantiated with low entropy, that mixing in entropy later doesn't fix?

Answer 1

It is hard to say what design rationale went into the design of the NIST DRBGs, which are ridiculously complicated ways to turn short-output PRFs into long-output PRFs typical of bureaucratic government crypto.

Certainly one can say generally that no entropy pool with incremental seeding can thwart an adversary who can witness outputs before adequate entropy has been supplied to the pool. Here an entropy pool is a state with an ‘absorb’ and ‘squeeze’ operation (or ‘enter’ and ‘extract’); the usual notion of a PRNG or DRBG is a special case where you absorb a seed once and squeeze output forever after.

Why can't you thwart this? Say the adversary is bounded to a budget of $2^{128}$ crypto operations. (Here a crypto operation is, e.g., an absorb followed by a squeeze, and is some constant number of bit operations.) If you absorb an input with 64 bits of entropy, from the attacker's perspective, and squeeze a long-enough output, the adversary can expect to try $2^{63}$ possible inputs before finding the one that matches the output. Now the state has no entropy, from the attacker's perspective. If you try to incrementally add another 64 bits of entropy, it's too late—it's as if you hadn't added the original input.

Why would NIST apply this warning to Hash_DRBG but not HMAC_DRBG? I dunno, why would NIST not comment on the provenance of the standard $P$ and $Q$ base points in Dual_EC_DRBG even after John Kelsey personally asked the NSA where they came from and was rebuffed? Government bureaucracies are formalized systems of exacerbating confusion of malice with incompetence.