New NSA-Approved Encryption Standard May Contain Backdoor

Hugh Pickens writes "Bruce Schneier has a story on Wired about the new official standard for random-number generators the NIST released this year that will likely be followed by software and hardware developers around the world. There are four different approved techniques (pdf), called DRBGs, or 'Deterministic Random Bit Generators' based on existing cryptographic primitives. One is based on hash functions, one on HMAC, one on block ciphers and one on elliptic curves. The generator based on elliptic curves called Dual_EC_DRBG has been championed by the NSA and contains a weakness that can only be described as a backdoor. In a presentation at the CRYPTO 2007 conference (pdf) in August, Dan Shumow and Niels Ferguson showed that there are constants in the standard used to define the algorithm's elliptic curve that have a relationship with a second, secret set of numbers that can act as a kind of skeleton key. If you know the secret numbers, you can completely break any instantiation of Dual_EC_DRBG."

Re:umm

[Anonymous Coward]

This is the NSA, not the FBI.

Re:umm

[bhima]

But this is the NSA we're talking about... Not the Bush administration.

Re:umm

[niceone]

Either way best not use Dual_EC_DRBG.

And if it is incompetence, in this case the malice can come later if anyone ever figures out the 'secret numbers'.

Re:umm

[nuzak]

> Either way best not use Dual_EC_DRBG.

I'm pretty sure that if they backdoored one, they backdoored them all. Best to not use any of the new algorithms, period.

What part of "NSA Approved" don't you understand?

[second class skygod]

They're in the business of national security. That's generally at odds with personal security and liberty. Those who would trust such a product from them are suckers.

--scsg

Re:umm

[bhima]

How do you back door an Open algorithm you didn't design and don't distribute?

Re:One wonders what we can ever do right

[BlowHole666]

Well I know one thing that is not right...your thinking. Perhaps you do not know about how engineering works? When you design something you design it to the best of your ability. If you notice a flaw, you fix it. You try and prepare for all known and unknown problems, but you are not going to catch them all. You are looking at specific examples and not at the whole picture. Yes maybe the 787 was flawed, maybe the NSA's choice is wrong. But what have we done right? Well you brought up airplanes lets see. The B2 bomber, that has a good trace record. How about the F16 it has never been shot down. Maybe the Mars rovers they appear to be doing quite well, and lasting longer then expected. So yes you win some and you loose some. Thats why it is engineering. If you had all the answers and knew all the potential problems then it would be called following the directions.

Lock the Trojan Horse in a Stable

[Jeremiah Cornelius]

Strategy: Legerdemain.

1. Close the obvious backdoor.
   
2. Create the public perception that this has been dealt with - while the subtly flawed algorithms are used.
   
3. Profit!

Trust the Spies

[Doc Ruby]

The NSA is spying on all telecom signals passing through the US (including this message. Hi, Dick Cheney!). Despite the Constitution's prohibitions. Why would you trust them not to make your crypto crackable?

This situation shows one of the strongest arguments for open source. Trust no one.

Don't trust any encryption

[FranTaylor]

Sessions can be recorded and cracked later when cpu is even more plentiful.

Encryption keys can be demanded by the government, they'll throw you in jail for not complying.

Keep your dirty laundry out of your computer.

The government doesn't think that your data is something that should be protected from unreasonable search, you shouldn't either.

Re:The answering machine

[Shakrai]

Anyone else reminded of the little Black Box from Sneakers? The one that used a mathematical backdoor to break any encryption based on a certain algorithm that was only used in the USA?

More to the point, anyone else remember the premise of that movie? That said black box was utterly useless for doing anything other then spying on Americans, which (prior to Dubya anyway) was outside of the NSAs mandate.

Re:Ummm...encryption standard?

[starfishsystems]

Randomness is absolutely at the heart of cryptography. So yes, to answer your question, it does matter.

If I can predict the value of a symmetric key, or the value whose two factors constitute an asymmetric key pair, I have effectively broken the encryption. Even supposing that I can't do this deterministically, but merely somewhat better than random, I'm still that much further ahead.

Re:What part of "NSA Approved" don't you understan

[kebes]

They're in the business of national security. That's generally at odds with personal security and liberty. Those who would trust such a product from them are suckers.

The problem is that this flaw is a much bigger threat to national security than to personal security. These "official recommendations" from the NSA are used to form official policies and guidelines in just about every branch of government (FBI, CIA, DOD, etc.).

