Posted on 12/17/2007 2:02:05 PM PST by antiRepublicrat
Random numbers are critical for cryptography: for encryption keys, random authentication challenges, initialization vectors, nonces, key-agreement schemes, generating prime numbers and so on. Break the random-number generator, and most of the time you break the entire security system. Which is why you should worry about a new random-number standard that includes an algorithm that is slow, badly designed and just might contain a backdoor for the National Security Agency.
Generating random numbers isn't easy, and researchers have discovered lots of problems and attacks over the years. A recent paper found a flaw in the Windows 2000 random-number generator. Another paper found flaws in the Linux random-number generator. Back in 1996, an early version of SSL was broken because of flaws in its random-number generator. With John Kelsey and Niels Ferguson in 1999, I co-authored Yarrow, a random-number generator based on our own cryptanalysis work. I improved this design four years later -- and renamed it Fortuna -- in the book Practical Cryptography, which I co-authored with Ferguson.
The U.S. government released a new official standard for random-number generators this year, and it will likely be followed by software and hardware developers around the world. Called NIST Special Publication 800-90 (.pdf), the 130-page document contains four different approved techniques, called DRBGs, or "Deterministic Random Bit Generators." All four are based on existing cryptographic primitives. One is based on hash functions, one on HMAC, one on block ciphers and one on elliptic curves. It's smart cryptographic design to use only a few well-trusted cryptographic primitives, so building a random-number generator out of existing parts is a good thing.
But one of those generators -- the one based on elliptic curves -- is not like the others. Called Dual_EC_DRBG, not only is it a mouthful to say, it's also three orders of magnitude slower than its peers. It's in the standard only because it's been championed by the NSA, which first proposed it years ago in a related standardization project at the American National Standards Institute.
The NSA has always been intimately involved in U.S. cryptography standards -- it is, after all, expert in making and breaking secret codes. So the agency's participation in the NIST (the U.S. Commerce Department's National Institute of Standards and Technology) standard is not sinister in itself. It's only when you look under the hood at the NSA's contribution that questions arise.
Problems with Dual_EC_DRBG were first described in early 2006. The math is complicated, but the general point is that the random numbers it produces have a small bias. The problem isn't large enough to make the algorithm unusable -- and Appendix E of the NIST standard describes an optional work-around to avoid the issue -- but it's cause for concern. Cryptographers are a conservative bunch: We don't like to use algorithms that have even a whiff of a problem.
But today there's an even bigger stink brewing around Dual_EC_DRBG. In an informal presentation (.pdf) at the CRYPTO 2007 conference in August, Dan Shumow and Niels Ferguson showed that the algorithm contains a weakness that can only be described a backdoor.
This is how it works: There are a bunch of constants -- fixed numbers -- in the standard used to define the algorithm's elliptic curve. These constants are listed in Appendix A of the NIST publication, but nowhere is it explained where they came from.
What Shumow and Ferguson showed is that these numbers 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 predict the output of the random-number generator after collecting just 32 bytes of its output. To put that in real terms, you only need to monitor one TLS internet encryption connection in order to crack the security of that protocol. If you know the secret numbers, you can completely break any instantiation of Dual_EC_DRBG.
The researchers don't know what the secret numbers are. But because of the way the algorithm works, the person who produced the constants might know; he had the mathematical opportunity to produce the constants and the secret numbers in tandem.
Of course, we have no way of knowing whether the NSA knows the secret numbers that break Dual_EC-DRBG. We have no way of knowing whether an NSA employee working on his own came up with the constants -- and has the secret numbers. We don't know if someone from NIST, or someone in the ANSI working group, has them. Maybe nobody does.
We don't know where the constants came from in the first place. We only know that whoever came up with them could have the key to this backdoor. And we know there's no way for NIST -- or anyone else -- to prove otherwise.
This is scary stuff indeed.
Even if no one knows the secret numbers, the fact that the backdoor is present makes Dual_EC_DRBG very fragile. If someone were to solve just one instance of the algorithm's elliptic-curve problem, he would effectively have the keys to the kingdom. He could then use it for whatever nefarious purpose he wanted. Or he could publish his result, and render every implementation of the random-number generator completely insecure.
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. But the procedure is optional, and my guess is that most implementations of the Dual_EC_DRBG won't bother.
If this story leaves you confused, join the club. I don't understand why the NSA was so insistent about including Dual_EC_DRBG in the standard. It makes no sense as a trap door: It's public, and rather obvious. It makes no sense from an engineering perspective: It's too slow for anyone to willingly use it. And it makes no sense from a backwards-compatibility perspective: Swapping one random-number generator for another is easy.
My recommendation, if you're in need of a random-number generator, is not to use Dual_EC_DRBG under any circumstances. If you have to use something in SP 800-90, use CTR_DRBG or Hash_DRBG.
In the meantime, both NIST and the NSA have some explaining to do.
But what makes this interesting is that Microsoft is including this random number generator in Vista SP1.
Is a bear Catholic?
SHHHHH! Dammit!
My random number for the day. See, it's real easy.
probably NOT random, as it has no repeated numbers.
Bruce Schneier rules at sniffing out snake oil.
Anyone ever use this encryption? I’ve thought about using it and I wonder if it’s any good.
Wait, there is a second edition. Arrrg, Sandy Clause ate all my money! Always next month.
Hasn’t cryptography long been considered regulated “weaponry”?
“Anyone ever use this encryption?”
I use GnuPG.
Wouldn’t surprise me.
8675309
Is anyone surprised by that? Apparently, Microsoft has never been able to hire a decent cryptographer.
4 8 15 16 23 42
Right. I threw out two zeros because I don’t like that number.
"There are two kinds of cryptography in the world. There is the kind that will keep your kid sister from reading your mail, and there is the kind that will keep major governments from reading your mail. This book is about the latter."
Probably the best technical book introduction ever written.
What are the chances of that?
Congratulations! You have a BINGO.
LOL! And I was just going to make some granola.
Yes, thus the origins of the "munitions t-shirt", described briefly here.
Not me, I'm Episcopalian.
***What Shumow and Ferguson showed is that these numbers have a relationship with a second, secret set of numbers that can act as a kind of skeleton key.***
I’d sure be curious to see their math where they showed this relationship. And, I’d like to know how they are certain that a second set of numbers exist or if this is just a case of we thought and wouldn’t you know the math works out.
Did you get “that number off the wall”?
There are more geniuses, per square foot, at the NSA than any place on earth.
They don’t need a back door.
OK here is my number
it is the product of 2 primes
A common encryption / decryption
algorithm depends on a public key
of a long number which is the product
of 2 long prime numbers
Find the 2 primes and you get the Kewpie doll
I found the whole article rather cryptic...
[Drill, f'Petessake, your car is parked in the General's spot. Move it, willya?]
Oops. Gotta go...
More importantly, does it pope in the woods?
Is there any reason to only use one random number generator? If two ‘random’ generators are independent, then the XOR of them will be at least as ‘random’ as the better of the two. Adding in an extra random generator might not help a whole lot, but it couldn’t hurt and it would at least make attacks on the primary one more difficult.
"Onetime pad wanna-be"
http://www.acme.com/software/factor/
23,292,079,583,053 =
3355067 * 6942359
Anyone who can find the primes, can
decrypt your messages in this scheme
Generally, if ya got a lot of computer
you can break darn near any scheme
To be fair, the article is about how you generate p and q to begin with. In other words, if my mission is to figure out what your two primes are that multiply out to 23,292,079,583,053, then, sure, I can try to brute-force my way through all 14-digit primes, but if you used some kind of flawed technique for picking your two primes in the first place, then I can save myself a whole ton of work.
It’s kind of like how I can always beat you at rocks-paper-scissors if I know you always pick rock.
Would that be Factorization: 6942359 * 3355067?
Jack
It’s kind of like how I can always beat you at rocks-paper-scissors if I know you always pick rock.
Bingo
“Generally, if ya got a lot of computer you can break darn near any scheme”
A computer, and time. Lots and lots and lots and lots and lots of time. :)
The point of digital encryption techniques isn’t to make a code unbreakable. There’s no such thing as a literally unbreakable code. Rather, the point is that, without some particular piece of information (such as a key), breaking the code is so computationally complex that the expected time it would require to break the code, given “reasonable” computing resources (more on that later), is greater than the lifetime of the value of the message itself.
As for what makes computing resources “reasonable” given the desired encryption strength, that depends on what you want to protect. Contrary to most tinfoil-hatters out there, the NSA is not going to pool the combined supercomputing resources of every federal lab in order to crack their way into your porn archive. They may, however, do so in order to acquire China’s nuclear launch codes - or, more to the point, the Chinese may do so to us.
Hasn’t cryptography long been considered regulated “weaponry”?
Yes. they are categorized as munitions.
I was once in the business of developing commercial encryption devices. Every design to be considered for export had to be approved by the NSA.
I can guarantee you that every approved encryption system has a backdoor the NSA can use, or they feel that they don’t need one as the encryption is easy enough to break without it.
ping for your list.
Can you believe we have to wait almost a whole year from last season until the new season starts? What is up with that?
That is so cool! In a geek sort of way.
It was a long time ago, but the cat came out of the bag. Students all over the world were learning how to do cryptography at their universities, but we couldn't export anything written here.
My kid cracked your kid’s code...
That's what my kid wants yours to think. Mwuhahahahhahaa.
is there a ping list for this stuff? if so, please put me on.
i recently read an article about how Google was used to break a password hash (MD5?). it seems to me that distributed computing is a poor man’s way to approach some of these tasks.
A simple one time pad is 100% unbreakable no matter how much time or computer power you have.
Yes fine, except for a one-time pad. :)
Disclaimer: Opinions posted on Free Republic are those of the individual posters and do not necessarily represent the opinion of Free Republic or its management. All materials posted herein are protected by copyright law and the exemption for fair use of copyrighted works.