Did NSA Put a Secret Backdoor in New Encryption Standard? (2007)

http://www.schneier.com/essay-198.html

by Jach • 14 years ago

174 93 14 years ago

delinka4• 14 years ago

"In the meantime, both NIST and the NSA have some explaining to do."

Not happening. Hasn't yet, nor will it. NSA just keeps quite and watches for someone to use their particular algorithm. We should assume malicious intent and take Schneier's advice: "My recommendation, if you're in need of a random-number generator, is not to use Dual_EC_DRBG under any circumstances."

And if you "don't have anything to hide," then I propose you've given up already and cryptography is useless to you.

lmm2• 14 years ago

Not entirely. While the best cryptography is that which is secure against everyone (duh), there are a vast number of perfectly legitimate use cases for cryptography where it doesn't matter if the NSA can read your encrypted data.

tych0• 14 years ago

Are there? If I knew something had a backdoor, I'd always wonder who else has figured it out.

delinka4• 14 years ago

I'd rather err on the side of keeping them in the dark all the time. Encrypting data differently based on whether I mind if NSA sees it leaks information. Specifically, that this data doesn't matter but that data does and NSA should focus their efforts on breaking that data or analyzing that social graph affiliated with the data.

nathan_long3• 14 years ago

I can't imagine any legitimate use case for crappy cryptography, and any crypto with a backdoor is crappy. If the door is there, anyone with the key can open it. How can you be sure who will get the key, or what their motives will be?

Good, modern cryptography offers a level of security unparalleled in the physical world, and at a processing cost which any computer can handle. Why would you intentionally choose something inferior?

tptacek12• 14 years ago

You don't have to take Schneier's advice in order to not end up with an elliptic curve random number generator. Nobody does that anyways.

NegativeK• 14 years ago

Can you elaborate on why?

lucaspiller• 14 years ago

Interesting... Was there any code written to demonstrate the attack?

delinka4• 14 years ago

That's a good question. I suspect if so, it was alongside an academic paper and this stuff just doesn't get attention from journalists. I'd be curious to find out but I don't have the skills to pore over the material myself.

danielweber2• 14 years ago

Do you really think "academic finds back door in NSA's random number generator" wouldn't get headlines? Remember how people freaked over the mere mention of the name of "NSAKEY" freaked everyone out?

pbsd3• 14 years ago

No. The backdoor relies on the generator of the parameters (presumably the NSA) knowing a discrete logarithm ahead of time. Anyone outside the NSA would have to break a rather large discrete logarithm, which is just not gonna happen anytime soon.

gmoore• 14 years ago

Not exactly current - the article is something like 5 years old....

delinka4• 14 years ago

You'll notice the "[2007]" in the post title.

jimktrains2• 14 years ago

Apparently the mods added it later. There really should be some way to tell what the mods have and haven't done.

camiller• 14 years ago

Yeah, I started reading it and thought gee this sounds familiar.

tptacek12• 14 years ago

Nobody used this random number generator.

javert• 14 years ago

Perhaps the government required defense contractors to use this one in products sold to other countries?

I don't have any evidence for that, just speculation on one reason the NSA might insist on including something like this in the spec.

anonymouz2• 14 years ago

This is quite interesting, as the NSA on the one hand needs to provide secure algorithms for the public to use, but on the other hand has an interest in being able to break algorithms.

IIRC, during the standarization of DES, the NSA has also modified some S-Boxes without giving any explanation. Only later, when differential cryptoanalysis became known to the public, it was clear that this was to strengthen DES against this particular attack (which was already known to the NSA).

The case here is more interesting though: It seems like you need to know some secret numbers (a sort of "private key" if you will) to be able to attack the PRNG. So it seems that the NSA could place a "safe" backdoor that even an attacker with the same cryptography knowledge as they have cannot break unless he himself possesses the "private key".

tptacek12• 14 years ago

What sense does it make to backdoor an RNG that no normal system is ever going to use, and to do so in a public standard, and further to do so by using deliberately broken curve parameters?

It was an interesting story because it was so weird. But even had Dual EC not become known to the world exclusively as "the CSPRNG with the backdoor in it", nobody would have used it anyways.

anonymouz2• 14 years ago

Yeah that is rather weird. A botched attempt maybe?

Nikker3• 14 years ago

