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"
Who can you trust?
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....
Someone creates an angry blog post and someone else submits a petition to change.org. Then nothing.
xorshift64 is a simple random number generator with a period of 2**64 - 1 (you cannot use 0).
The 64 bit random number that it produces is the same as its complete state.
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.
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 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.
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.
Given that cracking this open would be so useful to both other monitoring agencies, and to criminal hackers, it's sure to happen eventually, if it hasn't already. I'm sure China could throw one of their supercomputers at it.
I'd be curious to know just how hard it would be to brute-force the backdoor key itself. There didn't seem to be anything in TFA about that, and I can't figure out the math myself.
Please, people who understand EC properly, verify & reproduce this ASAP. If so this is yet another thing (one the BIGGEST things) the NSA has denied about the content of the Snowden leaks.
Plus RSA needs to really step up and be honest about just what occurred inside their walls wrt. FIPS and this algorithm.
At this point, I think the longstanding rule that 'only a fool writes his own crypto' is getting weaker.. I would amend it to "only a fool writes his own crypto, or uses ones supplied by anyone without full, independent audit and full control over magic constants..."
Captcha: bilked
No, because OpenBSD doesn't just use this PRNG as the source of randomness for its encryption implementations, it has used other sources mixed in for a long time. There was a recent story about FreeBSD switching to other sources and De Raadt being all cocky about other people finally doing what OpenBSD has done for years.
that particular bug you link was fixed a week before it was found to be security vulnerability (at the time was known to cause crash)
http://marc.info/?l=openbsd-misc&m=117404837006368&w=2
Philip Zimmerman, PGP. Older versions 6.5.8 might be okay, something open source. However there is all this worthless security infrastructure in place already that has been rooted. There needs to be compensation for fraud.
For a start, we could at this point reasonably demand that everyone who has accepted a salary from NSA be branded on the forehead with a scarlet letter, so that anyone with any sense would know not to hire them for any position involving trust. Let them work as street sweepers. As persons who sort garbage into different recycling streams. We know these persons cannot be trusted. Identify them, remove them from their current jobs, and place their names on a very public list of persons who cannot be entrusted with anything, in any endeavor.
There needs to be some amount of personal responsibility in the NSA, yet with the obvious exception of Snowden, there is no evidence of any such thing. One good place to start is to hold those who were involved in creating this monster accountable for ethical / moral turpitude.
Will
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.
You moron. My PGP encrypted email passes the Diehard tests for randomness -- Doesn't mean it's actually random bits.
But looking at it from a motivation standpoint, only option 3 would be worth paying $10 million for.
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.
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.
And when you're done in 50000 years with our current supercomputers, let us know the results. The number of possible combinations is a bit over 170141183460469231731687303715884105728. Good luck with your bubble-sort.
"The true measure of a person is how they act when they know they won't get caught." - DSRilk
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.
So, they introduced a backdoor into software that can be/is used to secure US nuclear secrets, in the hopes only they would be able to take advantage of it? This is just another variant of "security through obscurity." Really, really fucking stupid!
How many people work at the NSA? How many of them are involved in eavesdropping programs aimed at US citizens? Why don't we just make it easier and brand all government employees? Or all Americans?
I trust Bruce Schneider. If he's a sleeper agent, they've put in so much effort it would seem churlish not to use him.
And really, I'd use Blowfish ahead of any NSA encraption algorithm or LOL AES. If history has a sense of irony, China will pwn the entire US IT infrastructure using NSA backdoors.