Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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. See, e.g., 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 question: who uses Dual_EC_DRBG? Do any commercial products use Dual_EC_DRBG? Does anyone use it?

share|improve this question
1  
This is not much, so I'll just leave it as a comment, but a notable founder of a security research/pentesting company recently said that, in his assessment, no one really uses it. –  B-Con Sep 6 '13 at 5:36
add comment

6 Answers

up vote 15 down vote accepted

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/

share|improve this answer
1  
Wow. Great find! It's amazing that, in the BSAFE documentation, RSA classifies the SHA-1 based PRNG as "weak" (in their words) and recommend Dual_EC_DRBG on the grounds that it provides better security. That's pretty crummy advice to be giving to implementors. –  D.W. Sep 14 '13 at 0:29
1  
If I had a product that used BSAFE, I would replace it as soon as possible. It is plausible that it has a back door, and if it hasn't got a back door, it has been carelessly designed.(I did not think anyone would ever use Dual-EC-DRBG, which means it would be silly to backdoor it. Since someone clearly is using it, that argument fails.) –  K.G. Sep 14 '13 at 11:26
    
RSA acked the problem and "will change the default RNG in RSA BSAFE Toolkits and RSA DPM as appropriate". arstechnica.com/security/2013/09/… –  András Salamon Sep 27 '13 at 20:37
    
Not only does Bsafe use it, it appears the NSA paid RSA $10m to make it the preferred algorithm in BSafe. –  sampablokuper Dec 21 '13 at 23:57
add comment

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

share|improve this answer
    
That list appears to mainly be libraries implementing the algorithm along with a others from the same standard. It's unclear if any of those companies actually use the EC_DRBG RNG. For example, OpenSSL implemented it, they as far as I know, don't use it anywhere. –  imichaelmiers Sep 6 '13 at 5:09
    
Link-only answers are discouraged on Stack Exchange. It's best to summarize the key points made in the linked page in the answer itself, so that if the link ever becomes invalid for any reason the answer will still be useful. –  Michael Kjörling Sep 6 '13 at 7:33
5  
@MichaelKjörling, I don't think the standard reasons for discouraging link-only answers apply here. It is part of NIST's job to maintain the list of algorithms that they've validated, so I don't think they're going to just stop publishing the list. Moreover, they are the authoritative source of this information, and the information changes over time, so copying the information there into this answer would be a bad idea (this answer would get out of date). Bottom line: I think pointing to the authoritative source for this information is useful and appropriate, in this case. –  D.W. Sep 6 '13 at 20:55
4  
@D.W.: I agree that the link is useful, but a summary (along with the link, of course) would IMO be even better. On one hand, the NIST table isn't exactly easy to read; on the other, it strikes me that having a summary of the current situation, as of this writing, could also be useful for future readers. –  Ilmari Karonen Sep 8 '13 at 16:49
    
Link is gone... –  owlstead Sep 16 '13 at 7:18
show 1 more comment

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.

share|improve this answer
2  
I think this answer is quite spot-on. While there are definitely smart folks at the NSA, I doubt that they don't occasionally suffer from bureaucratic circumstances like the hypothetical scenario you've outlined here... any big organization, no matter how smart its constituents (and indeed perhaps because of their intelligence) is probably going to have that bureaucratic weight. –  Reid Sep 5 '13 at 23:24
2  
Not spot-on — reads like an awful lot of groundless speculation about internal politics within the NSA. They had a goal (get a backdoor into a NIST/FIPS-approved standard) and accomplished it. Look at the list of vendors (linked from the other answer to this question) who have had their Dual_EC_DRBG implementation certified by NIST — lots of hardware, software, & networking companies are listed. It seems likely that at least some of those vendors have shipped products that use Dual_EC_DRBG for "secure" communications purposes. What's surprising about that? –  cce Sep 6 '13 at 4:42
1  
@cce: What you say sounds like speculation too ... who says their goal was to get a backdoor into a standard? Even if it was, were they successful with Dual_EC_DRBG, or were they thinking about another standard? My point is that pretty much everything in the NSA-related discussions is speculation based on some vague, general facts. I don't think it's unreasonable to suggest that the NSA may suffer from bureaucracy: the rest of the government seems consumed in it, so what makes the NSA special? –  Reid Sep 11 '13 at 19:25
1  
Disproved by the announcement from RSA that their flagship BSAFE product uses it by default. Astonishing but true. A Few Thoughts on Cryptographic Engineering: RSA warns developers not to use RSA products –  nealmcb Sep 28 '13 at 14:23
1  
@nealmcb: True. Color me surprised. –  Ilmari Karonen Sep 28 '13 at 19:15
add comment

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.

share|improve this answer
1  
Your version of Windows. But there are many versions. How about the version they sell in China? How about the version they sell in the Middle East? How about the version they sell in Russia? In Korea? –  blueben Sep 10 '13 at 6:21
    
Are there some more detailed descriptions of how the Vista+ CSPRNG works? When I last looked, I only found a description of the old XP CSPRNG. –  CodesInChaos Sep 10 '13 at 7:24
    
Welcome to Cryptography Stack Exchange. The ability to comment is only unlocked when you reach 50 reputation-points (which means 5 upvotes on answers or 10 on questions, assuming no downvotes). –  Paŭlo Ebermann Sep 10 '13 at 17:43
1  
@blueben There is only one Windows codebase since Vista. Language packs can not contain code. –  kinokijuf Sep 11 '13 at 18:09
    
@blueben I would like to confirm what kinokijuf said: starting with the Vista series, there's only a single codebase for several operating system variations. This includes the PRNG and RNG implementations. –  e-sushi Sep 15 '13 at 0:48
show 1 more comment

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.

share|improve this answer
add comment

The back door was designed and patented in 2005:

US 8396213 B2 - Elliptic curve random number generation

share|improve this answer
    
That patent does not appear to patent Dual_EC_DBRG. Nor does it appear to patent any backdoor. Rather, the patent lists Dual_EC_DBRG in the prior art, and claims to patent a method for generating the points P,Q in a way that is verifiably free of backdoors. –  D.W. Dec 4 '13 at 1:15
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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