Since many of these procedures are implemented in hardware directly, maybe it could be utilized as a conditional fall-back? An example might be a MITM attack that indicates an invalid hand shake or shows that an insufficient random pool is detected so it would attempt to connect using each alternative in order till it gets to the weak link. Technically speaking this would be ideal since the government and ISP's that carry these messages are so intertwined that the breadth would cover every citizen in their own country and likely many others.

trotsky• 14 years ago

As a teaching moment? I've been told a story about a group of embassy staffers (state department, not the other kind) that were in the habit of being rather loose with sensitive conversations over the local telephones. This was during the cold war when secure conversations often meant driving into the office to speak face to face, which could understandably make weekend news rather unwelcome. This apparently made some folks on station rather unhappy, but repeated admonishment fell on deaf ears. The reported solution was to remove a tiny bit of insulation from several of the phone wires as they entered the building on the roof. This lead to a very occasional clicking on the lines as wind would move the wires and cause a momentary short which blossomed into a newfound respect among the corps for communication protocol.

Most people learn much better by doing (or getting done).

ChuckMcM• 14 years ago

I agree it was interesting because it was weird. One wonders if the NSA might put things out like this to test the analysis ability of the 'open' community? I wonder if there is ever the question inside the Fort like "Well we can do this, but how obvious is it to people outside our group?" Testing that question isn't easy, but answering it is important for knowing the size of the threat posed by an equivalent type vulnerability.

danielweber2• 14 years ago

Back when DES was being designed, IBM had a bunch of values in their S-boxes. NSA told them "don't use those values; use these values instead." People freaked that it was a backdoor the NSA put in.

About 15 years later, differential cryptoanalysis was publicly discovered. The original S-box values would have been very vulnerable to the attack, but the ones the NSA used were resistant, suggesting that NSA knew about differential cryptoanalysis way ahead of time and were suggesting ways to protect the public against its eventual discovery.

It is possible that there is still some magic in there to let the NSA magically defeat DES, but we still haven't found it. Similarly, it's possible that this random number generator exists for some nefarious purpose, but we have no evidence for it.

