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."

Re:Ummm...encryption standard?

[orclevegam]

This seems to be more an issue with something like SSL in which the security of the system is reliant on not being able to guess the next number out of the PRNG.

From TFA:

[Spy der Mann]

* WHAT WE ARE NOT SAYING:
NIST intentionally put a backdoor in this PRNG

* WHAT WE ARE SAYING:
The prediction resistance for this PRNG (as presented in NIST-SP800-90) is dependent on solving one instance of the elliptic curve discrete log problem.
(And we do not know if the algorithm designer knew this beforehand.)

On the last slide, the researchers add some suggestions:

Truncate off more than the top 16 bits of
the output block.
- Results on extractors from x coordinates of
EC points of prime curves suggest truncating
off the top bitlen/2 bits is reasonable.
* Generate a random point Q for each
instance of the PRNG.

Re:Ummm...encryption standard?

[ioshhdflwuegfh]

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.

Fix

[daveschroeder]

"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. "

Re:Give everyone the key

[superwiz]

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.

Clipper Chip

[starfishsystems]

I'm getting a distinct feeling of déjà vu about this. Anyone remember the Clipper Chip [wikipedia.org]? Key escrow? Same basic idea, and that proposal came out of the NSA as well. Only then the backdoor was explicit.

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.

Don't Use Dual_EC_DRBG

[The Real Nem]

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.

Re:umm

[Anonymous Coward]

And when there's a lot at stake, don't blame ignorance, but greed.
USA has done these things before. Just google for Crypto AG.

You misunderstood 'you' :)

[pavon]

bhima's comment was alluding to the fact that while NSA designed and distributed the Dual_EC_DRBG algorithm, they had no part in the other two algorithms (that we know of) other than as an outside commentator, and thus could not put a backdoor into them. In other words 'you' referred to the NSA, not to you, a user of the algorithms.

Fixed that for ya...

[Foerstner]

The thirty-year-old F-15 has been "defeated" during exercises with allied powers, flying planes developed twenty-five years later that are it's equal in technology, with pilots as well trained as ours.

Re:umm

[bhima]

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.

Re:umm

[sveiki_neliels]

Don't look for malice where incompetence will do. -- Napoleon

Napoleon? Try Hanlon's Razor [wikipedia.org].

Re:umm

[Goaway]

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:Ummm...encryption standard?

[peacefinder]

"[...] it's still nontrivial to generate the plaintext from the ciphertext, or am I completely offbase on this?"

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".]

Re:Mod AC Down

[kliklik]

Would that be Kryptos [wikipedia.org]?

Re:Ummm, parent is right.

[ahabswhale]

Learn how to read. CIA != NSA. In regards to your off topic remark, every organization of any reasonable size has people that aren't very smart or are ruled more by their egos than what's actually best for the organization (or country as the case may be). It's called human nature. Get used to it.

I mean really.

[/dev/trash]

If the bad guys have a bomb, I think we can all agree that decrypting their plans is a good thing.

My opinion - CIA !smart

[dbIII]

The CIA believe in a voodoo device invented by a comic book writer to peer into men's minds and see if they are telling the truth - wonder woman's golden lariat was sold as a con by it's writer and is called the polygraph. Court cases over unfair dismissal disputes (eg. trnaslators) are also giving some insight into the place and how clueless, petty and nasty some of the management is. They may have some sharp people in there but the collective mass is a herd of dumb frightened animals that kill people in horrible ways in flawed attempts to get information (they missed the memo from the Russians, Japanese etc that you use torture to scare people but it's useless if you want to get information). They have not been under adult supervision since before the days of Kennedy.

Re:Why not swap out the broken part then?

[plover]

The problem is that the amount of randomness from any of these sources is testably small.

A simple example would be something like one of the games we were all taught to program as kids. The first line was always something like 10 RANDOMIZE TIMER. Well, if you know the program was run at 8:19, the value of TIMER was likely somewhere between 29940 and 29999. It may be random enough for MONOPOLY.BAS, but it's not much of a challenge to try all 60 values. Entropically speaking, time of day is good enough for only a couple of bits, no more.

Let's say you had a message from DOMAIN\JOHN timestamped 2007-11-15 08:19:02, and you know I come in at about 8:00 every morning and turn on my computer. You can probably make some educated guesses about the values of GetLocalTime() and GetTickCount(). You know my user name. Process ids on Windows are sequentially assigned as of boot up, and probably wouldn't vary by more than a hundred, especially for a creature of habit. Memory and disk space are also likely to be in a similar range, so checking my desktop on another day might reveal some good guesses for those ranges.

All those values plus a few others are used by the Windows pseudo-random number generator, as revealed earlier this week. [slashdot.org] Sure, they mix in some harder-to-guess values, but who knows how easy or hard they might be to discover, especially with access to the hard drive? If you use only 32 bits of entropy to seed a cryptographic routine to emit 128 bytes of random numbers, that's still only 32 bits of guessing that needs to happen.

Healthy Case of Paranoia

[Propaganda13]

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 publicly design, did not publicly sponsor development of, and do not distribute?

Fixed your question and hopefully answered it for you too.