5
$\begingroup$

Matthew Green states in the Practical Kleptography presentation (video, at about 12:15) that Hash_DRBG (from SP800-90A) as originally proposed by NSA had potentially exploitable flaws or bugs and that NIST fixed it.

I've been unable to find how. This VCAT report only states that it was contributed by NSA and NIST "provided substantial comments".

Does anyone know how Hash_DRBG was broken and what fixes were made?

$\endgroup$
9
$\begingroup$

Please bear in mind that this information is all secondhand. I have not looked closely at the original drafts of Hash DRBG (although you might find a draft that's early enough if you peruse the FOIA results in [1]).

However, during conversations with folks at NIST I was told that there were certain weaknesses in early drafts of Hash DRBG that were very similar to known issues in the FIPS 186 (DSA) DRBG. Kelsey, Schneier, Wagner and Hall have at least one paper on this [2]. In particular, if an attacker is able to control some of the entropy inputs to the DRBG, they could force that DRBG to repeat output. I gather from these discussions that the original draft of Hash DRBG had similar issues. The version published in NIST SP 800-90A was modified to deal with these.

It's important to note that I'm not saying these flaws were deliberate. Quite frankly they just look like bugs. And they appear to have been fixed long before to the publication of NIST SP 800-90A. I also can't state with certainty that Hash DRBG was an NSA design, though I believe the NSA was involved in its design.

One more note: it's my understanding that Hash DRBG was eliminated in the ANSI standard because it was deemed redundant, but it was kept in NIST SP 800-90 (though in repaired form) because the NSA asserted that some partners had already implemented it. Hash DRBG was also included in ISO 18031, some portions of which I can probably dig up and add to this link later. It's not clear whether the ISO version includes the repairs.

Welcome to our crazy world!

[1] https://github.com/matthewdgreen/nistfoia [2] https://www.schneier.com/paper-prngs.pdf

$\endgroup$
  • $\begingroup$ Thanks for the quick answer! I didn't mean to imply they were necessarily deliberate either. I'll have to look at the FOIA documents, quite a few seem relevant by titles. $\endgroup$ – otus Sep 23 '14 at 14:16
  • 1
    $\begingroup$ I'm attaching an excerpt from ISO 18031 for anyone who's eager to compare it to NIST SP800-90A. I'm posting this as a series of annoying screenshots to make it clear this is fair use. They're at isi.jhu.edu/~mgreen/hashdrbg1.png, isi.jhu.edu/~mgreen/hashdrbg2.png and so on through isi.jhu.edu/~mgreen/hashdrbg9.png. $\endgroup$ – Matt Green Sep 23 '14 at 14:49
  • $\begingroup$ Screenshots 5 and 6 seem to be missing? $\endgroup$ – otus Sep 24 '14 at 7:01
  • 1
    $\begingroup$ Sorry! Try removing the .png from those two. $\endgroup$ – Matt Green Sep 30 '14 at 2:19

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.