Talk:Dual EC DRBG

Slowness

Bruce Schneier says (http://www.schneier.com/blog/archives/2007/11/the_strange_sto.html) that Dual EC DRBG is three orders of magnitude, not three times, slower than its peers. Peter 16:14, 15 November 2007 (UTC)

Fixed. -- intgr [talk] 17:12, 15 November 2007 (UTC)

Missing information

The following information is missing from the article:

• When was this PRNG standardized? (The document in reference 1 is from march 2007, but it is titled "(revised)".
• How does it actually work?

-- Paul Ebermann (talk) 15:21, 12 September 2011 (UTC)

I would like to try and describe the algorithm. I've already added a high-level overview. However I'm not sure how useful it's gonna be. Understanding the algorithm requires some completely different prerequisites than the rest of the article. Dlesos (talk) 13:26, 18 January 2022 (UTC)

"Fatal weakness" engineered by NSA?

The article currently says that DUAL_EC_DRBG has a fatal weakness which was engineered by the NSA, but that seems to be speculation. The NYT article provided as a citation does not identify the algorithm. Here is the full quote:

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

“Eventually, N.S.A. became the sole editor,” the memo says.

Bruce Schneier has speculated (see here also) that DUAL_EC_DRBG is the algorithm in question, but if that's the best we have we should a) cite it and b) state that it is speculation.

 – mike@enwiki:~$  22:45, 5 September 2013 (UTC)

Looks like we have actual confirmation.  – mike@enwiki:~$  17:06, 11 September 2013 (UTC)

Confirmation of what? Can you quote the material that indicates to you a confirmation?--Brian Dell (talk) 19:42, 13 January 2014 (UTC)

About half a year ago someone at work showed me the backdoor. I did the maths, and in my words, it's so ingenious, it's provably impossible to detect this backdoor given just the algorithm description and key parameters, with less effort than breaking the cipher. The parameters have a mathematical relation that can only be found when you know the 'backdoor math'. --217.122.174.9 (talk) 20:42, 12 March 2016 (UTC)

Further resources about Dual EC DRBG

http://www.mail-archive.com/cryptography@metzdowd.com/msg12262.html

A message from John Kelsey about the Development of Dual EC DRBG.

http://www.google.com/patents/US20070189527

US Patent US20070189527, "Elliptic curve random number generation" to Daniel Brown, Scott Vanstone, which describes the "backdoor" in Dual EC DRBG, teaches how the backdoor can be removed by generating Q (the second base point) randomly after P (the basepoint) is known by a mechanism not involving point multiplication, thereby ensuring that that P is not a known multiple of Q (which is the "backdoor"), nor that Q is known multiple of P. And further teaching how known secret relations between P and Q may be used as part of a key escrow system.

Published by the NSA?

The statement in the lede is misleading: I can find no publication of the algorithm by the NSA in advance of the NIST SP800 publication. Can anyone cite such a reference? Ross Fraser (talk) 13:34, 23 September 2013 (UTC)

The current lede does not say that NSA published the standard? Thue (talk) 13:40, 23 September 2013 (UTC)

Don't be a mouthpiece for RSA

Their statement to Ars is so clearly misleading, that anyone who knows anything about the subject can easily see it. Slow random number generator to thwart attacks? Gimmi a break, this is not how things are done. Wikipedia shouldn't reproduce it without clearly explaining it's nature, as people that does not understand the issues involved might be easily misled by this PR/damage control statement from RSA. jk 22:14, 26 September 2013 (GMT+1)

Agreed 100%. "Dual_EC_DRBG was an accepted and publicly scrutinized standard" - yeah, and the scrutiny had clearly concluded it was inferior and possibly had a backdoor. I am surprised RSA can't find anybody to spin less obvious bullshit. I will change it if nobody else will, using the section I write at Rsa_security#NSA_backdoor as a template. Thue (talk) 22:03, 26 September 2013 (UTC)

The wording is too argumentative. We can only include what reliable sources say, not our own opinions. I've trimmed out unsourced opinion.--agr (talk) 23:04, 15 October 2013 (UTC)

Wording problem

The text "one of the recommended configurations of the Dual_EC_DRBG permits the possibility of the existence of a known secret key, which facilitates solution of the problem, has been retained" doesn't parse. Was is supposed to be something like "... permits the possibly that a known secret key ... has been retained"? 2620:0:1000:1501:1260:4BFF:FE68:1974 (talk) 16:48, 3 October 2013 (UTC)

Revert article rename?

I disagree with the recent article rename, from Dual EC DRBG (Google: 151,000 results) to Dual elliptic curve deterministic random bit generator (Google: 14,500). Note that even Dual_EC_DRBG gets 73,000 Google hits. (All searches with quote marks)

The expansion is way too long and I'd argue it violates WP:COMMONNAME. The subject is most well known due to having a backdoor, it doesn't really matter what technology it's based on. Even the original standard almost exclusively refers to it as "Dual_EC_DRBG", only once does it say "Dual Elliptic Curve Deterministic RBG" -- in the section title. [1] -- intgr [talk] 22:16, 23 December 2013 (UTC)

I renamed the article because the previous title was an uninformative initialism - the general reader cannot work out what the article is about from the title. Google hits are not a good way to assess proper article names. WP:COMMONNAME calls for article titles to be recognisable and states 'Ambiguous [...] names for the article subject [...] are often avoided even though they may be more frequently used by reliable sources'. Whilst not strictly speaking ambiguous, 'Duel EC DRBG' gives very little information on what the article is about, whilst 'Dual elliptic curve deterministic random bit generator' at least gives the reader the information that this is a random number generator that uses elliptic curves. See also WP:CONCISE which requires article titles to contain 'sufficient information to identify the topic in a way the average person searching for it will recognize'. I think the new name is clearer, more informative, and not overly verbose. Having said that, I moved the page boldy and would no objection to moving back if consensus on this talk page is against me. Modest Genius ^talk 14:48, 24 December 2013 (UTC)

I notice that the article has been moved back to the initialism. I agree with that. The previous spelled out title can refer to a whole class of RNGs with different elliptic curves. Dual_EC_DRBG refers to an instance of the overall concept using specific elliptic curve generated by NSA and approved by NIST. It is the provenance of that curve, and the possibility that it could have been generated with a back door, that is at the heart of the controversy. --agr (talk) 17:07, 29 December 2013 (UTC)

List of Products using this algorithm

We need a list of products, operating systems, appliances that use this algorithm. Is MS Windows using it? MacOSX? etc. — Preceding unsigned comment added by 113.28.129.54 (talk) 02:15, 27 December 2013 (UTC)

There are two parts: who implemented it, and who used it by default. A good starting point is http://crypto.stackexchange.com/questions/10189/who-uses-dual-ec-drbg Thue (talk) 03:23, 27 December 2013 (UTC)

RSA-NSA deal is not alleged

Reuters has reported there was a RSA-NSA deal to set Dual_EC_DRBG, and RSA has not denied this. So the existence of this deal is not disputed, and is therefore not "alleged", and I am removing all "alleged" prefixes for this in the article. Thue (talk) 19:18, 2 January 2014 (UTC)

What remains "alleged" is that receiving funding from the NSA is relevant here. The NSA has been heavily involved with the encryption "industry" for a long time because they know a lot about encryption.--Brian Dell (talk) 19:51, 13 January 2014 (UTC)

Use of "alleged" for the existence of the backdoor

The New York Times writes:

Cryptographers have long suspected that the agency planted vulnerabilities in a standard adopted in 2006 by the National Institute of Standards and Technology 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.”

To me, that sounds like as solid a confirmation as you could, without NSA coming straight out and admitting it (good luck waiting for that). And since it is NSA's documents, the documents are essentially NSA admitting it. All the cryptographers believe it, and NIST itself obviously believe it too. Together with the circumstantial evidence (we know one of the CSPRNGs is backdoored, and NSA did pay RSA $10 million to use that specific one..., plus the standard really is obviously contorted to allow the backdoor, etc etc), that should be good enough to drop the "alleged" everywhere, IMO.

Thoughts? Thue (talk) 08:04, 3 January 2014 (UTC)

Are there any competent impartial people who have publicly stated that they don't believe it's a backdoor? I remember reading on Schneier's blog that he's not convinced it's a backdoor, but I can't find it now. His later posts display less doubt though. -- intgr [talk] 17:55, 3 January 2014 (UTC)

Dan Brown is an expert cryptologist who appears to be impartial (unlike, say, Schneier, see below) and Brown has strongly suggested that the general impression created by the NYT story is misleading although he doesn't mention the NYT in particular: http://www.ietf.org/mail-archive/web/cfrg/current/msg03651.html See also here where Brown notes "many statements about Dual_EC_DRBG that seem too broad." Later, Brown says "I still don't know for sure if the default P&Q are backdoored." Crypto developer Henrick Hellström is also "not entirely convinced NSA actually intended to put a backdoor in Dual EC DRBG, or rather, that this standard was part of the SIGINT enabling program."--Brian Dell (talk) 19:15, 13 January 2014 (UTC)

The Wired article How a Crypto ‘Backdoor’ Pitted the Tech World Against the NSA apparently tried to find somebody who didn't think there were a back door, to get a counterpoint. And the person they found to represent the nay-sayers was... not a cryptographer, but an anonymous manager from Microsoft! I thought that was unintentionally hilarious. Thue (talk) 19:10, 3 January 2014 (UTC)

The whole counterpoint in the article (which the cryptographer they talk to dismisses) hangs on the idea that the New York Times may have mislead themselves while reading the documents. But there really isn't any newspaper more careful about the assertions it makes than New York Times, especially accusations against the US government, from the newspaper who refused to use the word torture about anything the US did to prisoners after 9/11. Given that we don't have the raw documents, and with the supporting evidence we know, I believe we have to go what with what the New York Times concludes from the documents. Surely the Times have a competent cryptographer on staff to make sure it actually understands what the documents say. The Wired article tries to make a point out of the fact that the 2007 Shumow presentation says "we can't be sure", but the whole point of the backdoor is that it is theoretically impossible to verify whether anybody has the secret key. Thue (talk) 02:01, 4 January 2014 (UTC)

It's generally believed that the NYT's expert consultant here was Schneier. He's the only cryptography sort known to have seen the Snowden documents ("I have been working with Glenn Greenwald on the Snowden documents, and I have seen a lot of them.") Schneier made new claims about the NSA the day of the NYT story in a fashion suggesting he was getting his information in parallel with the NYT. But Schneier has frequently suggested conspiracy theories about the NSA while backing up just enough to maintain plausible deniability that he's that sort. He initially claimed that NIST had made "internal changes" to the Keccak algorithm that reduced security, and the clear takeaway was that Scheier was calling on his authority as an expert on the technical question of whether there were or were not changes suggested by NIST under the NSA's influence to create the impression that the NSA had deliberately subverted that algorithm. A few days later he backs off, saying he "misspoke" with respect to his claim about the NIST making "internal changes" and said "I do not believe that the NIST changes were suggested by the NSA." Of course he still insists that has fundamental point remains (that the NSA is a bogeyman) but in fact it's enormously different because he no longer is providing any technical expertise supporting the contention that the NSA has undermined the Keccak algorithm, just an opinion that the NSA has undermined "trust," which any non-expert could just as readily assert. Later that same month, Schneier titles a post "US Government Monitoring Public Internet in Real Time." What's it about? Some guy tweeting from the Acela train that former CIA and NSA Director Michael Hayden was on the same train and Hayden learned that this guy was tweeting about him. If there was anything nefarious here (on the part of the NSA) Schneier doesn't provide any "expert" support to the contention. Schneier later "clarifies" that "I don't think this was a result of the NSA monitoring the Internet." Well then what's the point of his post and its title? See the pattern here? Schneier jumps at something, speculates, but is then reluctant to stake his professional reputation on any particular technical claim about the NSA that could potentially be disproven by a thorough fact investigation. This is Schneier on Dual_EC_DRBG in a nutshell. Where has Schneier said unequivocally that the NSA corrupted NIST to deliberately undermine Dual_EC_DRBG? He hasn't. My point here being that when NYT goes categorical on Dual_EC_DRBG, it is purely speculative to insist that Schneier, as the expert consultant, would have seen that categorical statement before it went to press and would have corrected it. It's not his reputation on the line but the NYT's. Schneier's claim to fame is not taking on people pointing fingers at the NSA and saying they've gone too far. In fact, Schneier frequently points the finger himself but is very solicitous about his status as an expert and accordingly backpedals when he senses that he's gotten far enough over his skis to potentially threaten his credibility.

At a minimum, the NYT story is weakened by the fact that the NIST responded to it with a categorical denial: "NIST would not deliberately weaken a cryptographic standard" and the NYT failed to advise readers of this denial (is there any evidence the NYT even tried to contact NIST as part of its due diligence process?) The NYT also fails to report that the vulnerability here couldn't be exploited by anyone except the author. The technical reality here is that you have to know the secret numbers. There is an asymmetry here: if the NSA did insert a backdoor here, no criminal syndicate could use it, yet you wouldn't know that reading the Times. Schneier, and everyone else in the cryptography business who knows the particulars of the Dual_EC_DRBG vulnerability understands this, but Schneier and his like-minded privacy advocates in crypto have been conspicuously silent on this fact, failing to use their technical knowledge to point out this asymmetry, apparently because that would just pour cold water on the "firestorm" (to use WIRED's term for what the NYT started). WIRED initially exhibited the same anti-NSA slant in what it wrote about in the immediate wake of the NYT story, but after some technical investigation "surprised" themselves: "But beneath the flames, a surprising uncertainty is still smoldering over whether Dual_EC_DRBG really is backdoored."

The final indictment of the NYT's reporting is when the NYT mentioned "the fatal weakness, discovered by two Microsoft cryptographers in 2007" and failed to point out for readers that these same two cryptographers said at the time that "WHAT WE ARE NOT SAYING: NIST intentionally put a back door in this."

The bottom line is that there is a difference between advising readers here on Wikipedia that the NYT didn't hedge in reporting that this standard was backdoored, and Wikipedia stating categorically in its voice that the standard was backdoored. The WIRED story clearly claims that there is "uncertainty" on the point, and Wikipedia should acknowledge that.--Brian Dell (talk) 16:45, 13 January 2014 (UTC)

The NYT quote at the beginning of this section starts "Classified N.S.A. memos appear to confirm…" That sounds like a hedge to me. If the documents the Times reviewed explicitly stated that NSA built a vulnerability into Dual_EC_DRBG, the Times would have said "Classified N.S.A. memos confirm…" Their editors know the difference. There are many reasons to suspect a back door, theoretical possibility, opportunity and motive, but as far as I have seen there has been no clearcut proof. Until there is, we should continue to use the word "alleged" while laying out the full story so readers can form their own judgement. We can even quote what the Times said. But Wikipedia must not draw its own conclusions. --agr (talk) 22:23, 13 January 2014 (UTC)

----

Brian Dell, you are misrepresenting what Schneier actually says.

> "He initially claimed that NIST had made "internal changes" to the Keccak algorithm that reduced security, and the clear takeaway was that Scheier was calling on his authority as an expert on the technical question of whether there were or were not changes suggested by NIST under the NSA's influence to create the impression that the NSA had deliberately subverted that algorithm" link

What he really said:

• NIST made changes to the algorithm after the competition.
• There is no question that the changes weaken the algorithm, only whether the changes were justified or not.
• NIST is currently going through a crisis of trust in the public opinion, because of the NSA saga.
• If you have a crisis of trust, then that's a bad time to make changes to weaken algorithms; it risks eroding that trust further.

These are all easily verifiable facts and it's a reasonable logical progression. He said nothing to suggest that the NSA was behind this decision.

He didn't "back off" from any of these statements. He backs away from the phrase "internal changes", these are not internals of the Keccak algorithm, but its parameters that are recommended by the standard.

> "Schneier titles a post "US Government Monitoring Public Internet in Real Time." What's it about? Some guy tweeting from the Acela train that former CIA and NSA Director Michael Hayden was on the same train and Hayden learned that this guy was tweeting about him. If there was anything nefarious here [...]" link

Again, the article says nothing about anything nefarious, it's just you making that judgement. The original post (BEFORE the update) even said "Nothing covert here; the tweets were public. But still, wow"

All these tweets were public, anyone could have read them. It's reasonable that a well-funded PR agency is monitoring public opinion on social media. This is just interesting confirmation of quickly they reacted.

None of this undermines Schneier's credibility, merely confirms that you need reading comprehension. -- intgr [talk] 21:53, 14 January 2014 (UTC)

It seems to me that the party with the reading comprehension problem is you. According to you, what "he really said" included the claim that "There is no question that the changes weaken the algorithm". This is a cryptographic objection, is it not? When Schneier later says "My problem with the changes isn't cryptographic" that is a retraction of all cryptographic objections, no?

The observations Thomas Pornin made about Keccak/SHA-3 the day before Scheier issued his "security levels were reduced" objection are germane here: "In many cases (unfortunately, in most cases), decision to use or not use a specific algorithm in a given system will be taken by people with a, let's say, less acute grasp of cryptography than the crowd of cryptographers. Most don't imagine that there is a difference between collisions and preimages. What happens on their heads is not something like "mmh, NIST made a trade-off between academical security and performance, but a sound one, approved by other cryptographers, so that's good". Rather, it goes along the lines of "OMG they changed the algorithm now it's all backdoored !". Schneier jumped in with the OMG! crowd and then pulled himself out after his charge of "internal changes" was exposed as bogus and realizing that if he stood by "security levels were reduced" as an objection he would be making a gigantic hypocrite out of himself. It's true that you can't get 512-bit pre-image resistance with Keccak/SHA-3 but Schneier once called "ridiculous key lengths" one of the warning signs of "snake oil cryptography." To quote Schneier: "we cannot even imagine a world where 256-bit brute force searches are possible. It requires some fundamental breakthroughs in physics and our understanding of the universe. For public-key cryptography, 2048-bit keys have same sort of property; longer is meaningless." Keccak/SHA-3 offers security corresponding to public-key cryptography of 15360 bits! As for the "US Government Monitoring Public Internet in Real Time" post, why bother telling us that the "US Government [is] Monitoring Public Internet in Real Time" if there's nothing more to see here than a PR agency monitoring public opinion on social media? Why any need to "clarify" that "I don't think this was a result of the NSA monitoring the Internet" if nobody with a basic level of reading comprehension could have possibly concluded that he ever insinuated such a thing?--Brian Dell (talk) 01:33, 15 January 2014 (UTC)

Dual EC/TLS Vulnerability

http://dualec.org/ http://projectbullrun.org/dual-ec/ 80.226.24.13 (talk) 08:05, 2 April 2014 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified 2 external links on Dual EC DRBG. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20131227190128/http://veridicalsystems.com/blog/secure-or-compliant-pick-one/ to http://veridicalsystems.com/blog/secure-or-compliant-pick-one/
• Added archive https://web.archive.org/web/20131227190128/http://veridicalsystems.com/blog/secure-or-compliant-pick-one/ to http://veridicalsystems.com/blog/secure-or-compliant-pick-one/

When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at {{Sourcecheck}}).

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 18 January 2022).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 07:35, 17 December 2016 (UTC)

Need a section on fixed Dual EC

I believe by now that a number of programs use Dual EC, but have changed the bad parameters so it's now secure. Not sure how many programs use the fixed version, or if the fixed version is in any way backward compatible (a communication from a fixed program being able to send an encrypted message that can be read by an un-fixed program, or visa versa). — Preceding unsigned comment added by 2601:601:F00:1010:59F7:107A:36EF:5204 (talk) 10:42, 22 September 2017 (UTC)