[LINK] Fwd: Did NSA Put a Secret Backdoor in New Encryption Standard?

Tue Nov 20 08:38:11 AEDT 2007

The link will take you to the better formatted version.
Jan

>You might be interested in this.
>
>
><http://www.wired.com/politics/security/commentary/securitymatters/2007/11/securitymatters_1115>http://www.wired.com/politics/security/commentary/securitymatters/2007/11/securitymatters_1115 
>
>
>
>
>
>Did NSA Put a Secret Backdoor in New Encryption Standard?
>
>
>
><http://www.wired.com/services/feedback/letterstoeditor>Bruce 
>Schneier 11.15.07 | 12:00 AM
>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 
><http://www.cs.virginia.edu/~rjg7v/annotated.html>problems and 
>attacks over the years. A recent 
><http://eprint.iacr.org/2007/419>paper found a flaw in the Windows 
>2000 random-number generator. Another 
><http://eprint.iacr.org/2006/086.pdf>paper found flaws in the Linux 
>random-number generator. Back in 1996, an early version of SSL was 
><http://www.ddj.com/windows/184409807>broken because of flaws in its 
>random-number generator. With John Kelsey and Niels Ferguson in 
>1999, I co-authored <http://www.schneier.com/yarrow.html>Yarrow, a 
>random-number generator based on 
><http://www.schneier.com/paper-prngs.html>our own cryptanalysis 
>work. I improved this design four years later -- and renamed it 
>Fortuna -- in the book <http://www.schneier.com/pc.html>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 
><http://csrc.nist.gov/publications/nistpubs/800-90/SP800-90revised_March2007.pdf>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 
><http://en.wikipedia.org/wiki/HMAC>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 <http://eprint.iacr.org/2006/190>were 
>first <http://eprint.iacr.org/2007/048>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 <http://rump2007.cr.yp.to/15-shumow.pdf>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 
><http://en.wikipedia.org/wiki/Secure_Sockets_Layer>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.
>- - -
>Bruce Schneier is CTO of BT Counterpane and author of 
><http://www.schneier.com/bf.html>Beyond Fear: Thinking Sensibly 
>About Security in an Uncertain World

Jan Whitaker
JLWhitaker Associates, Melbourne Victoria
jwhit at janwhitaker.com
business: http://www.janwhitaker.com
personal: http://www.janwhitaker.com/personal/
commentary: http://janwhitaker.com/jansblog/

Living, like writing, requires no wisdom. Only revising does. - Jim 
Sollisch, Sept, 2007
'Seed planting is often the most important step. Without the seed, 
there is no plant.' - JW, April 2005
_ __________________ _