Did the NSA build a backdoor into a new elliptic encryption standard?

Posted by Rick C. Hodgin, material from Wired

Wired's Bruce Schneier is reporting that one of the four recent government approved standard methods for creating random numbers has a flaw which is so blatant, that the two cryptographers who found it claim "it can only be described as a backdoor."

Background
There are four proposed methods for generating random numbers in the new SP 800-90 standard, called DRBGs or Deterministic Random Bit Generators.  The first is a hash function, the second uses HMAC (a key-form of hashing), the third is based on block ciphers and the forth is based on elliptic curves, called Dual_EC_DRBG.

The problem
The elliptic curve algorithm has drawn attention to itself for several reasons.  First, it's three orders of magnitude slower than the other ones (1000x slower).  Second, it's been discovered that it has a flaw so potentially damaging that if someone were to solve the elliptic function, then obtaining only 32 bytes of any encrypted data would provide enough information to decrypt all of the following data.  And third, it has been "championed by the NSA", according to Schneier.

Physical encoding
Schneier explains, "This is how [the elliptic algorithm] works:  There are a bunch of [fixed number constants] 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 [the two researchers who discovered the flaw in August and reported on it, named Dan Shumow and Niels 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 [https] 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."

Recent flaws in software random number generators have been reported in SSL, Windows 2000, Linux and other systems.  In each case, these flaws resulted in a total breakdown of that security system.  When it became possible to know the random number sequence, any data encrypted with those methods could no longer be deemed secure.  While it is likely that such data was not captured and decrypted, it is no longer impossible to say with certainty because the algorithm is known to be unsecure.  And this may now be the case with the NSA championed Dual_EC_DRBG method of generating random numbers.

Conclusion
While the researchers have no way of knowing for sure if the elliptic curve function has actually been solved, they suggest the mechanics of the operation, meaning the selected use of a set of fixed number constants listed in Appendix A without explanation, make it at least possible.  And if true, this has profound implications about our National Security Agency and its desire to assist citizens and corporations in having the most secure data encryption solutions possible.

Schneier ends his article by advising everyone to avoid the Dual_EC_DRBG at all costs.  He suggests one of the alternative encryption methods if a requirement to use the new SP 800-90 standard is present.  He also says, "...both NIST and the NSA have some explaining to do".  Read the original article.