DRBG Validation List | Hacker News Reader

DRBG Validation List

csrc.nist.gov

A couple random observations:

* The overwhelming majority of vendors here list Dual_EC_DRBG along with the HMAC and CTR DRBGs. A reminder: Dual_EC is a catastrophically slow CSPRNG that relies on bignum multiplication; if you pay any attention to crypto performance at all, you have every incentive never to use Dual_EC, and to an almost reasonable first approximation, nobody does. The HMAC and CTR CSPRNGs are innocuous designs based on simple conventional crypto.

* I'm a little suspicious of this list because it suggests Windows Server 2008 and Windows 7 use only Dual_EC. Neither do; you'd have to go through contortions to make Windows use Dual_EC. Obviously, the list is about certifications and not actual field configurations, but still, you should know: Windows does not rely on Dual_EC.

* Here are the products (other than Windows, which, see above) that are listed as only certifying Dual_EC:

    Lancope
    Mocana
    McAfee Firewall Console
    Thales Datacryptor

None of these are particularly important industry products. McAfee is not a leading firewall vendor (Cisco and Juniper are). Lancope is a niche intrusion detection product, and Lancope is not exactly a hotbed of cryptographic research, if you get my drift. Also, the CSPRNG Lancope would be using would be relevant only to their admin console. I don't know what Mocana or Thales do, which could be my ignorance showing, or it could be telling given what I do for a living.

Here's what Bruce Schneier had to say about the Dual EC DRBG:

"If this story leaves you confused, join the club. I don't understand why the NSA was so insistent about including Dual_EC_DRBG in the standard. It makes no sense as a trap door: It's public, and rather obvious. It makes no sense from an engineering perspective: It's too slow for anyone to willingly use it. And it makes no sense from a backwards-compatibility perspective: Swapping one random-number generator for another is easy."

This is basically my take on Dual EC as well. I am not putting it past the NSA to backdoor a crypto standard (I would bet against it being a NIST standard --- if they backdoored a standard, my money is on a telephony/RF one --- but I would not bet my house against it). But this would be an inexplicable backdoor to add.

> I don't know what Mocana or Thales do

Thales are a large defense contractor - a French equivalent of BAE Systems or General Atomics.

Not particularly famous for corporate integrity [0].

[0]: http://en.wikipedia.org/wiki/Thales_Group#Corruption_allegat...

My other blind spot on backdoors is defense contracting, because we won't do any of it, so maybe someone has a compelling theory on how Dual EC could have gotten NSA into EU or .CN defense establishments.

For definitions of "nobody" that include essentially all of RSA Security Inc's crypto libraries and a number of their other products, at least by default - and how many people are going to change the default?

Name a piece of software you rely on that you think is likely to use Dual_EC.

To be honest, nearly every developer will change it from the default as soon as they run a stress or performance test using a library that has dual ec as its default (e.g. BSAFE Crypto-J).

Dual EC is order of magnitudes slower than HMAC. It's impossible to not notice a default EC library if you run any kind of throughput test. Then, unless you a specific requirement to use it, you change the default.

> I would bet against it being a NIST standard

Are you actually "betting against" Dual_EC_DRBG being backdoored by the NSA? The leaked documents specifically say the NSA weakened/backdoored a NIST standard in 2006[1]. Schneier himself, in the essay you quoted, repeatedly calls Dual_EC_DRBG backdoored[2], and has more recently suggested Dual_EC_DRBG could be the standard referred to by the leaked documents[3].

Also, it's not even close to a "reasonable first approximation" to say "nobody" uses Dual_EC_DRBG. BSAFE is in over one billion applications/devices[4]; how many of those do you really think aren't using BSAFE's default RNG?

It's true this isn't at all a subtle backdoor (it took only a year for Shumow and Ferguson to discover it), nor does it appear to be very widely used, but too much of what you're saying about Dual_EC_DRBG just isn't supported by fact.

[1] http://bits.blogs.nytimes.com/2013/09/10/government-announce... and http://www.theguardian.com/world/2013/sep/05/nsa-gchq-encryp...

[2] https://www.schneier.com/essay-198.html

[3] https://www.schneier.com/blog/archives/2013/09/the_nsa_is_br...

[4] http://satchitssecurity.typepad.com/a_page_from_satchits_sec...

(1) The NYT article says NSA generated Dual_EC, but does not present evidence that it's backdoored.

(2) Schneier isn't a subject matter expert on elliptic curve random number generators.

I am aware that Schneier believes Dual_EC to be backdoored. I'm aware that Dual_EC comes from NSA. I would not use Dual_EC and would flag it if I saw it in an app I assessed. But I would still, right now, with the information I have, bet against it being an NSA backdoor. Not because I trust the NSA, but because it's a very dumb backdoor.

