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."
On the last slide, the researchers add some suggestions:
What happens in the article is that one of the algorithms proposed by NSA for standardization contains possibly a major backdoor because the constants it uses to generate numbers are such that there might be other constants, unknown by looking at the algorithm itself but nevertheless possibly known to the authors at NSA that allow to get the whole generated sequence of numbers based on only 32 byte sequence of generated numbers. Maybe or maybe not, depending on whether there are such constants, which only NSA knows.
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.
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.
No. I was replying to someone who said the NSA had put backdoors in all available Random Number Generators and I wondered how the NSA could possibly get a backdoor in all of such algorithms. My line of thinking was this
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.
Nothing in the world is more dangerous than sincere ignorance and conscientious stupidity.