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.
Can you still read the linked article? Or am I not allowed? I can't tell anymore what is allowed under the law and what isn't, since the US Gov feels free to interpret the law as it chooses.
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.
And some people generate new key pairs
People use something else, until a new scandal crops up.
Meaning what? That encryption was good enough to keep likes of the NSA out even with their resources, and so they compromised it?
Or something even more insidious.
"If any question why we died, Tell them because our fathers lied."
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.
Does this mean that OpenBSD has suffered a 3rd remote hole in its default installation? (http://it.slashdot.org/story/07/03/15/0045207/remote-exploit-discovered-for-openbsd)
(I don't understand the implications of Aris' blog above, so I'm hoping someone can explain it to me & other OpenBSD users.)
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.
Currency implosion, wouldn't worry so much about your paychecks not cashing, the oil peddling masters balls that you've been licking is contaminating water aquifers and rendering US soil uninhabitable so there won't be much food grown or water to drink to buy with a paycheck that doesn't cash anyway, genius.
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
They are us. Some really bad people are slightly inconvenienced as a side-effect, but are by no means stopped (See: Tsarnaev brothers, zero evidence of attacks stopped by the NSA).
"When information is power, privacy is freedom" - Jah-Wren Ryel
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.
Dual_EC_DRBG is *not* mandatory under FIPS 140-2. As of today (January 1), some of the older RNGs are no longer permitted for new FIPS validations, effectively leaving you with only SP800-90A (DRBG). However, there are four different DRBGs contained within 800-90A. Nothing says you need to implement all four of them. One is good enough. Out of the four, only one of them (Dual_EC) is considered suspect.
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
That's a fallacy. I choose what I share on social media. Granted, I can't control what other people share about me, but that was just as true before social media; we just used to call it gossiping. That's why you have to be careful who you trust with things that you consider secret—keep your secrets secret and all that.
Check out my sci-fi/humor trilogy at PatriotsBooks.
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.
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
mod this isnightful.
Moderating "-1, Disagree" is simple censorship. Have the guts to post your opinion. -- Spazmania (174582)
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!
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.
Which to the NSA is useless information overload, with RSA keys being easily hacked it leads down a completely different path than the average Joe on the net, I would think that the NSA is much more interested in targets of value. The fact is most people who use Google+ or Faceplant have nothing of any real value to be had especially for security agencies. If you are a consumer and all of a sudden your posting habits make advertising money for Brin and Zukerberg who gives a rats ass. Here we are with a bunch of so called information gurus telling us that are consuming habits are a valuable commodity. Personally I listen to Igor Stravinsky and if in watching and listening to a youtube vid suddenly Google comes back and advertises a concert somewhere of a performance of Le Sacre Du Printemps then good for them.
AND BY THE WAY nice shift off the topic and away from the bastards at the NSA subverting RSA keys and a not so cunning redirect to attack instead Google services as being somehow associated with the information sink hole in Washington that is the NSA.... If however I frequent neo nazi sites and post hate speech on the net then as far as I am concerned being on the radar of the NSA is not that bad a thing...UNLESS OF COURSE I AM A MORON WHITEY TIGHTY BORN AGAIN NAZI MYSELF OR A CLOSET TERRORIST.
However being much more concerned about my bodily fluids and essences, instead I am against the fluoridation of our precious water and bodily fluids. The encryption key is found in PURITY OF ESSENCE from which all things will be revealed. GOOGLE IS EVIL DON'T FORGET IT only through the use of Microsoft Windows and Bing can true encrypted PURITY OF ESSENCE be acheived. RSA keys the NSA have absolutely nothing to do with this thread. WOOOF
This message was not sent from an iPhone because Peter Sellers really was a deviated prevert without a dime for the call
If you use more than 1 sequence of randomness while using the required standard, is that code viewed as compliant?
No, not really - and as I was writing it I thought "I bet someone's gonna bring Moore's Law into this and then I'm going to have to explain". So I'll explain - the 50,000 years was a figure thrown out there. Really, as long at time taken > life expectancy, OP won't be able to find a result. The actual time to perform that many encryption cycles would be in the millions of years. If Moore's Law progresses over time that would certainly be brought down, but not within OPs lifetime. Then you've got to compare the data set. Nevermind that physically storing that many 32-bit strings would take more atoms than exist on our planet. The point was simply that OPs suggestion was ridiculous.
"The true measure of a person is how they act when they know they won't get caught." - DSRilk
We could also brand the asses of the sanctimonious jackasses around here who feel the need to impose their versions of integrity and morality on the rest of us. You and your ilk are assholes and, like all those who claim to own the high moral ground, are not as relevant as you think you are. But, you are smarter than most; all we need to do is just ask you.
We need another 15 stories of stale news about "teh NSA is bad; Snowden is a saint" so that you and the hive can express your indignation and outrage and thus make yourself feel superior to those you like to call "the sheeple."
By that definition even this is random:
int rand()
{
static int seed = 0;
seed++;
return seed;
}
Outputs full range of values? Check!
Must be random.
I'll stick with twofish,or AES256 for my openssl and gpg stuff.
Uh, Linux geek since 1999.
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?
Did you ever stop to think that the "sanctimonious irrelevant jackasses" around here might be striving for "sadistic prick of the year" when it comes to subject matter being discussed that attacks the integrity of their work?
Isn't that what they're already doing?
http://arstechnica.com/security/2013/12/nsas-broken-dual_ec-random-number-generator-has-a-fatal-bug-in-openssl/
Uh, Linux geek since 1999.
Isn't FIPS something that has a legal requirement to be secure? Doesn't this by extension invalidate the security of FIPS?
http://www.gnupg.org/documentation/manuals/gcrypt/Random_002dNumber-Subsystem-Architecture.html#Random_002dNumber-Subsystem-Architecture
Uh, Linux geek since 1999.
Correct. But you do not choose what is shared about you on social media. Which is what actually matters.
http://en.wikipedia.org/wiki/RANDU
The NSA is so busy building a haystack in which to search for needles, it misses the 100 ton girders with a Vegas scale neon sign pointing right at them.
What changed under Obama? Nothing Good
If they aren't already, now would be the time to start putting the masses to work hunting down the NSA's special key. This is a nasty one, and the sooner we can use it to bludgeon the guilty parties the better.
Women are like electronics: you don't know how damaged they are until you try to turn them on.
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.
Good point.
Uh, Linux geek since 1999.
True, good point.
Uh, Linux geek since 1999.
OpenSource has nothing to do with it. Here we have (allegedly) a set of carefully crafted constants used in a crypto context. Without knowing why those specific numbers where chosen, or that they are, in fact, not "weak", everything using them, open and closed, is suspect.
(I would tend to agree the NSA -- having had their hands all over the thing -- do know the secret relationship between P and Q.)
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.
Which to the NSA is useless information overload....
OK: first, you quoted the GP, who had a good point in responding to the GGP.
Second, NSA doesn't need to deal with this info directly, because Google and Facebook already do. They can just intercept the aggregate metadata, and drill down as needed, as they know where to go for the details. How do you think they know how to serve these companies with information requests? They already have the metadata, and can use it to request the information stored by others. Why is this pertinent to the topic? Because to intercept the aggregate metadata, they have to break the encrypted streams -- which often involves FIPS-regulated transactions, which means Dual EC DRBG is possibly a default seed, especially on RSA-based products.