It helps here to understand the gist of the purported backdoor. Basically, a (sketch of a) way to think of the issue is, NSA's ECC CSPRNG is built around curve parameters in such a way that generating numbers with it involves a public key operation, and only the public key is in the standard. The obvious question is, "what's the private key?". Obviously, you're not happy that NSA (which until recently wasn't even the confirmed author of the construction) won't say.

On the other hand, that problem is SO OBVIOUS, and in SUCH A WEIRD, UNLIKELY-TO-BE-VALUABLE STANDARD, that it's kind of ridiculous. "A trojan platypus", as Daniel Franke put it.

I've already addressed the "billions of deployed device" point.

> (1) The NYT article says NSA generated Dual_EC, but does not present evidence that it's backdoored.

So all of the following is just a coincidence then?

* Publicly-released document states that as part of a project to enable SIGINT collection, the NSA "influences policies, standards, and specification for commercial public key technologies"[1]

* NYT reports "Classified N.S.A. memos appear to confirm that the fatal weakness, discovered by two Microsoft cryptographers in 2007, was engineered by the agency"[2]

* NSA was the sole editor of Dual_EC_DRBG[3]

* Dual_EC_DRBG has a property where if you know the discrete log of one of its parameters, you can predict its future output. Since it's not explained how the parameter was derived, it's possible the parameter was chosen not randomly, but in a way to ensure its discrete log is known. (Shumow and Ferguson show how this is done[4].)

> (2) Schneier isn't a subject matter expert on elliptic curve random number generators.

It's not Schneier who raised the prospect of the backdoor - Shumow and Ferguson did. It's not like the NIST curves where Schneier says he doesn't trust them, but can't specify how they could be backdoored. Here we know exactly how Dual_EC_DRBG could be backdoored. Schneier doesn't need any elliptic curve expertise to postulate that it is actually backdoored, just his intuition as a security expert (which you must respect, as you quoted him to make a point above).

> It helps here to understand the gist of the purported backdoor. Basically, a (sketch of a) way to think of the issue is, NSA's ECC CSPRNG is built around curve parameters in such a way that generating numbers with it involves a public key operation, and only the public key is in the standard. The obvious question is, "what's the private key?". Obviously, you're not happy that NSA (which until recently wasn't even the confirmed author of the construction) won't say.

No, that's not quite it. The question isn't "what's the private key?"; it's "does anyone know the private key?" If the "private key" (e in Shumow's and Ferguson's presentation) were in the spec, everyone would be able to break it. We want assurance that the only way anyone could know the "private key" is by actually solving the elliptic curve discrete log problem (which is probably only possible by generating the Q parameter yourself).

> I've already addressed the "billions of deployed device" point.

I must have missed that...

[1] http://www.theguardian.com/world/interactive/2013/sep/05/sig...

[2] http://www.nytimes.com/2013/09/06/us/nsa-foils-much-internet...

[3] ibid

[4] http://rump2007.cr.yp.to/15-shumow.pdf

You're literally the only person left who doesn't think this was an NSA backdoor. Including the people who wrote the document, and the companies who went public saying not to trust them, at great expense to themselves.

Mocana amongst other things sells FIPS-140 certified cryptography software for various different platforms. They have both C and Java libraries.

This is the only place that I've been able to find a decent list of vendors potentially affected. This lists all vendors, so you will have to ctrl-f for BSAFE.

To be completely clear, most vendors on this list are not known to be affected, only those listed as using the library, or libraries derived from it (also listed).

All entries using Dual_EC_DRBG are potentially affected, but it is believed that most do not use that by default. If it's the only one listed, you can probably assume they use it by default. Especially things called "Datacryptor DUAL_EC_DRBG" by Thales e-Security.

This seems dangerous. If you're going to name and shame people, I think you've really got to be extremely sure you're naming the right people.

This isn't an article naming-and-shaming; it's an information dump so people can sort through it and find the right people to actually name-and-shame.

This lists which companies have certified implementations, not which products relies on which CSPRNG/s by default. I think there are already internal code audits underway by some of the listed entities, if not, it would be wise to get started real quick before customer anger arrives.

If this is not a clear impetus for open source, eg, publicly audit-able code >>> trade secrets, I think we should keep blindly accepting black box solutions, from chip to app. No funny business ever happens without transparency.

Unfortunately, the stupid moderator submission title editing policy has struck again, so anybody seeing this has no context now. Thanks for being unhelpful, moderators!

I've got dozens of pieces of Cisco gear deployed throughout my network but I'm far from a crypto expert and, honestly, haven't really kept up on this specific issue so perhaps somebody can help me out here.

