Slashdot Log In
New NSA-Approved Encryption Standard May Contain Backdoor
Posted by
Zonk
on Thu Nov 15, 2007 01:21 PM
from the find-out-by-knocking dept.
from the find-out-by-knocking dept.
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."
Related Stories
[+]
NIST Opens Competition for a New Hash Algorithm 187 comments
Invisible Pink Unicorn writes "The National Institute of Standards and Technology has opened a public competition for the development of a new cryptographic hash algorithm, which will be called Secure Hash Algorithm-3 (SHA-3), and will augment the current algorithms specified in the Federal Information Processing Standard (FIPS) 180-2. This is in response to serious attacks reported in recent years against cryptographic hash algorithms, including SHA-1, and because SHA-1 and the SHA-2 family share a similar design. Submissions are being accepted through October 2008, and the competition timeline indicates that a winner will be announced in 2012."
[+]
Cryptography Expert Sounds Alarm At Possible Math Hack 236 comments
netbuzz writes "First we learn from Bruce Schneier that the NSA may have left itself a secret back door in an officially sanctioned cryptographic random-number generator. Now Adi Shamir is warning that a math error unknown to a chip makers but discovered by a tech-savvy terrorist could lead to serious consequences, too. Remember the Intel blunder of 1996? 'Mr. Shamir wrote that if an intelligence organization discovered a math error in a widely used chip, then security software on a PC with that chip could be "trivially broken with a single chosen message." Executing the attack would require only knowledge of the math flaw and the ability to send a "poisoned" encrypted message to a protected computer, he wrote. It would then be possible to compute the value of the secret key used by the targeted system.'"
This discussion has been archived.
No new comments can be posted.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
Full
Abbreviated
Hidden
Loading... please wait.
umm (Score:5, Interesting)
Don't look for malice where incompetence will do.
-- NapoleonRe:umm (Score:5, Insightful)
Parent
Ummm, parent is right. (Score:5, Interesting)
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.
Parent
Re:Ummm, parent is right. (Score:4, Insightful)
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
Parent
Re:Ummm, parent is right. (Score:4, Funny)
Turns out Vista doesn't have the uptake they thought it would...so, they really can't exploit the windows backdoor any longer...
They gotta try something!!
Parent
Re:Ummm, parent is right. (Score:5, Insightful)
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.
Parent
Re:umm (Score:4, Insightful)
And if it is incompetence, in this case the malice can come later if anyone ever figures out the 'secret numbers'.
Parent
Re:umm (Score:5, Insightful)
Parent
You misunderstood 'you' :) (Score:3, Informative)
Re:umm (Score:5, Informative)
1: Open algorithms are the mainstay of the crypto community
2: All those algorithms described in the article have been published
3: The NSA did not sponsor, develop, or promote all of random number generators described in article (much less all that are available)
4: The NSA is not the sole distributor of the source or binary versions of these algorithms
I know the NSA has a bunch of really sharp folks but how could they pull off having a backdoor in an Random Number Generator algorithm which they did not design, did not sponsor development of, and do not distribute?
As far as Dual_EC_DRBG goes it is clear how they could have pulled off a stealthy backdoor, the algorithm is their own design.
Parent
Re: (Score:3, Informative)
Huh? You seem to be implying either that the algorithm criticized by Bruce is in fact secure, or that the insecure algorithm is unlike the other three in some way that renders the other three immune to a similar insecurity. Neither implication makes any sense.
Sorry, the second implication is both completely true, and makes perfect sense. I don't really understand how you could claim otherwise.
It is unlike the other three, just as the other three are all unlike each other. It uses elliptic curves, where the other three don't, and the attack is specific to elliptic curves.
Re:umm (Score:4, Funny)
Still..........I'd better go change the combination on my luggage....
Parent
Re:umm (Score:4, Interesting)
The incompetence is that they failed to hide it.
Parent
alternate explanation for incompetence (Score:5, Interesting)
- 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.
Parent
Re:umm (Score:5, Insightful)
Don't tolerate incompetence.
Especially when the party involved should know better, and when there's a lot at stake.
Parent
Re: (Score:3, Informative)
USA has done these things before. Just google for Crypto AG.
The answering machine (Score:5, Interesting)
Re:The answering machine (Score:5, Insightful)
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.
Parent
Re: (Score:3, Interesting)
From TFA: (Score:5, Informative)
On the last slide, the researchers add some suggestions:
Re:From TFA: (Score:5, Interesting)
Parent
Lock the Trojan Horse in a Stable (Score:5, Insightful)
Parent
Doesn't work (Score:4, Insightful)
Parent
T-shirts (Score:5, Funny)
Fix (Score:4, Informative)
Everyone who is not in NSA... (Score:4, Interesting)
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."
Trust the Spies (Score:5, Insightful)
This situation shows one of the strongest arguments for open source. Trust no one.
Re: (Score:3, Funny)
Version: GnuPG v1.4.6 (GNU/Linux)
jA0EAwMCPPnmI+wr8DVgyRye1U/9KBxX5jcOp0oidm/5y9TesyWpjQbYvE3j
=pvFV
-----END PGP MESSAGE-----
This is secure. The password is foo. Let's have a symmetrically encrypted discussion using GPG. All passwords are foo.
Don't trust any encryption (Score:3, Insightful)
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: (Score:5, Interesting)
"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?
Re:I can't be the only one: (Score:5, Insightful)
Parent
Things we know we don't know. (Score:5, Interesting)
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
Re:Things we know we don't know. (Score:5, Interesting)
This 10 year thing starts to tickle my paranoia. NIST has the stated goal to make all of it's algorithms unbreakable for at least 10 years, and the NSA claims on their website that they are always 10 years ahead of what is known publicly (with respect to computational power and cryptographic research).
Parent
Clipper Chip (Score:4, Informative)
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.
why put all your eggs in one basket? (Score:4, Interesting)
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.
Don't Use Dual_EC_DRBG (Score:5, Informative)
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 [iacr.org] 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 [wikipedia.org] which is terribly inefficient. CryptMT [iacr.org] (Cryptanalysis [eu.org]) also deserves a mention as it looks like a promising pseudo-number theoretic DRBG, at least a better candidate than Dual_EC_DRBG.
No, it *does* have a backdoor (Score:3, Insightful)
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? (Score:4, Informative)
Parent
Re:Ummm...encryption standard? (Score:5, Informative)
Parent
Re:Ummm...encryption standard? (Score:5, Insightful)
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.
Parent
Re:Ummm...encryption standard? (Score:5, Insightful)
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?
Parent
Re:Ummm...encryption standard? (Score:4, Informative)
I Am Not A Cryptanalist, but it is my impression that you are off base in this. Generating the plaintext may not become a completely trivial task with the backdoor key, but it at least would become so many orders of magnitude easier that the system would be essentially useless.
In really basic broad-brush terms, we can say that the ciphertext consists of the plain text added to a keystream by a method defined in a certain protocol. To decrypt the ciphertext, the legitimate recipient needs to subtract the keystream from the ciphertext using the same protocol. Any attacker who could capture the whole ciphertext usually should also discover the protocol in use. (That's not necessarily a trivial step, but often it is... especially with computers using known protocols.*) So the only unknown the attacker needs in order to reveal the plaintext is the keystream.
Schneier's article says that by observing a mere 32 consecutive bytes of randomness, an attacker with the key to the backdoor can generate the whole random stream, at least from that point forward. So if such an attacker can suss out that small portion of the keystream or plaintext - and that's what cryptanalysis is all about - then they can use that to break the whole message with relative ease.
[*: It is widely thought, and has been repeatedly proven by real world cryptosystem breaks where the protocol is unknown to the breaker, that for the most part hiding the protocol does no damn good. This is what's meant by "obscurity is not security".]
Parent
Re: (Score:3, Insightful)
Fixed that for ya... (Score:4, Informative)
Parent
Not the same thing (Score:5, Insightful)
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.
Parent
Re:What part of "NSA Approved" don't you understan (Score:3, Funny)
Re:What part of "NSA Approved" don't you understan (Score:5, Insightful)
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.
Parent
Re: (Score:3, Insightful)
Supposing
Re:Give everyone the key (Score:5, Informative)
Parent
Re:Of course! Just look what they did with the tel (Score:4, Interesting)
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.
Parent