Did NSA Put a Secret Backdoor in New Encryption Standard?

[mouser]

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.
...
But today there's an even bigger stink brewing around Dual_EC_DRBG. In an 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.
...

http://www.wired.com...securitymatters_1115

from http://it.slashdot.o...184204.shtml?tid=172

[Ralf Maximus]

If I were running the NSA, of course I'd do crap like this.

On the other hand, NSA has enough terraflops on tap to bypass any encryption almost instantly.  You might as well encode your stuff using Dr.Seussisms and pray the vat-grown NSA geeks never read any children's books while growing up in the secret underground bases.

Which reminds me...

ATTENTION SNEETCH ONE: THE BABY HAS GRASPED THE HAMSTER, BUT HAS NOT SWIGGLED THE BARLEY WINE.  OH, THE PLACES YOU'LL GO WHEN I RUN THE ZOO, IF HORTON HEARS A WHO OR TWO.

[Lashiec]

Oh, I was thinking in posting this two days ago, but I passed onto it, because I thought that people would catch the news anyway.

It's not exactly clear, like Mr. Schneier says at the end of the article, if the NSA did this deliberately, or was a simple oversight. Of course, we'll never know, once they give some explanations, they would choose the latter option

[jgpaiva]

ATTENTION SNEETCH ONE: THE BABY HAS GRASPED THE HAMSTER, BUT HAS NOT SWIGGLED THE BARLEY WINE.  OH, THE PLACES YOU'LL GO WHEN I RUN THE ZOO, IF HORTON HEARS A WHO OR TWO.

-Ralf Maximus (November 19, 2007, 12:46 PM)

I SEE YOUR 200 AnD RAISE YOU 37. LET THE NUTsY BUTMIST RUN INTO THE CaRTILAGE.

[mwb1100]

This reminds me of the rumors that back in the 70's the NSA made the DES encryption standard weaker to enable them to be able to decrypt at will. According to this Wikipedia article (yeah, I know, but it seem to jive with my memory of the situation) http://en.wikipedia...._Encryption_Standard:

• the NSA may or may not have had a hand in determining the values for the DES S-Boxes.  However, whoever did come up with the S-Box values (the NSA, IBM, or both) did it in such a way as to make them more resistant to attacks that at the time were not generally known - ie, stronger rather than weaker
• the NSA may or may not have had a hand in making the DES key a rather short 56-bits, throwing away 8 available key bits for use as 'parity'

It seems like the Dual_EC_DRBG random number protocol is dead in the water - slow and suspect will kill any algorithm.

[tinjaw]

42

[f0dder]

I doubt that "NSA has enough terraflops on tap to bypass any encryption almost instantly." - either there's some unknown backdoors in things like Rijndael, or they have much more advanced quantum computing device than anybody else... but I doubt both of those. (They're much more likely to use the carnivore system to employ man-in-middle attacks and log your encrypted data streams. And no, carnivore/echelon isn't just paranoia.)

I dunno if this possible ECC backdoor is on purpose... it seems unlikely that they'd oversee such a thing. But on the other hand it also seems unlikely that NSA would be stupid enough to have an obvious backdoor, they know there are some pretty skilled people left they haven't yet employed

[Ralf Maximus]

I doubt that "NSA has enough terraflops on tap to bypass any encryption almost instantly." - either there's some unknown backdoors in things like Rijndael, or they have much more advanced quantum computing device than anybody else... but I doubt both of those.

-f0dder (November 19, 2007, 06:57 PM)

f0dder, f0dder, f0dder... I love you man, but you're not nearly paranoid enough.  When I think about the NSA, I imagine a kind of super-evolved human, with more than 50% of their body-mass constituted by neurons.  Which have been soaked in a special formula of stimulants (Coffee) and augmented with alien bioware scavanged from crashed saucers.  Which have been trained from infancy to crack codes in their subconcious, their conciousness busy enough cruising the interweb looking for Enemies of the United States.

Then, just imagine what kind of computers such gods would create.  And multiply by 50.

THEN, only then, might you be paranoid enough.  Maybe.  Follow me? 