Within Cisco's operating systems (primarily IOS, but also NX-OS, IOS XR, etc.) I can think of a number of places where hashing and encryption are used: password hashes (obviously), BGP passwords, OSPF authentication, NTP secret keys, etc. Which of these might potentially be affected if Cisco were using this algorithm? Any of them? All of them? With the exception of being able to specify particular types of hashes for user passwords, I'm not sure what else one might do to mitigate any vulnerabilities.

Edit: After thinking about it for a few minutes, I realized that since the processors in Cisco devices are already so slow (relatively speaking), Cisco would likely avoid using such an algorithm when other, much faster options are available. I can't be for sure, of course, but it seems reasonable. In the meantime, I'll keep my tinfoil hat on.

It would be shocking if Cisco were using Dual_EC in any "traffic-scale" crypto in their devices. It isn't just extremely slow, but also slow in a way that makes it obnoxious in embedded environments.

Yeah, I thought that after posting my original comment. With the processors on the control-plane already being as slow as they are, I can't imagine they'd intentionally choose to use such a slow algorithm for such "time-sensitive" operations (verifying OSPF authentication, etc.).

https://supportforums.cisco.com/thread/2062466

http://www.juniper.net/security/auto/vulnerabilities/vuln241...

https://latinamerica.rsa.com/rsasecured/product.aspx?id=968

"Cisco routers utilize RSA BSAFE encryption and are certified to interoperate with RSA Certificate Manager software and RSA SecurID authentication technology."

You're shocked now, I guess.

But it's no big deal, nobody uses Cisco routers.

Throw Novell in there too:

http://www.novell.com/support/kb/doc.php?id=3590033

and Adobe:

https://latinamerica.rsa.com/rsasecured/product.aspx?id=108

and many more:

https://latinamerica.rsa.com/rsasecured/results.aspx?search=...

Do any of those products actually use Dual_EC? Have you checked?

You really think iOS has its IPSEC primitives wired directly to Dual_EC? That's what that error message suggests. It's not subtly slower; it's like doing an RSA operation on every damn packet.

Probably a stupid question, but could a malicious party use Dual_EC as a primitive to construct broken but fast crypto? ( I am thinking about something like seeding a fast CSRNG with a Dual_EC random number and thereby breaking the fast CSRNG.)

Wow, the scale of this is amazing, virtually all versions of windows are affected (search "Microsoft Corporation" & check for "Dual_EC_DRBG") as are a substantial number of Cisco products.

Apple seems to fare better assuming that's what this means: CTR_DRBG: [ Prediction Resistance Tested: Enabled;

Regarding hardware devices (Cisco etc routers) it'd be interesting to get an audit of vulnerability by firmware versions. People are terrible at keeping those things up to date.

TL'DR: if you fear MITM, you've got your work cut out auditting your infrastructure

Microsoft implements Dual_EC, but does not default to it.

CTR_DRBG is just a block cipher in counter mode. I don't think it's a scary construction.

I SAW THAT TPTACEK SAYS CTR MODE IS NOT A SCARY CONSTRUCTION!

Oh you are never going to live that down brother :-)

IN A RANDOM NUMBER GENERATOR.

I am not terrified of CTR, by the way; I just think CBC gets a bad rap. It's interesting that people can be on a jihad against DSA for needlessly depending on randomness, but not at all perturbed by the CTR randomness failure mode.

(Granted, the DSA failure mode is much worse and much harder to get right.)

And why is it OK for use in a PRNG/DRBG and not a cipher?

Because generally the plaintext input to a PRNG using a cipher in CTR mode is uninteresting to attackers, and generally cannot be controlled. What a DRBG needs to do is provide unpredictable bits, not bits that can't be decrypted.

If the "plaintext input to a PRNG" becomes known to the attacker, the entire output of the PRNG becomes known (i.e., 'predictable') to the attacker.

That's why I try not to give attackers root access to the system, that way they can't examine the state of my PRNG.

Because PRNG constructions tend to run the whole key schedule when they refresh their state; for instance, CTR_DRBG uses inputs to derive a nonce and a whole new key.

BTW, I think that's a great point about the comparison with DSA.

I'm obnoxious, but every once in awhile I get a good one in. :)

Let's be clear here: This is a list of product that NIST considers "validated" by an accredited lab for one or more of their SP800-09 DRBGs.

Only the "Dual EC" DRBG is known to be weak/backdoored.

We know that some of them do, but just because a product contains a validated Dual EC DRBG doesn't mean it's on by default.

Basically, the only reason to use such a DRBG is FIPS compliance, and since FIPS mandates so many other odd things most product has a special "FIPS mode" switch which is off by default.

Is it even known to be weak? Or is it, like P-224 and P-256 themselves, simply based on a constant that we don't know the provenance of?

Yes, once the spec was released it was immediately found to have biases.

Hmm, interesting to see Harris Corporation is on the list. They provide a lot of encryption gear to the U.S. government.

Reply on news.ycombinator.com