Slashdot Mirror
Dual_EC_DRBG Backdoor: a Proof of Concept
New submitter Reliable Windmill sends this followup to the report that RSA took money from the NSA to use backdoored tech for random number generation in encryption software. From the article:
"Dual_EC_DRBG is an pseudo-random number generator promoted by NIST in NIST SP 800-90A and created by NSA. This algorithm is problematic because it has been made mandatory by the FIPS norm (and should be implemented in every FIPS approved software) and some vendors even promoted this algorithm as first source of randomness in their applications. If you still believe Dual_EC_DRBG was not backdoored on purpose, please keep reading. ... It is quite obvious in light of the recent revelations from Snowden that this weakness was introduced by purpose by the NSA. It is very elegant and leaks its complete internal state in only 32 bytes of output, which is very impressive knowing it takes 32 bytes of input as a seed. It is obviously complete madness to use the reference implementation from NIST"
Reuters reported on Saturday that the NSA had secretly paid RSA Data Security $10 million to make a certain flawed algorithm the default in RSA’s BSAFE crypto toolkit, which many companies relied on. RSA issued a vehement but artfully worded quasi-denial. Let’s look at the story, and RSA’s denial....
shun anything electronic, or electric for that matter. Substinance farm and read dead-tree books for leasure.
The link above is a very good introductory article on EC cryptography. If you know a little math but have no background in elliptic curves, this is a good introduction. Well worth reading.
Clearly explained at an introductory level, with Wikipedia links for the assumed terms.
Topical, singular (ie - it's the first one currently, a news "scoop" if you like), technical, and important.
Lots to like here - Slashdot needs more articles like this.
There's still no requirement for Dual EC DRBG (so the summary is misleading) but Annex C is also somewhat misleading.
FIPS 140-2 is modified by SP 800-131A which describes algorithm transitions (see FIPS 140-2 Implementation Guidance G.14) and therefore any new FIPS 140-2 module submitted after Dec 31, 2013 can only use an RNG from the SP 800-90A standard; not any of the other RNGs listed in Annex C.
However SP 800-90A specifies four different DRBG algorithms, only one of them being the suspect Dual EC DRBG. So even today new modules aren't forced to use it. (And if fact I believe NIST posted a warning on their 140-2 website strongly recommending that people not use the Dual EC DRBG)
(Hi. I'm the one Dan was replying to, from another thread. Proof on request, but /. mangles PGP signatures, amongst many other things.)
No, it'd take a Rho attack of 2^127.8 complexity to break that key. Not happening. Way more likely is that someone simply steals the key from the NSA - a daunting prospect - but not particularly useful if all you wanted to know is that there is a backdoor, not to actually use it. There is, and people have been pointing that out since 2006.
I was... surprised at Dan's response. I did not actually expect a response to noting that the backdoor in Dual_EC_DRBG was, and I'll quote myself here, "a backdoor that couldn't have been more obvious if you'd erected a flashing neon sign and driven a mounted parade with a marching band through it", because I didn't think anybody was in disagreement about that. Apparently I was wrong.
My own reply to him, pointing out that even if you mind your Ps & Qs (in the way that he patented, mind you), Dual_EC_DRBG still sucks: http://www.ietf.org/mail-archive/web/cfrg/current/msg03689.html
I don't have a reply to that yet. In all fairness, it has been the Christmas and New Year period, and it's been kind of a busy one this year, and there's some procedural things to sort out that are probably going to take some time (and input from the crowd here would probably only make things worse, right now). Meanwhile, we have recommendations to make about TLS - in short, use it, but for God's sake, turn off RC4 because it's shit and probably worse than the BEAST attack people tended to use it to avoid - and some new things to roll out with that before the big work on TLS 1.3; with encrypted ClientHellos and pinned certificates to stop random CAs impersonating sites high on the wishlist.
An update, by the way: after re-opening the comments period, having been openly informed of the Snowden disclosures (albeit years after cryptographers warned them), NIST have agreed to remove Dual_EC_DRBG from SP 800-90A. So that's something, at least.
I have been adding various facts to the Wikipedia article on Dual_EC_DRBG. A good deal of the most interesting points have not been reported in mainstream media.
* The ANSI group which standardize Dual_EC_DRBG were aware of the potential for a backdoor.
* Three RSA Security employees were listed as being in that ANSI group, making RSA Security's claim innocence claim shaky, since it is less likely that RSA Security didn't know about the back door when NSA paid them $10 million to use Dual_EC_DRBG as default.
* Two Certicom members of the ANSI group wrote a patent which describes the backdoor in detail, and two ways to prevent it.
* Somehow the ways to prevent the backdoor only make it into the standard as non-default options.
* Somehow the people on the ANSI group forget to publicize the potential for a backdoor. Especially Daniel brown of Certicom (co-author of the patent), who also wrote an attempt at a mathematical security reduction for Dual_EC_DRBG, but somehow forgets to explicitly mention the backdoor. The conclusion in Brown's paper also seems very determined to hype Dual_EC_DRBG, whereas the other papers about Dual_EC_DRBG seem excited to hype the errors they find.
* The potential backdoor only becomes public knowledge in 2007.
* Daniel Brown writes in December 2013 that "I'm not sure if this was obvious." and "All considered, I don't see how the ANSI and NIST standards for Dual_EC_DRBG can be viewed as a subverted standard, per se.".
Certicom is the main inventor and patent-holder for elliptic curve cryptography. The two Certicom employees failing to warn or prevent the backdoor they clearly know was possible doesn't reflect well on Certicom.
Business Intelligence, for the purpose of corporate espionage. You also have to take into consideration that the NSA does answer to someone, and that someone was corporate sponsored before they were even put on a ballot to be voted on. They were put up to this, and continuance of the program likely has little to do with terrorism as the program has proven fruitless even after intelligence information was given about events prior to them being given/developing these tools but they in fact failed to respond accordingly to prevent them, this includes 9/11.
That's a fallacy. I choose what I share on social media.
No you don't. Social media sites like Google+ and Facebook vacuum up information about you from everywhere, even things you never intended to be made public like links you've clicked on.
Indeed -- you choose what you share on social media (to a degree), but most people aren't aware of the value of what they're sharing in the first place, and they have almost no control over what is shared about them. This is not the same as gossiping, as gossip involves the game of telephone -- there's no documented evidence that it's true. But when a date-stamped geolocated image of you in a nightclub shows up on your friend's blog with facial recognition indicating that it's you in the picture, and you called in sick that day, that's not gossip; that's evidence -- especially since that photo can then be flagged up for people who are following YOU (including co-workers and possibly your boss), even though you had nothing to do with the publication of the photo.
And this is before we get into whether your privacy settings have been changed by the service host since the last time you reviewed them, and whether others who don't need to honor those settings have found anything interesting in "your" files hosted in an international cloud server system.
If you choose to share nothing on social media, then at least none of the links can be verified, and it's closer to gossip. As soon as you start to share anything though, the metadata is enough of a net to snag all the bits of data about you that are published by others.