So, if the NSA was indeed intentionally creating a backdoor, then they were doing a disservice to the "national security" they are supposedly protecting. By allowing (encouraging, in fact) top-secret government data to be encrypted in this way, they would be making the nation's secrets quite vulnerable. By comparison, private citizens and corporations can use whatever encryption they like, regardless of NSA recommendations.

I suppose one could argue that the NSA thought that no one would figure it out, so that they (and they alone) would be able to break that encryption for all time (so that they can spy on other branches of the government?). I think a simpler explanation is that NSA just made a mistake in endorsing that algorithm, and never intended to threaten national security. Of course it will be interesting to see what position they take now that a flaw has been publicly identified.

Not the same thing

[Moraelin]

It's not the same thing. For a start, it's not even necessarily software. It's a mathematical algorithm.

So, yes, the implementation can be buggy, but for something like cryptography you'd at least expect the maths behind it to be rock-solid.

A lot of cryptography is based on stuff like that it's _far_ easier to multiply two prime numbers, than to find out which two large primes are the factors of a very large number. (I don't know this particular algorithm in TFA yet, so I used RSA as a simple example.) Once some maths guy has figured that out, and how it can be used, then the actual implementation in software tends to be actually very simple and straightforward. You just do one operation over and over again to encrypt the stuff, and another operation again and again to decrypt it. So even an error in the implementation is pretty inexcusable, because it's not a lot of code and you have a step-by-step description of exactly what to do.

Usually when an error in the implementation happens, it's not as much a programming bug, as the fact that (again) someone didn't understand the underlying maths and principles. E.g., I vaguely remember a disk encryption program which used a secure algorithm, but... had an invariable and huge block of known text at the beginning of it, which meant it was crackable anyway.

Anyway, to get back to the important part: it's not software, it's maths. Pure old-fashioned maths.

And... well, I'm not saying that that maths is easy. The average code monkey trying to invent encryption _will_ come with something ridiculously easy to crack.

But I'll say this: if the best and brightest mathematicians the NSA can find, still aren't competent enough, then I'd worry about the USA. I'm not even an American, and my attitude is somewhat anti-American (or at least anti-Bush), but even I in my crankiest hour wouldn't have _that_ bad an opinion of the USA.

To put it in perspective: something like this isn't like your average piece of code that someone typed on a Friday afternoon and never bothered to test. Something like this is bound to be reviewed by at least 2-3 other pairs of eyes before it becomes an official spec. So if they simply couldn't find anyone qualified enough to review it... I'd worry. A lot.

The conspiracy theory there is actually the _far_ more flattering alternative.

Re:Ummm, parent is right.

[failedlogic]

If you find out the episode, please reply to this thread. I'd be interested in watching it (and its likely on Youtube which will make it easy to watch or my public library will have it).

Re:I can't be the only one:

[jbf]

Well I'm not surprised. Microsoft Research has tons of sharp security guys working there. Niels Ferguson is quite well-known in security circles. You don't get your company's name as an "author" unless your employees actually did the work; funding is not good enough. It might annoy the NSA, but academics don't care that much.

Re:umm

[sacrilicious]

Don't look for malice where incompetence will do.

Don't tolerate incompetence.

Especially when the party involved should know better, and when there's a lot at stake.

Doesn't work

[Sycraft-fu]

Again, because we are talking about public algorithms. Things like this are public, open algorithms. Anyone can evaluate them, as Bruce noted. As such you can't "hide" something in there unless you are waaaay better than anyone else. If that is the case, well then why bother with any deception in the first place? This isn't a "This is a black box just trust it." It's an open algorithm and any experts can look at it, as has happened.

Re:Ummm, parent is right.

[Bearhouse]

Agree with both.

1. CIA=sharp, Academe=smart. The NSA boys are both smart and sharp. They've got the budget.
Wonder when the 'super brains' from Google will get into crypto? They have the market cap now - thanks to the inexplicable hype over Android...
2. Yup - I tend to metamod the -ve mods as 'unfair', because they seem to be driven by bigotry than than sense.

So, inserting one trapdoor? Likely, but not probable. Insert an easy one to find, so we miss the others...now that's smart 'n' sharp

No, it *does* have a backdoor

[peacefinder]