Also, this article is 5 years old (the headline didn't say so when I first read this). Schneier was in pretty big self-promotion mode at that time.

Nikker3• 14 years ago

Don't forget that IBM actually designed Lucifer which was 128bits but it was the (edit:s/NSA/NHIS) that truncated it to 56bits and named it DES. So maybe this is an example of "6 of one or half a dozen of the other"?

tptacek12• 14 years ago

And don't forget that Eli Biham smote Lucifer with differential cryptanalysis, found more than half of the keys insecure, reduced its security to 235, and published a journal article concluding that NSA strengthened the cipher design; DES was better than Lucifer.

CWuestefeld4• 14 years ago

I can't find the citation right now, so treat this as apocryphal, but...

I've read an explanation that the USA's focus on security has changed in the days since 9/11/2001. At one time, the philosophy was that the country was more secure when we could all be assured that the privacy of our communications was intact.

But in the last decade we've changed that philosophy. The government's security philosophy now is that the most important thing is for the government to be able to tell what's going on.

So it may be that the parent post's anecdote is quite correct, and reflects the policy of that time. But in the days of the War On Terror, we can't trust that anymore.

(And OT, I believe it reflects a fundamental change in the philosophy of governance that is against the founding principles of the country, and a pretty bad thing. I believe that our strength derives from ... us -- we the people. And so strengthening the government by weakening us in fact weakens the nation.)

EDIT: fix date. Thanks, Retric.

dpark4• 14 years ago

> At one time, the philosophy was that the country was more secure when we could all be assured that the privacy of our communications was intact.

That's never really been the view of the U.S. government. It's always been the view that you should be able to have communications with your neighbor that are secure from everyone except the US government, who obviously need to snoop in order to protect us all.

The security agencies and the police agencies have always pushed for more comprehensive and more invasive surveillance. We've had wiretapping for as long as we've had wires to tap. We crippled Internet security for years. I remember the days of separate US and international Netscape releases, due to crypto export restrictions. It wasn't until 2000 that the restrictions were truly relaxed.

Retric2• 14 years ago

9/11/2001

antidoh2• 14 years ago

Well, the NSA is building that data center in Utah to store and process all the data they're hoovering up. That data would be much more useful if it weren't encrypted. So they do at least have a motive, even if the ability can't be proved.

Nelson692• 14 years ago

If I'm not mistaken, they've sort of tweaked the definition of "interception" too. The game plan is to capture everything and then it's 'intercepted' when they actually listen and analyze it.

Flenser• 14 years ago

suggesting that NSA knew about differential cryptoanalysis way ahead of time and were suggesting ways to protect the public against its eventual discovery

The NSA may also have know who else knew about differential cryptoanalysis, and didn't want it to be weak in ways that others could break it, but left it weak in ways that they could.

dalke• 14 years ago

You would think that after this many decades any such built-in weakness to DES would have been discovered. Do you think the NSA crypto knowledge (or rather, IBM crypto knowledge, since that's where differential cryptanalysis was developed) back in the 1970s was better than the modern crypto knowledge?

tedunangst• 14 years ago

If that's true, then the NSA is 40 years ahead of the public.

cerebrum• 14 years ago

From https://en.wikipedia.org/wiki/Differential_cryptanalysis

"In 1994, a member of the original IBM DES team, Don Coppersmith, published a paper stating that differential cryptanalysis was known to IBM as early as 1974, and that defending against differential cryptanalysis had been a design goal."

apawloski2• 14 years ago

To expand a little, the NSA also required the initial permutation of plaintext bits. This was done before the first 16 rounds of DES, and looked like this:

    58 50 42 34 26 18 10 2
    60 52 44 36 28 20 12 4
    62 54 46 38 30 22 14 6
    64 56 48 40 32 24 16 8
    57 49 41 33 25 17  9 1
    59 51 43 35 27 19 11 3
    61 53 45 37 29 21 13 5
    63 55 47 39 31 23 15 7

Which meant "put the 58th bit of the plaintext into the first position, put the 50th bit into the second position, etc, and THEN run through the encryption algorithm."

At the time, it was totally unclear why you had rearrange the bits in this very exact way. After all, you were about to encrypt it (and obliterate any plaintext patterns) anyway. And would it be as strong if you started with the 57th bit, instead of the 58th? The whole thing seemed so arbitrary.

Now it's true that this is robust to differential cryptanalysis, but it's also true that these bit permutations significantly slow down software implentations of DES. But it's trivial to implement the initial permutation in hardware.

In the 1970s, the hardware required to crack DES costed $20,000,000 US dollars [1] (about $120 million in today's dollar [2]). The general tinfoil-theory at the time was that 1) only the NSA had the resources to build such a machine and 2) by forcing DES to use this initial permutation, the NSA was giving themselves a significant "head-start" over everybody else using software to crack DES.

[1]http://www.krapp.org/hydra/courses/analysis/3-DataEn.pdf (PDF) [2]http://www.wolframalpha.com/input/?i=%2420%2C000%2C000+1970+...

pbsd3• 14 years ago

The permutations in DES have nothing to do with security; there is an excellent explanation by Thomas Pornin on what their purpose was: http://crypto.stackexchange.com/a/6/592

What was altered were the 8 S-boxes, seemingly random lookup tables that map 6- to 4-bit values. More details by Don Coppersmith himself at: http://simson.net/ref/1994/coppersmith94.pdf

stanfordkid• 14 years ago

Spot on. You have to realize that the government buys software and systems that rely on encryption from the private sector. It is in their own interest to have the strongest crypto in government hardware and software. So while they know a lot of exploits they also know that it is quite plausible that our enemies know the same exploits (i.e China, Russia) and using government hardware that uses a poor standard is not a great idea.

stordoff• 14 years ago

It is possible that the NSA modified this RNG for perfectly good reasons, but, in my opinion, even the slight possibility of an attack existing is too high when other better RNGs exist.

tptacek12• 14 years ago

This isn't a controversy. Nobody would have used that RNG anyways. There's probably no bignum math in any commonly used RNG, let alone elliptic curve math. Not only that, but Dual EC had problems even before Furguson pointed out the parameter weirdness.

You do not need to be on guard against secret NSA Dual EC backdoors.

gizmo6862• 14 years ago

>>It is possible that there is still some magic in there to let the NSA magically defeat DES, but we still haven't found it.

Actually the NSA s-boxes are weak against linear crypto analysis. http://reference.kfupm.edu.sa/content/l/i/linear_cryptanalys...

If I remember Schneider's applied cryptography correctly, the NSA s-boxes were among the worst 7% possible.

I wonder what we would be saying about the NSA if we (publicly) discovered linear crypto-analysys before differential. However, I suspect the vulnerabilty to linear analysys is the result of how structured they made it to resist differential.

Did NSA Put a Secret Backdoor in New Encryption Standard? (2007)

Related Stories