6
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I am thoroughly unimpressed by this answer. “typical of bureaucratic government crypto” is not a scientific argument and is rather silly. You don't explain why Hash_DRBG and HMAC_DRBG would have different properties. I'm not asking what you think of NSA, I'm asking for scientific or historical reasons. The middle paragraphs may be part of a good answer, but they would be better served on their own. $\endgroup$ – Gilles 'SO- stop being evil' Dec 29 '17 at 12:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.