I thought the article was saying something slightly different: The standard does have a backdoor, it's just not clear who - if anyone - holds the keys.

The safe assumption is that someone does hold the keys and therefore the standard is useless for cryptography, even though it might be just fine for other applications.

Re:Ummm...encryption standard?

[peacefinder]

starfishsystems gives a good answer, but I'll say it a bit differently in case it helps.

The random number generator in question is a mathematical tool for generating randomness, not a cryptosystem of any kind. It has many potential applications. However, modern cryptography is absolutely dependent on high-quality randomness, so cryptosystems tend to use exactly this sort of tool. The thing is, if the "random" data stream one uses in a cryptosystem is actually predictable, then the whole cryptosystem is insecure right from the start no matter how good it otherwise appears.

It's is very much analagous to building a house on sand: if the foundation is unstable, it pretty much doesn't matter how good the rest of the construction on top of it may be; the whole structure is in dire and immediate peril.

The random number generator itself may be just fine for many applications. However, any cryptosystem built on this random number generator is presumed to be useless just because there exists a set of keys which can easily predict the whole random number stream given a tiny part of it. We don't actually know if anyone holds the keys, but if someone does then that person could undetectably open any cryptographic locks built on this random number generator, or release the keys so everyone could open the locks.

That help?

Re:Ummm, parent is right.

[bjohnson]

CIA=sharp???

Uhh, go read "Legacy of Ashes" and weep. http://www.randomhouse.com/doubleday/legacyofashes/ [randomhouse.com]

Yes, there are smart people who have worked for the CIA, but they've been lead by clueless frat boys drunk on power and prodigious quantities of booze.

Suffice it to say that anything the CIA as an agency has done right it's been entirely by accident.

Re:What part of "NSA Approved" don't you understan

[logicnazi]

Using the backdoor requires solving a discrete log problem. The NSA may have an actual proof of hardness for these problems putting a minimum bound on the amount of computer power required. This in turn might give them a minimum bound of a decade or so (someone really needs to check just how hard this discrete log problem turns out to be) for anyone else to discover the secret keys and they can just announce finding a security flaw in the algorithm 2 years before anyone might have found the keys.

Supposing they have separate classified advice for top secret material and this RNG will only be used on low security documents the tradeoff between an enemy potentially having access to low security information from several years ago and giving them potential access to other people's communications might be favorable.

Still, the problem with this scenario is that it seems implausible that they were ever going to get widespread adoption of this RNG outside the government. Then again many things agencies do can't be explained by smart people behaving reasonably. Maybe some mucky mucky over at the Bush admin got a bug in their britches about us helping the terrorists when they found out that they were using strong encryption the NSA had helped strengthen (like DES) and ordered them to start putting in back doors ignoring arguments to the contrary.

I can certainly see the 9/11 changed everything attitude justifying this sort of crap to some self-righteous and idiotic official.

Re:Ummm, parent is right.

[Anonymous Coward]

It's spelled "contractor". And you've never been in the NSA's building. They use ACLs tied to biometric data everywhere.

Re:Things we know we don't know.

[Anonymous Coward]

One quite reasonable explanation is that yes, getting this particular set of numbers requires solving a discrete log problem. However, NSA has determined that not all discrete log equations are equally easy to solve, and now they're advising to basically shun the insecure variants and take one they know is more secure. They can't prove it in public, because the whole discrete logs on elliptic curves stuff is supposedly not cracked at all.

This would fit in with the previous S-boxes for DES and the bitshift for SHA-1. Wikipedia is quite explicit on the fact that the sceurity of elliptic curve cryptography is critically dependant on the curve selected; the NSA may simply have found more easy cases.

Re:Ummm, parent is right.

[aproposofwhat]

I think the point of Schneier's article is that everybody (i.e. everybody who means anybody in terms of cryptoanalysis) has crawled over each algorithm, and there's only one that has failed the peer review.

It's somewhat surprising that an algorithm with a documented flaw made it through to the standard, but Schneier makes it clear that the NSA pressured NIST to let it through, so there are grounds for concern.

Re:Unbreakable encryption

[Skippy_kangaroo]

That isn't really encryption is it. The raison d'etre of encryption is that someone else can recover the message following a defined process.

If I take a signal and add random noise to it then remove all references to the specific random numbers I won't be able to recover the original signal. That's not encryption - that's more like shredding and burning.