Who uses Dual_EC_DRBG?

Question

Recent news articles have suggested that the NSA may be involved in trying to influence the cryptography in public standards or commercially deployed software, to enable the NSA to decrypt the encrypted traffic. For example, see this article in the New York Times.

The New York Times article specifically mentions a 2006 NIST standard, where two Microsoft engineers later discovered a serious problem in the scheme. The New York Times article explains how the standard was written by the NSA, who pushed the scheme hard:

Simultaneously, the N.S.A. has been deliberately weakening the international encryption standards adopted by developers. One goal in the agency’s 2013 budget request was to “influence policies, standards and specifications for commercial public key technologies,” the most common encryption method.

Cryptographers have long suspected that the agency planted vulnerabilities in a standard adopted in 2006 by the National Institute of Standards and Technology, the United States’ encryption standards body, and later by the International Organization for Standardization, which has 163 countries as members.

Classified N.S.A. memos appear to confirm that the fatal weakness, discovered by two Microsoft cryptographers in 2007, was engineered by the agency. The N.S.A. wrote the standard and aggressively pushed it on the international group, privately calling the effort “a challenge in finesse.”

After some sleuthing, I'm pretty certain this is a reference to the Dual_EC_DRBG pseudorandom number generator scheme described in NIST SP 800-90. The weakness is that Dual_EC_DRBG appears to contain a backdoor, and anyone who knows the backdoor can totally break the PRNG. The weakness was first described in a rump session talk at CRYPTO 2007 and was subsequently discussed by Bruce Schneier in Wired.

As a consequence, there are now good reasons to suspect that Dual_EC_DRBG contains a NSA backdoor, and the NSA might be able to spy on anyone who is using Dual_EC_DRBG.

My questions:

• Who uses Dual_EC_DRBG?
• Do any commercial products use Dual_EC_DRBG?
• Does anyone use it?

Answer 1

RSA BSAFE Libraries (Both for Java and C/C++) use it as their default PRNG.

Java:

• http://developer-content.emc.com/docs/rsashare/share_for_java/1.1/dev_guide/group__LEARNJSSE__RANDOM__ALGORITHM.html

C/C++:

• https://community.emc.com/servlet/JiveServlet/previewBody/4950-102-2-17171/Share-C_1.1_rel_notes.pdf

This obviously impacts users of the library such as "McAfee Firewall Enterprise Control Center".

See also https://lwn.net/Articles/566329/

Answer 2

Here is a list of products and companies who have had their EC DRBG algorithm validated by NIST. http://csrc.nist.gov/groups/STM/cavp/documents/drbg/drbgval.html

The validation lists all modes that have been validated, so you can see which ones have gone to the effort of having their implementation of Dual_EC_DRBG validated. Tim Dierks points out that, for Lancope's certification (NIST validation #288), Dual_EC_DRBG is the only listed mode of operation that was tested or validated. It's hard to know why Lancope would have submitted their library for validation if they weren't using it. So, it sounds like there exists at least one implementation in the wild that uses Dual_EC_DRBG. (Thanks to Tim Dierks for this analysis.)

Answer 3

Frankly, I'd be surprised if anyone did use it. Even before the potential backdoor was discovered back in 2007, the Dual_EC_DRBG was known to be much slower and slightly more biased than all the other random number generators in NIST SP 800-90. To quote Bruce Schneier:

"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."

I guess it's possible that the only people at NSA who ever thought the back door was going to work were too high in the hierarchy to really understand the practical issues. I can easily imagine a conversation something like this:

"The SIGINT folks keep asking for an algorithm that we can break but nobody else can. Is that possible?"

"Well, technically, yes, but it'd be really slow. Nobody's ever going to want to use it. And it'd look really suspicious, anyway."

"Never mind that, just do it. I really want to get those guys off my back."

The only other possibility I can think of is that maybe some people are using Dual_EC_DRBG in crypto products, simply because the NSA has been leaning on them to do so. But it still seems like an awkward way to introduce a backdoor into a cryptosystem, when it would be so much easier to just slip in a deliberate bug or two. Still, it's a NIST-approved algorithm, so using Dual_EC_DRBG could at least let you legitimately claim that your code has been tested and validated, while still having a backdoor.

Answer 4

As of 9 Sep. 2013, the NIST recommendation is that Dual_EC_DRBG SHOULD NOT be used. Quoting from the link:

Recommending against the use of SP 800-90A Dual Elliptic Curve Deterministic Random Bit Generation: NIST strongly recommends that, pending the resolution of the security concerns and the re-issuance of SP 800-90A, the Dual_EC_DRBG, as specified in the January 2012 version of SP 800-90A, no longer be used. [emphasis in original]

Also, the comment period for SP 800-90A has been reopened through 6 Nov. 2013.

Effective immediately, NIST Special Publication 800-90A is being re-issued as a draft for public comment for a period ending November 6, 2013

The complete drafts and the announcement of the comment re-opening are available at http://csrc.nist.gov/publications/PubsDrafts.html.

Answer 5

For those who are wondering if Microsoft (being a big vendor) uses it… Windows does not use it. In fact, you must explicitly change from the default RNG which is AES-CTR RNG.

Specifically:

Debugging on Windows7 shows CryptGenRandom uses AES256-CTR with a 48 byte seed, which re-keys by XORing with its next 48 bytes output after each invocation to provide forward security for the RNG state.

The RNG state is provided per thread which in turn is fed from a process wide RNG state.

Slightly weirdly, 8 x 48 byte states are maintained for the process (each initially seeded from a kernel call to CNG.sys plus other info) RNG which are cycled round robin to provide the per thread initial RNG seeds.

Answer 6

On the Practical Exploitability of Dual EC in TLS Implementations by Stephen Checkoway et al. (Usenix 2014) is some research that has been done on how much this NSA backdoor has affected the internet.

In short: It's hard to say. What saved a lot of systems from being compriomised is the fact that Dual_EC_DRBG was poorly executed and recommended against early.

Microsofts SChannel library implements Dual_EC_DRBG and is used by 12% of the servers at time of the paper. But not having the algorithm as the default means that not all those servers are vulnerable to the attack.

The largest harm was probably done by RSA making the Dual_EC_DRBG algorithm the default DRBG for their BSAFE suite. (Result of the $10 Mio bribe from the NSA)