Slashdot Mirror
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."
Don't look for malice where incompetence will do.
-- NapoleonAny guest worker system is indistinguishable from indentured servitude.
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?
End of lesson. You may press the button.
Is what is essentially a random number generator really an 'encryption' standard? And if it's really a backdoor, don't you still need to know rather quite a bit more than the random number seeds to break something like AES or RSA?
My blog
On the last slide, the researchers add some suggestions:
secret numbers appearing on T-shirts in Finland in 3.. 2.. 1..
- For the complete works of Shakespeare: cat
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
"It's possible to implement Dual_EC_DRBG in such a way as to protect it against this backdoor, by generating new constants with another secure random-number generator and then publishing the seed. This method is even in the NIST document, in Appendix A. "
Should use the one that is hardest to break. If the NSA thinks elliptic curves are the best, only the NSA should use it. Let's see how happy they are having their own "unbreakable" code just for them.
Personally, I wish the NSA was a bit more chivalrous when it comes to these kind of things. If it is your **JOB** to break codes, why whine when people pick the one that is hardest to break. The rest of the world doesn't have the luxury to pick how hard their job gets to be, so why should you?
The NSA is like an anti-virus / a pharmaceutical company where a cure is only good if it's in the company's best interests. Not to say that anti-virus / pharmaceutical companies are not ethical. But there is a saying along the lines of "If you can't come up with the solution, there is good money to be made in the problem."
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.
I smoked pot once. But I DID NOT inhale. Will you hire me?
"Flyin' in just a sweet place,
Never been known to fail..."
That would explain why SELinux isn't widely used.
-- This space for lease, low setup fee, inquire within!
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.
--
make install -not war
Read the post above. Getting the key involves solving a discrete log problem for one instance of an elliptic curve. Discrete log problem is an unsolved mathematical problem. So its solution essentially (you mileage may vary slightly) requires brute force. Either NSA has a solution and was hoping the weakness would go unnoticed, or they don't have it. If they don't have it, no one will have it for a long time. These are more difficult to compute (and therefore more time consuming) than the traditional encryption schema (discrete log problems for Z/pZ). Now the question of whether you believe malice or incompetence is at play here is essentially up to you.
Any guest worker system is indistinguishable from indentured servitude.
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.
I can't be the only one who clicked on the link and was astonished to see:
"On the Possibility of a Back Door in the NIST SP800-90 Dual Ec Prng - by Dan Shumow, Niels Ferguson, Microsoft"
Microsoft are exposing this? Are they funding the group making these kind of claims? If this was true, wouldn't this intensely annoy the NSA to have this exposed? Am I missing something here? .
- I see the disclaimer ("What we are NOT saying") where they seem to be saying - "No way did the NSA intentionally make this broken - maybe it was an errant developer and maybe they knew what they were doing", but it amounts to the same thing, surely?
'This writing business. Pencils and what-not. Over-rated if you ask me. Silly stuff. Nothing in it' - Eeyore
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.
I wish I could remember the show I saw. But the scientist (MIT, PhD scientist) was amazed at the intellect of the NSA folks who came to see him about his research. I can't remember who it was - it was a NOVA episode (but it stuck in my head because of his fear!). And after talking to friends who work with various internet security companies and defense contractors, I have to reiterate their opinion of these guys - they're really sharp. And as much as I like to disparage Government workers, these guys aren't to be trifled with.
And, as I was previewing, I noticed that the parent was moderated "Offtopic".
As an Offtopic note: 2 out of 3 down mods that I meta mod are unfair. Keep that in mind. It's really pissing me off.
I prefer Flambe as apposed flamebait.
The NSA is a lot more competent than you think.
:-P
Go google "NSA DES" sometime.
"The NSA was embroiled in controversy concerning its involvement in the creation of the Data Encryption Standard (DES), a standard and public block cipher used by the US government. During development by IBM in the 1970s, the NSA recommended changes to the algorithm. There was suspicion the agency had deliberately weakened the algorithm sufficiently to enable it to eavesdrop if required. The suspicions were that a critical component -- the so-called S-boxes -- had been altered to insert a "backdoor"; and that the key length had been reduced, making it easier for the NSA to discover the key using massive computing power, although it has since been observed that the changes in fact strengthened the algorithm against differential cryptanalysis, which was not publicly discovered until the late 1980s."
So they made some small changes to DES... then a *decade* later, the rest of the crypto world says, "Huh. We've just done the sums and that actually made it better."
Not to say that in this case they're just screwing with the algorithm though
You are in a twisty maze of processor lines, all alike.
There is a lot of hype here.
The crypto community spoke out strongly against it, and the proposal, despite having a great deal of political muscle behind it, did not fly very far. Another sensible reason for its failure to gain acceptance was that it would have had no chance of success on the international market. Even if domestic use could have been forced through legislation, let's say, no other nation with a clue would pick it up.
Parity: What to do when the weekend comes.
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.
A polar bear is a cartesian bear after a coordinate transform.
I see how it could be a problem for embedded work. But on personal computers, which nowdays have tremendously abundant resources, why not use multiple algorithms and entropy sources to build your pool? (Yes, I know some systems already do this.) NSA may be able to predict one sequence, but they sure as hell can't predict a bunch of them, XORed. They'd need mathematicians to crack all the RNGs, have a camera on your lava lamp, a microphone listening to the room, a tap on your power line, etc. By the time they do all of that, they might as well have just asked you what your plaintext is.
As copyright owner of this comment, I authorize everyone to defeat any technological measure which limits access to it.
There is another explanation; difference of opinion between management and staff
- Management wants a backdoor in public standard, orders their very smart math geeks to make it so
- Math geeks say it can't be done
- Management insists
- Math geeks go away and come up with something out of left field that technically fulfils the request of management, knowing it's vulnerabilities. They probably tell management that their solution is the best they could do, but it still has all the following problems (slow, crypto-nerds will see through it sooner or later, etc)
- Management hears the 'best' and 'done' part, discounts possibility of anyone outsmarting their 'uber-elite' NSA math geeks
predictable results follow.
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.
In my final year in CS, I wrote a lengthy paper researching various DRBGs. To my surprise, there were very few good candidates for cryptographic DRBGs, but of the 7 I looked at, Dual_EC_DRBG rated the worst. I was unable to find any theoretic proofs for Dual_EC_DRBG, but I did find a few papers exposing serious flaws in Dual_EC_DRBG including this one which describes a tractable distinguisher so efficient it can run on a modest desktop.
The other three DRBGs recommended by NIST were all reliant on the security of various other cryptographic primitives such as SHA (Hash_DRBG), HMAC (HMAC_DRBG - which is often based on SHA) and AES or 3DES (CRT_DRBG). They were all reasonably obvious, and only really tried to set out some sort of standard for jumbling the output of their respective primitives enough that they would be resilient to any unknown vulnerabilities in said primitives (though certain paths also failed to do this). This was mostly accomplished by calling the primitives several times (HMAC_DRBG with the NIST HMAC implementation called for 6 SHA hashes per SHA sized output) which isn't very efficient.
I suspect they only included Dual_EC_DRBG because it wouldn't have looked too good if they were unable to come up with a single number theoretic or otherwise novel DRBG. They shouldn't be too disappointed, however, as the only one I was able to find was Blum Blum Shub which is terribly inefficient. CryptMT (Cryptanalysis) also deserves a mention as it looks like a promising pseudo-number theoretic DRBG, at least a better candidate than Dual_EC_DRBG.
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.
With reasonable men I will reason; with humane men I will plead; but to tyrants I will give no quarter. -- William Lloyd
bhima's comment was alluding to the fact that while NSA designed and distributed the Dual_EC_DRBG algorithm, they had no part in the other two algorithms (that we know of) other than as an outside commentator, and thus could not put a backdoor into them. In other words 'you' referred to the NSA, not to you, a user of the algorithms.
Open source alone is not enough. In fact these algorithms ARE open source. There even public domain standards!
Crypto is a special case. While it's true that "open source" cryptographic algorithms/protocols tend to be far safer choices then proprietary/secret/home-brew algorithm the problem is that correctness of a cryptographic algorithm is a far stronger notion to achieve and verify then for a normal program. For a normal program "correct" implies producing the right out put. In a cryptographic setting we want the the "correct" output which must be "secure". Precisely understanding the meaning of "secure" for a given app. and context is a central concern of cryptographers.
What is needed for crypto is the next step beyond open source, namely open process. That is along with an algorithm the NSA (or NIST or IBM or whoever) should be publishing a complete security definition, analysis and reasoning behind the design choices. (See The Making of Rijndael for example.)
If the NSA had provided ANSI, NIST and the public with such documentation then the problems pointed out by Shumow and Ferguson would not exist. The reasoning behind the choice of all constants would be clear to all.
On a realistic note it's not exactly likely that the an organisation like the NSA would ever do such a thing. Take the case of the DES algorithm developed by IBM with help from the NSA. Only a decade later later when Eli Biham and Adi Shamir published their work on Differential Cryptanalysis did the reasons for the choices of constants in DES become clearer. However at the time of DES's creation this (very powerful) cryptanalytic method was not known to the public. Thus by demanding open process the NSA would effectively have been required to release what was probably one of their most guarded technological advancements.
Thus since it can not be expected that the NSA adhere to open process development I think our best bet is to simply go with another algorithm which does. Like rijndael for example...
The thirty-year-old F-15 has been "defeated" during exercises with allied powers, flying planes developed twenty-five years later that are it's equal in technology, with pilots as well trained as ours.
The US free market: two halves of a government-granted duopoly are free to set the market price.
Hardware manufacturers? How about certificate authorities?
If any of you think this is the least bit specious, the VeriSign website proudly proclaims that they will subcontract to telcos/ISPs that are ordered to eavesdrop in a "legal intercept" capacity. There is no other reason for VeriSign to be in that line of work unless they are using their ability as CA to stage undetectable MITM surveillance attacks.
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.
If you liked this thought maybe you would find my blog nice too:
Why not use the encryption as-is, but swap out the random number generator with something else?
I've always wondered why random number generators don't pull values from an A/D converter hooked to a white noise generator or Lorenz attractor or some such.
Weaselmancer
rediculous.
Kudos to Bruce Schneier for being a respected voice of reason and (seen to be) a disinterested party to critically analyze the strengths and weaknesses of what will be a backbone of computing (and, indeed, our daily lives).
If I were the NSA trying to work in a back door, instead of coming up with a subtle flaw in the algorithm, I'd get Bruce Schneier to publicly praise an algorithm known to have flaws, while simultaneously offering to pay him a gajillion bucks and threatening his family if he refuses. That would probably derail publicly available encryption for a while. ("Bruce Schneier recommends: WinCrypt Terrorist Edition!")
404555974007725459910684486621289147856453481154 in hex is "You sank my Battleship?"
[GPG key in journal]
Would that be Kryptos?
guru in training
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.
"Mr. Potato Head? Mr. Potato Head! Back doors are not secrets!"