top | item 6336178

N.S.A. Foils Much Internet Encryption

923 points| ebildsten | 12 years ago |nytimes.com

388 comments

order
[+] tc|12 years ago|reply
This is really damaging.

Not only will this cause other countries to put up barriers against US (and UK) services and products, it's going to affect uptake of standards developed here.

On the lighter side, a treasure hunt was just announced. Can you find one of these vulnerabilities, or evidence of the NSA having attacked a particular system to steal keys?

----

[Edit 1] Some speculation:

By careful hardware design -- and lots of it -- the NSA may be able to find keys large enough that we would be mildly surprised but not shocked. It's not well known that searching for many keys in parallel amortizes well -- it's much cheaper than finding all the keys individually. DJB has a great paper about this:

http://cr.yp.to/snuffle/bruteforce-20050425.pdf

If I were looking for subverted hardware, I'd be really interested in reverse engineering Ethernet chips and BMCs. The CPU would be an obvious choice as well -- could there be some sequence of instructions that enables privilege escalation?

On protocols, the best sort of vulnerability for the NSA would be the kind that is still somewhat difficult and expensive to exploit. They want the security lowered just far enough that they can get the plaintext, but not so far that our adversaries can.

There is some history with not taking timing attacks seriously enough. Perhaps careful timing observation, which the NSA is well positioned to do, could give more of an edge than we suspect. Or perhaps you could push vendors to make their products susceptible to this kind of attack, secure in the belief that it may be difficult for others to detect.

[Edit 2]

I gave a talk that discussed what I think we as engineers should do here:

https://www.youtube.com/watch?v=c7oK59DZwR4#t=1m46s

And Phil Zimmermann and I discussed a number of these issues in a Q&A session:

https://www.youtube.com/watch?v=W42i8zCEizI#t=49m55s

[+] mrb|12 years ago|reply
I think we know very well which encryption has been foiled by the NSA. This is not speculation, but quasi-certainty: 1024-bit RSA.

- Crytographers all acknowledge 1024-bit RSA is dead [1].

- Attack cost 10 years ago was estimated to be a few million USD to build a device able to crack a 1024-bit key every 12 months [2].

- "Much of" the "secure" HTTPS websites use such weak key sizes [3].

- NSA had a budget of 10.8 billion USD in 2013.

Drawing a conclusion is not very hard.

[1] http://arstechnica.com/uncategorized/2007/05/researchers-307... [2] http://www.cs.tau.ac.il/~tromer/twirl/ [3] https://www.eff.org/pages/howto-using-ssl-observatory-cloud

