Dual_EC_DRBG Backdoor: a Proof of Concept 201
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"
Another view on teh RSA / NSA thing... (Score:5, Informative)
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....
Re:YES! (Score:2, Informative)
Good article (Score:5, Informative)
The link above [0xbadc0de.be] 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.
Re:is RSA soon an open vault? (Score:5, Informative)
It seems to me that anything we thought were encrypted and could be, and was, considered secure in that embodiment, is soon subject to revelation. I'm no expert, but I'm losing faith in these algorithms. Please tell me it's going to be okay. PS: if you are NSA, I don't need your reassurances.
Don't worry. It was known for quite a while that this algorithm _might_ have been backdoored. There are basically three possibilities:
1. The NSA didn't know that it could be backdoored when they created it. So there is no backdoor, and the NSA is kicking themselves for that missed opportunity, or for the embarrassment. 2. They knew about it, but intentionally didn't create a backdoor. 3. They knew about it and created a backdoor.
From looking at the algorithm, we cannot possibly know which one is the case. Obviously it would be totally insane to use this algorithm. But that _was_ known for quite some time.
FIPS (Score:5, Informative)
FIPS is a large group of standards - literally, the Federal Information Processing Standards. Any requirement is not "mandated by FIPS", it is mandated by one particular standard - which may or may not apply to any contract.
FIPS 140-2 Annex C, for one, lists quite a few acceptable random number generators; for that standard, I see no requirement for Dual EC DRBG.
Re:FIPS (Score:5, Informative)
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)
Re:How long until someone cracks the backdoor key? (Score:5, Informative)
Actually read TFA, enough flew over my head that I can't personally verify the math, but if true, well holy fucking shit. Once someone brute-forces the backdoor "key" used by the NSA, it looks like the entire system is cracked. Even if it takes a while to brute-force, once you have that you can open any encryption using that curve.
It's quite possible that this cannot be brute forced. The only way is to create the back door at the time that the random number generator is created. In the end, that is the _first_ requirement: That an arbitrary attacker, given a complete description of the algorithm, cannot brute force it.
Re:How long until someone cracks the backdoor key? (Score:5, Informative)
(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 [ietf.org]
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.
More interesting facts (Score:5, Informative)
I have been adding various facts to the Wikipedia article on Dual_EC_DRBG [wikipedia.org]. 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 [ietf.org] 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.
Re:How long until someone cracks the backdoor key? (Score:4, Informative)
It's quite possible that this cannot be brute forced. The only way is to create the back door at the time that the random number generator is created. In the end, that is the _first_ requirement: That an arbitrary attacker, given a complete description of the algorithm, cannot brute force it.
From what I understand the whole point of algorithms like this is that brute force is the only option (without knowing the key). If there was some other mathematical way of determining the key the hackers would use that; so the goal is to create an algorithm where the secret key has to either be known, or brute forced. The only way to find the secret key is to literally try every possible number and hope that the computer stumbles across the right one eventually.
Re: The maths is easy for a fifth grader (Score:2, Informative)
Incorrect.
Randomness will assume a gaussian curve distribution, given enought samples, over sufficient time.
A generator algorithm that produces a uniform flat distribution would expose predictable patterns in output that could be exploited.
Re:Good article (Score:4, Informative)
Just to add to this, if you want a good primer on Elliptic Curve Cryptography in general (and not just this exploit), this article from Cloudflare is pretty great even if you don't have a mathematical background. It also explains RSA quite well, so it's a good general crypto primer:
http://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography [cloudflare.com]
Re:YES! (Score:5, Informative)
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.
Re:How long until someone cracks the backdoor key? (Score:4, Informative)
From my understanding, the ability to have *a* backdoor is a quirk of the math, but the "key" depends on the parameters of the elliptic curve. Those parameters for this specific implementation were written by the NSA (under the guise of their mandate to secure American communications) and standardized by NIST. TFA had a full proof of concept using parameters he had generated, which worked.
Re:More interesting facts (Score:5, Informative)
> In short, as is the case with many conspiracy theories all you have is a collection of things that are suggestive, not definitive.
When you design a standard, one of the design criteria is that it does not allow for even a potential a backdoor. See fx https://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number [wikipedia.org] . It is most definitive that Dual_EC_DRBG should never have been approved given the knowledge available at the time of how to prevent any possible backdoor.
Re:How long until someone cracks the backdoor key? (Score:4, Informative)
If its not doable how then did NSA supposed to have done it? Its not like they came up with the key at random then invented this algorithm to fit it, the fact that there is a backdoor key is a quirk of the mathematics.
It's basically public-key crypto: you can create a keypair and publish the public key - that's essentially what this is, where the point Q in the Dual_CD_DRBG spec is really just a public key. There's a private key as well - it's far to expensive to compute it from the public key (basically 2^128 time), but they didn't have to do that since they generated the private key first.
And it's really not a "quirk of the mathematics" - it's really pretty straightforward if you understand elliptic curves, and it has been well-known how to do this since 2007 or earlier. I think a lot of academic cryptographers didn't really worry about it when Shumow and Ferguson pointed out the potential backdoor, because it's really a pretty crappy technique anyway - academic cryptographers, who quite frankly often don't know what is used in practice, assumed no one would use this. Then it turns out that RSA used it as the default tehnique in BSAFE. Oops.
Re:Bah (Score:2, Informative)
That "stolen credentials" story seems to be widely circulated but not much anchored in evidence. In fact, probably was originated from some NSA insider to discredit Snowden. A more detailed report to what happened comes from an article from Ars Technica. A very good read, by the way:
The National Security Agency’s oversharing problem
http://arstechnica.com/information-technology/2013/12/the-national-security-agencys-oversharing-problem/ [arstechnica.com]