No, really... why are you following me? *sob*

On the subject of encryption, one method I understand to be nearly fool-proof is the one-time pad.  Or maybe I mean a Vernam cipher.  Whichever.

The idea is very simple but diabolically hard to break: XOR every letter of your message with the next byte of a one-time generated stream of random noise (previously recorded for you just for this use).  The name comes from WWII when agents would carry specially-created pads of prewritten gibberish around with them for encryption purposes.  They'd tear off one sheet of the pad for each message, thus staying in sync with their senders/recipients, who had identical pads.  The text was sometimes created by a human randomly spasming their hand on a typewriter loaded with carbon paper.

ANYWay, this article got me thinking about encryption again.  I'm an idiot when it comes to the subject, but one thing I do remember: the one-time pad is supposedly unbreakable, *if* you keep your pad-material away from prying eyes, and *if* it's used exactly once.

The downside to OTP is it's inconvenience.  In the modern world, the pad-of-carbon-copies has been replaced with massive files of random bytes... so how do you get the pad-file to your compatriot?  Email?  Remember, if the pad's ever compromised it's USELESS.

Then I thought about this: what if we used DVD movies as the one-time-pad? As far as the computer's concerned it's just a massive collection of bytes, and short of the apocalypse I can't imagine any message I'd want to send someone that was longer than 4.5 gigabytes.

Then all I have to do for you to acquire the right pad material is make sure you have the same movie as me, share the initial offset into the data-stream, and we're ready to go. Ha!  Suck this, NSA!

Just make sure when I say "Terminator 2" you get the Special Edition 3-disc set, not the Ultimate Edition 4-disc set."

[f0dder]

Yeah, one-time pads are the only really-really secure form of encryption that exists today (although they say quantum computing will bring new wonders - that's a bit into the future, though). But it does require that you don't f*ck up and re-use the pad. If you search history books, you'll see people forget about this, even for very important stuff.

I still don't believe NSA has the computing power to brute-force 256bit keys. If they can break 256-bit encryption, imho it's not by bruteforcing, but rather some backdoor, or fancy mathematics that the rest of the world doesn't know about... and something of that scale would be extremely hard to hide.

So... really... I think what you should be most worried about is the snooping that goes on all over the internet, automatically, all the time. If even one "hop" on your data stream's route from you to your target has a sniffer, most encrypted/secure protocols of today break. SSL, SSH, TOR, ... . And wouldn't an obvious place to install a carnivore client be at every ISP?

[Ralf Maximus]

Crap!  Must... buy... more... aluminum foil... :-)

Honestly, I do believe that the NSA has miles of racks filled unfathomly advanced hardware, stuffed with software more advanced than anything we can imagine.  Cracking just about anything is possible for them, given a few weeks of concentrated labor. Coupled with Eschalon and Carnivore, they have a never-ending supply of pads and open-text samples to work with. 

Of course it could just be the image they like to cultivate, the reality closer to a high-school AV club playing D&D, but I kinda doubt it.  In all their history, nobody has overestimated the capabilities of the NSA.

(Any NSA technicians listening in on this, please feel free to comment.)

[J-Mac]

Because, Jesse, that's what they do!!   

Jim

[CWuestefeld]

I think it's highly unlikely that the NSA can crack messages encoded with modern algorithms like Twofish, etc. To do this would require that either their mathematicians or there computers are a revolution beyond what the rest of the world understands. While it's likely that they have some edge, it's hard to believe that they could have, e.g., a working quantum computer when the "public" world has at best built useless demonstrations of 1 or 2 bits.

And as long as you're using some modern algorithms to cover your communications, you're safe from Echelon and Carnivore. With the encryption done on your own machine, the only data they can glean is from traffic analysis. What's holding this back from becoming more widespread is the network effect: no one does it because no one does it; no one will start until they can "jump on the bandwagon" because it's no fun to send encrypted messages when no one is receiving them. It would be cool to start a community that communicated in this way, just to jumpstart the process.

And BTW, for anyone who has any interest in cryptography and related fields and who enjoys sci-fi, I strongly recommend the book Cryptonomicon by Neal Stephenson.