[+] tptacek|12 years ago|reply
I would not be at all surprised to learn that the major advance these disclosures refer to is an on-demand RSA-1024 factoring capability. RSA-1024 is already known to be unsafe (Eran Tromer estimates a 7 figure cost for a dedicated hardware cracker, which is approximately the threshold DES was at in the late '90s, when nobody believed DES was secure). On-demand offline RSA-1024 attacks would have major implications, would be a huge advance in the state of the art, but also seems feasible given an effectively unlimited budget.
[+] lambda|12 years ago|reply
One of the vulnerabilities was already discovered by researchers in 2007: http://rump2007.cr.yp.to/15-shumow.pdf

At the time, it wasn't clear if this was a deliberate backdoor or an accident, but it was proven that there there was a possibility that there was a secret key that would allow someone to predict future values of a pseudo random number generator based on previous values. Now it looks pretty clear that it was a deliberate backdoor.

This really reduces trust in US based cryptographic standards. And US based cryptographic hardware, as they mention in the article that they convinced hardware manufacturers to insert backdoors for hardware shipped overseas.

[+] grecy|12 years ago|reply
> but not so far that our adversaries can.

Please clarify what you mean by "our".

Please clarify what you mean by "adversaries".

[+] tptacek|12 years ago|reply
You can't have read Applied Cryptography from the mid-90s and not understand this to have been NSA's M.O. from the jump. Bruce Scheier, who was quoted in the Guardian piece about the same story, is America's foremost popularizer of the notion of NSA as crypto's global passive adversary. People who build real cryptosystems have never, ever been allowed to rely on the goodwill of the NSA not to cryptanalyze their systems.

Entire crypto schemes, from the RIPEMD hash to the specific parameter generation mechanism in DSA, are premised on the idea that USG-sponsored crypto concepts aren't inherently trustworthy. Similarly, all of Applied Cryptography was premised on the idea that NSA was decades ahead of commercial and academic crypto.

Of the revelations about NSA, this has to be the least revelatory (it's up/down there with the "revelation" that NSA employs teams of people whose job it is to break into Windows computers); it essentially restates something we were already supposed to have taken for granted.

That's not to say this isn't a fascinating story. It is; just keep it in context. Things to remember:

* You really want to know whether NSA is directly attacking cryptographic primitives or whether they're subverting endpoints. I think if you talk to cryptographers, you'll get a slight bias towards the belief that it's the latter: that there are implementation weaknesses at play here more than fundamental breaks in crypto.

* You want to keep in mind that breaks in cryptosystems represent new knowledge, and that the enterprise of breaking cryptosystems is an issue distinct from the public policy concern of where NSA is allowed to deploy those breaks.

* Bear in mind that in the legacy TLS security model, before things like pinning and TACK, NSA would only require a viable attack on a small subset of CAs to gain (along with pervasive network taps) massive capabilities. The payoff for these kinds of capabilities is radically degraded by the anti-surveillance mechanisms of modern browsers like Chrome, which is something you probably want to be thanking people like Adam Langley, Trevor Perrin, and Moxie Marlinspike for pushing so hard to implement.

[+] tytso|12 years ago|reply
I am so glad I resisted pressure from engineers working at Intel to let /dev/random in Linux rely blindly on the output of the RDRAND instructure. Relying solely on an implementation sealed inside a chip and which is impossible to audit is a BAD idea. Quoting from the article...

"By this year, the Sigint Enabling Project had found ways inside some of the encryption chips that scramble information for businesses and governments, either by working with chipmakers to insert back doors..."

[+] untog|12 years ago|reply
Because strong encryption can be so effective, classified N.S.A. documents make clear, the agency’s success depends on working with Internet companies — by getting their voluntary collaboration, forcing their cooperation with court orders or surreptitiously stealing their encryption keys or altering their software or hardware.

That's the money quote there- the NSA hasn't cracked encryption. They've just put back doors in.

And we can't even be that angry at the (e.g.) Microsoft execs that authorise the back doors- they potentially face jail time if they resist NSA requests. All the while presumably not able to talk about the requests publicly.

EDIT: and the really fun part - did you know the former head of the NSA serves on the board of directors for Motorola Solutions? http://en.wikipedia.org/wiki/Michael_Hayden_(general)

[+] masonhensley|12 years ago|reply
I'm guessing this is what tripped up Lavabit. Mr. Levison probably didn't have the back doors and balked at being complicit once he came onto the NSA's radar.

From the article: "Intelligence officials asked The Times and ProPublica not to publish this article, saying that it might prompt foreign targets to switch to new forms of encryption or communications that would be harder to collect or read."

Also: “Properly implemented strong crypto systems are one of the few things that you can rely on,” - Snowden

I would assume that because Snowden used Lavabit & they shut down that the NSA took issue with how secure Lavabit actually was.

[+] justincormack|12 years ago|reply
Plus (form the Guardian article) there are covert agents in all the companies, presumably lifting all the certs, which may well be unauthorised, but you can't prosecute.

Do you know who your covert agents are?

[+] philfreo|12 years ago|reply
> That's the money quote there- the NSA hasn't cracked encryption. They've just put back doors in.

It's not like they've just gotten secret keys. They've specifically gotten chip manufacturers to add backdoors to hardware, as well as significantly influenced actual cryptography standards themselves:

> "The N.S.A. wrote the standard and aggressively pushed it on the international group, privately calling the effort “a challenge in finesse.”

> “Eventually, N.S.A. became the sole editor,” the memo says.

[+] teleclimber|12 years ago|reply
That's the quote that jumped out at me too. The solution for those who want to stay out of NSA's reach is to use your own hardware, and use open source software (where it's hard to put a backdoor without being discovered) and strong encryption.
[+] Zariel|12 years ago|reply
Isn't this the fact that NSA has access to the internet companies private key for the SSL certificate? There by giving them the tools to decrypt the initial TLS handshake and then from there you can get the symmetric key and decrypt the rest? Or is there more to it, reading the article I didn't see any hard proof of this.
[+] pedrocr|12 years ago|reply
>the Bullrun program, the successor to one called Manassas — both names of American Civil War battles. A parallel GCHQ counterencryption program is called Edgehill, named for the first battle of the English Civil War of the 17th century.

Spying on your own citizens codenamed as civil war. How nice.

>Only a small cadre of trusted contractors were allowed to join Bullrun. It does not appear that Mr. Snowden was among them, but he nonetheless managed to obtain dozens of classified documents referring to the program’s capabilities, methods and sources.

Once again, the people spying on everyone suck at keeping their own secrets. How many others have taken the information with them and sold it off instead of leaking it?

>In one case, after the government learned that a foreign intelligence target had ordered new computer hardware, the American manufacturer agreed to insert a back door into the product before it was shipped,

If you're a non-US company how can you keep trusting US IT vendors? I wouldn't want to be one of these companies' reps at Airbus for example.

[+] quotemstr|12 years ago|reply
What's truly frightening is this line from the Guardian's article on the topic:

> The NSA describes strong decryption programs as the "price of admission for the US to maintain unrestricted access to and use of cyberspace".

What does that even mean? That statement is at the same time paranoid, arrogant, and subtly threatening. It's as if to say that without the ability to decrypt interesting traffic, the NSA would be forced to take stronger measures to curtail internet traffic.

[+] toyg|12 years ago|reply
Look at what's happening in the UK, in Australia, in France, in Italy, in Spain... the Chinese model is winning hearts and minds of politicians everywhere, and how could it not? If you're into politics, you likely want to reach a Platonic ideal of harmonic society, where nobody is offended, nobody is threatened, and all laws are perfectly respected and enacted. You can't have that on a fully-open network. How can you keep your people from enduring child porn and Islamic propaganda, without censorship?

So most states are slowly moving towards implementing their own little firewalls. The only notable absence? The US. Despite occasional campaigns from religious nutters of various sizes and shapes and continuous pressures from commercial telcos, subsequent US administrations repeatedly affirmed that fundamental Net freedoms would not be curtailed.

This document states that such a position is not coming from idealism or even commercial convenience: it's a way to persuade the rest of the world to do business over networks and protocols that the NSA can tap at will. Should this capability be forcefully contained, there wouldn't be a political incentive to keep the Net flowing freely through US routers.

It's a perfectly reasonable and plausible position, and that's why it's so terrifying.

[+] snowwrestler|12 years ago|reply
I think the key to understanding this is to remember that it was written by the NSA for the understanding of the NSA, or other highly authorized eyeballs in the government.

In many government documents, use of the name "U.S." is shorthand for the U.S. national government, not the entirety of the nation. Sometimes it is even shorthand for the particular agency that authored the document (since, in theory, they represent and act on behalf of the entire nation).

So what this internal NSA document most likely means by "unrestricted access and use" is the NSA's unrestricted access to, and use of, whatever data they want.

Think of it like a budget justification (since that is the purpose of at least half of all internal government reports). "You need to keep spending a lot of money on this program if you want us to keep getting all that data you like so much."

[+] ganeumann|12 years ago|reply
That was what caught my eye also. It seems to imply that if they can't read our Internet traffic then they'll have to take the US off the Internet. That's a pretty drastic threat.
[+] ihsw|12 years ago|reply
It means there are two choices for America's participation in the global internet: decryption capabilities or America's Great Firewall.

The statement implies that in the absence of "strong decryption programs" then there would be only restricted access to and use of cyberspace. I'm sure the intelligence leadership in the US Government look at China's Great Firewall with both trepidation and admiration.

[+] wiredfool|12 years ago|reply
It makes sense if "the US" = "the NSA". Stuff's been encrypted, for the NSA to continue to have access, they've gotta break it.
[+] JulianMorrison|12 years ago|reply
Up until very recently, the received wisdom was: the crypto wars are over, we fought the law and the law gave up, the NSA has quit trying to crack encryption, they have decided the USA is best strengthened by having a reliable internet which business rival nations can't just read like the morning's news. The NSA knows the problems in crypto and their suggestions make it stronger against attacks we don't know. Trust the NSA.

Would that it were true! It would make sense. This makes no damn sense. Just recently I would have ruled out huge conspiracies as implausible because they inevitably leak (roll save against ethics how many times?). The joke's on me, folks. The NSA has no sense. And the conspiracy leaked.

So now every single decision that was taken with help from the NSA (SELinux, TLS, elliptic curves, etc) needs unpicking and running by a cryptographer who isn't a shill. What a damn drag. And meanwhile, the aftershocks will run for years trashing trust in the networked economy.

Fuckin' brilliant, NSA. You screwed the pooch. You accidentally the whole internet.

[+] cbr|12 years ago|reply

    So now every single decision that was taken with help
    from the NSA (SELinux, TLS, elliptic curves, etc) needs
    unpicking and running by a cryptographer who isn't a
    shill.
Cryptographers have already been looking very carefully at everything that comes out of the NSA. Lots of security researchers, in and out of the US, would love to find NSA-introduced flaws.
[+] D_Alex|12 years ago|reply
>they inevitably leak (roll save against ethics how many times?)

Haha, nicely put. Note too that sooo many "roll save against temptation" must happen to avoid abuses of the NSA capabilities.

[+] caf|12 years ago|reply
Note that SELinux isn't crypto - it's code to implement mandatory access control, which is just regular bitbashing that any software engineer is completely qualified to audit.
[+] smutticus|12 years ago|reply
Reminds me of this: http://marc.info/?l=openbsd-tech&m=129236621626462&w=2

As someone who has been following the NSA and government monitoring of online activity for close to 15 years the Snowden leaks just keep taking the wind out of me. It's like everything that we thought might be going on was actually going on. When Theo de Raadt wrote the above mail I, like many at the time, assumed it was tinfoil hat territory. I was clearly wrong.

[+] m0nastic|12 years ago|reply
In that particular instance you weren't wrong[1], but that's the problem when stories like this come out, is that it makes it much harder to know what's a crazy conspiracy theory and what's real.

[1] Those claims made by Greg are completely untrue. I ran the professional services group for that company and will happily attest to whomever asks that at no time did we insert a backdoor (or anything that could even be construed as such) into IPSEC.

[+] 16s|12 years ago|reply
Normal people don't need 256-bit symmetric encryption. That's assault encryption and should only be used on the battlefield. 40-bits is enough and anything over that should be banned.

I'm only joking, but the same argument is used against other technologies that governments seek to control/dominate.

Edit: Skipjack was 80-bits I think. It was used in Clipper Phones: http://en.wikipedia.org/wiki/Skipjack_(cipher)

[+] albertsun|12 years ago|reply
"In one case, after the government learned that a foreign intelligence target had ordered new computer hardware, the American manufacturer agreed to insert a back door into the product before it was shipped, someone familiar with the request told The Times."

Wow.... this really puts all the furor over Huawei contracts in the US in context.

[+] donohoe|12 years ago|reply
So at this rate are there any encryption methods that we're pretty sure that the NSA cannot crack?

  By introducing such back doors, the N.S.A. has
  surreptitiously accomplished what it had failed 
  to do in the open. Two decades ago, officials 
  grew concerned about the spread of strong 
  encryption software like Pretty Good Privacy, 
  or P.G.P., designed by a programmer named Phil 
  Zimmermann. The Clinton administration fought 
  back by proposing the Clipper Chip, which 
  would have effectively neutered digital 
  encryption by ensuring that the N.S.A. always 
  had the key.
Link to Paragraph w/ highlighting: http://www.nytimes.com/2013/09/06/us/nsa-foils-much-internet...

Should I bother to read up on PGP?

[+] Zigurd|12 years ago|reply
The N.S.A. hacked into target computers to snare messages before they were encrypted. And the agency used its influence as the world’s most experienced code maker to covertly introduce weaknesses into the encryption standards followed by hardware and software developers around the world.

This is mostly a confirmation of what has been supposed: No magic, mostly bribed and coerced cooperation from the people who should be keeping our communications secure.

And while it doesn't do anything for the credibility of US-based companies, N.B.: "hardware and software developers around the world."

[+] w1ntermute|12 years ago|reply
Can someone who actually knows about encryption comment on whether it's actually physically feasible for the NSA to have actually broken, say, SSL 3.0 (which has 128 bits of entropy, IIRC) on a large scale (i.e., when you're sifting through petabytes of data on a daily basis)?

And if this were really an issue, couldn't you just use 4096-bit RSA (unless they have managed to surreptitiously insert a backdoor in it)?

[+] dailyrorschach|12 years ago|reply
This is likely a minority view, but I have no problem with the NSA being able to break encryption, that's in fact part of their job. Decoding encryption has long been part of their mission. I also suspect they're not alone in terms of signals intelligence groups in having this capability.

The issue to me has always been how and what data they access and store, and how it is used.

[+] haakon|12 years ago|reply
The larger issue here is that they "covertly introduce weaknesses into the encryption standards". It's not that they cleverly and fairly break encryption, it's that they sabotage the standards.
[+] a3n|12 years ago|reply
I guess I'm with you on the ability to crack. Any researcher should be able to try as hard as they want, and succeed.

I draw the line at collecting everything without specific warrants, regardless of what they do with it, against their charter and the Constitution.

I draw the line at hardware backdoors for equipment that I buy, and insertion of vulnerabilities into encryption standards that I take advantage of. Or I guess I should say that take advantage of me.

[+] jonknee|12 years ago|reply
> I have no problem with the NSA being able to break encryption, that's in fact part of their job.

Their "breaking" of encryption is a combination of purposefully introducing vulnerabilities into standards, surreptitiously altering software and hardware to give the NSA a backdoor, hacking into private systems and stealing keys, etc etc.

I'm cool with an NSA super computer trying to brute force my VPN traffic to YouTube, I'm not cool with the NSA planting an engineer at a chip fab and changing designs to add a backdoor (a backdoor that could also be exploited by other actors).

[+] mhurron|12 years ago|reply
If the NSA can, others can. It makes the whole thing useless.
[+] stdgy|12 years ago|reply
The problem isn't that they're working to break encryption. The problem is that they're maliciously inserting backdoors and subverting crypto-research and publication, which puts all of our security at risk. (Not to mention runs counter to their stated mission)
[+] alasdair_|12 years ago|reply
There are a couple of other issues, even if one agreed with your view:

1. They obviously can't keep their own secrets, so it's unlikely that they will do any better than keeping yours. Eventually, your data will leak out to non-NSA people.

2. By adding backdoors, they weaken the encryption. This implies that anyone with sufficient skill who goes looking for backdoors may be able to exploit the hole that the NSA opened up. This is a big deal, especially if you have secrets that you need to protect.

[+] junto|12 years ago|reply
There is an old saying that states that a jealous husband or wife can't be trusted. They don't trust you because they are, have, or are thinking about fucking someone else.

When the combined '5 eyes' come out and ban Lenovo / Huawei from being used on any of their secure networks, because of fears of back doors [1], one has to imagine that the same is true of themselves.

The hardware is most likely backdoored as well as firmware, the OS and installed software. I would not trust anything, even open source, because to be perfectly honest, there a very few people who really are smart enough to understand the in depth cryptographic requirements. If there are people, then they probably already work for the NSA or GCHQ.

If you want to plan a terrorist attack or become a politician or business leader who does not want to be blackmailed, don't do anything on the internet apart from share pictures of cute cats.

My advice to any terrorists is to go dark. Speak in private. Write it down pass the note and then burn it. Use old methods like book ciphers. Touch and electronic device and they have you.

Legal note: Of course I'm not advocating 'advising' terrorists, well only the good ones, you know those ones that we call 'freedom fighters'. The ones western governments like to back when it suits their purposes.

[1] http://www.infosecurity-magazine.com/view/33679/lenovo-compu...

[+] mindslight|12 years ago|reply
I feel like these kinds of articles are meant to induce a sense of hopelessness regarding the ability to push back against the NSA.

If it turns out one way functions actually don't exist, I'll give in and learn to love big brother. Withstanding that, I'll continue considering communications freedom (and all that it implies) as our manifest right and view these types of breaks as implementation errors.

[+] 16s|12 years ago|reply
Some organizations have IT security departments that attempt to foil encryption already. They use devices to terminate SSL before it leaves their network and forge certs back to clients and basically act as a MITM for the clients making the TLS/SSL request. They do this to inspect the traffic before it leaves the network.

I predict that in the next 5 to 10 years, many organizations across all industry sectors will drop/reject encrypted packets (SSL, SSH, SFTP, etc) that they cannot decrypt. And the reason they'll give is that it makes them more secure.

The concern I have (as a security technologist) is that most people who use encryption are not bad, however everyone is punished and every packet must now be inspected because a few people use encryption to do bad things. So one day soon, I'm afraid that anyone who uses encryption will be suspect simply because they do and the stronger the encryption, then the more suspect they'll be.

Will it become illegal to do encryption research or use OpenPGP unless you agree to escrow your private key or will everyone be forced to use very weak ciphers? In today's climate (encryption is evil), I see all of these things as very real possibilities.

[+] csense|12 years ago|reply
Speaking as an American, it's not a problem that the capability to break encryption exists and the NSA has it. It really does make national security stronger if your intelligence people can read enemy communications.

The problem is that the NSA apparently used those capabilities on basically everyone, millions of innocent Americans whose activities should be of no interest to intelligence agencies, not just the handful of genuine spooks and terrorists our intelligence agencies are supposed to protect us from. (To international people: Cosmically speaking, you're not less important than we are, but the NSA's first responsibility is to protect and serve the USA, so them spying on innocent Americans is at least as bad as them spying on innocent foreigners.)

And it has been shown that the NSA provided information to ordinary criminal investigations with no links to terrorism or foreign intelligence, having police say "it's a lucky traffic stop," where the government actually knew the drugs were in that car ahead of time due to a decrypted phone call. This makes a mockery of the Fourth Amendment because, when prosecutors/police lie to the courts about the origin of evidence, the courts cannot properly answer the question of whether their methods of gathering evidence violate the defendant's Constitutional protection against unreasonable search and seizure.

In short, this is coming out -- which, as the article said, will weaken those capabilities -- because the NSA went too far outside their mission scope. If they hadn't done those two things, I'd be willing to bet Snowden wouldn't have leaked this data.