[f0dder]

CWuestefeld: problem is that although encryption is done on one's own machine, there's usually some handshaking going on, and if there's a man in the middle, well... *boom* - he can intercept as well as augment data stream. Lots of protocols are vulnerable that way.

PGP encrypted emails don't fall under this category, as long as you're 100% sure you have the right pubkeys, but then social engineering or good old hacking can be employed - I wouldn't be surprised if NSA/friends often know about 0-day exploits at the same time or before the blackhats.

Carnivore is very real, and the us government is doing some really massive-scale data mining with it. Try applying for a .mil security related job and you'll see...

[Lashiec]

Hehe, the DES story is legendary. Even today, some people are still suspicious of the algorithm. Personally, I think that's being overly paranoid, considering that IIRC the files containing the passwords of Opera and Firefox, and GNUPG all use Triple DES as the encryption algorithm. You can always use stronger algorithms, though, so I don't see any problem in there.

I highly doubt of some backdoor in Rijndael. Wasn't the specification available to the public? Then again it was chosen before the Twofish algorithm... (conspiracy theory... ).

One time pad is extremely secure, that's undeniable, but extremely inconvenient. Is someone using it today? Using media as passphrases, though, it's a nice protection system (jv16 PowerTools has something like this as an option to prevent unauthorized access to the software), but in this age, when everyone loses everything and kids run amok around the house, it's not recommendable.

Don't worry about Carnivore, the latest trend is a traffic shaper per ISP. Besides, Carnivore it's retired, apparently commercial software does its job better (pretty fearful, everyone can go to the P2P and download its copy, and start playing NSA).

And Twofish is unbreakable. Why? It was designed by Bruce Schneier . I'll bookmark that book, thanks. Whoa, it's a novel, that's sweet.

(Now I'm going to write a post ranting about how you guys write too much in too little time, darn!)

[CWuestefeld]

Carnivore is very real, and the us government is doing some really massive-scale data mining with it.

-f0dder (November 20, 2007, 08:56 AM)

Yes, even if they can't read the mail thanks to encryption, there's plenty of data mining to be done for traffic analysis. In it's simplest form, just the fact that you've sent mail addressed to, say, Tony Soprano is interesting. A level beyond that, seeing that you sent more volume of mail to him just before a big "job" suggests even more about you.

And this moves outward from there. Who is Mr. Soprano emailing? At the same time as his activity increases, is there a corresponding increase for someone else? Etc.

However, there's a flip side to this. You can get significant knowledge in this way, but acting on that knowledge tips your hand about what you're watching. If you want to keep getting the info, you can't actually use it, or at least not beyond what would be plausible for chance and good detective work.

This was the case during WWII. The Allies had the Japanese codes through almost the entire war, and the German codes for most of the second half. But if we took advantage of knowing all their plans, they would realize we had the codes, and we wouldn't have the benefit when we really needed it. So we had to pretend frequently that we were ignorant. It must have been very painful for the decision makers to let people die, knowing that an attack was coming but needing to preserve the pretense of surprise (and this is part of the backstory in the novel I mentioned, Cryptonomicon).

[f0dder]

This was the case during WWII. The Allies had the Japanese codes through almost the entire war, and the German codes for most of the second half. But if we took advantage of knowing all their plans, they would realize we had the codes, and we wouldn't have the benefit when we really needed it. So we had to pretend frequently that we were ignorant. It must have been very painful for the decision makers to let people die, knowing that an attack was coming but needing to preserve the pretense of surprise (and this is part of the backstory in the novel I mentioned, Cryptonomicon).

-CWuestefeld (November 20, 2007, 10:32 AM)

Yeah, evacuate the important people from pearl harbor, let a bunch of not so important people die. Wasn't just about not letting the enemy know that their messages were being intercepted, it was also to convince the american population that the world and it's war was something they should care about.

Anyway, the whole carnivore system goes beyond just logging your traffic, it's a whole big frigging associative massively cross-referenced database. Blog posts, communities, medical records - you name it.