Matthew Green Speculates on How the NSA Defeats Encryption

This blog post is well worth reading, and not just because Johns Hopkins University asked him to remove it, and then backed down a few hours later.

Posted on September 11, 2013 at 11:53 AM • 45 Comments

Comments

AlexSeptember 11, 2013 12:09 PM

+1 for his use of a still shot from Das Leben der Anderen a.k.a. Lives of Others. in his blog post. I'd encourage everyone to watch it. (C'mon, watch it this week. It's on Netflix & Amazon streaming). It's a movie based on the life of a Stasi agent in East Germany. The movie makers went to great extremes to keep things authentic, using Stasi buildings, original equipment, and own policy books to re-enact what had occurred.

I'm still reading the article, will be back later after I finish it.

Nick PSeptember 11, 2013 12:26 PM

The point that jumped out at me is that the foundation of OpenSSL was one guy's attempt to learn Bignum division. And then they build much complexity on that. And then it's used in Apache and many commercial products. Inspires a whole lot of trust, eh Bruce?

bobSeptember 11, 2013 12:37 PM

I dont understand why no one has made a screen saver (like SETI at home) that when your PC is idle it just constantly sends craploads of random (but plausible looking) encrypted emails all over the world, just to give NSA something to do with all that spare time they obviously have. Could even salt them with interesting keywords for them to find, like an easter egg hunt.

Could call it Anonev.

JeffHSeptember 11, 2013 12:44 PM

@bob - Most people would call this spam (where would you send the emails to?), and even if allowed, it'd be easy to filter unless lots of people did it to lots of different addresses.

The better solution is to actually require all emails to be encrypted, but that hasn't taken off *ever*. Just not practical.

AliceSeptember 11, 2013 12:46 PM

@bob
(for debate purposes)


So the NSA can waste more Tax dollars monitoring US citizen data as they will need to grow their ability to collect and analyze?

jonesSeptember 11, 2013 1:02 PM

I'm about halfway through the article now, but some of this has been known for a while. Specifically, the 56-bit key used in DES has long been known to be a compromise between the NSA's ability to crack codes and industry's need for security (that is, cracking a 56-bit key was within NSA ability, but just beyond the reach of industrial rivals).

JeffHSeptember 11, 2013 1:10 PM

Not having been in such crypto circles, I found it mildly astonishing that we use NIST standards without the experts involved in said actually understanding how the whole standard works (as it is implied that the NSA weakens standards by first writing - much talk of sole author, even - and then obfuscating the standard enough that it appears secure to independent experts without being so).

It would be easy to go 'oh, why did we rely on a US institution to write standards for the world, surely we should have seen this coming', but truth be told, pretty much any organisation anywhere could be infiltrated, coerced, or just plain have the political motivation to screw something up. That's why I find it more concerning that, regardless of the source of the standard, that the entire thing isn't dramatically more transparent and until a lot of independent people say it's ok, the standard doesn't go through.

Or are those in the know saying that even that has failed?

ClockerSeptember 11, 2013 1:18 PM

Suppose that RSA is vulnerable to some type of attack by the NSA (1024 bit, maybe higher?). Would communication still be secure, if two people exchange public keys in person, never make those keys public, and never use them with anyone else?

GeorgeVSeptember 11, 2013 2:46 PM

Time to use DJB's NaCl instead of OpenSSL, perhaps?

We should also take a look at his Salsa20 algorithm and his ECC curves.

DanielSeptember 11, 2013 2:50 PM

From the article: "now people will have to verify."

It is simply unrealistic and I do not toss out that phrase lightly. How is the average person supposed to verify, for example, that the Linux kernel doesn't have a backdoor or that their download of it wasn't hijacked by a MitM attack?

Back in the bygone days there was a huge debate in the Catholic church about whether salvation was for monks alone (those who lived "perfect" lives) or whether salvation was available to sinners too. The Church rejected the former an embraced the latter, hence practices like confession to the priest.

I see a lot of security pros taking the monkish position: that in order to have any realistic chance at being secure one has to be a security professional. That isn't a sustainable long-run model. The church recognized, in my opinion correctly, that many people simply did not have the self-discipline let alone the interest in being monks. So if salvation was going to work for the ordinary person concepts like the Saints, and forgiveness, etc had to be implemented.

Don't ask me to verify. I do not have the time, the inclination, and in some cases the ability to do that. Figure something else out security pros.

braffSeptember 11, 2013 3:00 PM

@ Daniel sept 11 2:50 PM
Very well said. But since code for security and integrity always have to be audited, and since that is a near-monkish skill, we still need the monks. So I guess what we normal lusers need is a system of reliable trust concerning the integrity of the cryptocode-monks?

gonzoSeptember 11, 2013 3:52 PM

The government programs, approaches, and tactics often "echo" between different segments.

We know, for example, that the United States avoided problems with violations of torture rules for things like water boarding etc. by farming these operations out to other countries.

The big shoe to fall, in my view, will be if it turns out our intelligence aparatus has been sharing "raw" data collected (aggregated, stored, whatever non-typical usage they have in mind for the interception and keeping of content) and then sending this to an ally over seas for their use -- probably G.B. or Israel, but possibly also to include France.

If that shoe falls in this story, we can be assured that even well beyond the violations of FISA oversight, there would exist a well oiled machine for harvesting and targeting Americans, only "our" intelligence agencies would not technically be the ones doing it.

DavidSeptember 11, 2013 3:57 PM

So far, the best comment I've heard about the encryption is this:
How do you pass a HIPPA or PCI audit when you know that much of the encryption is either being bypassed or broken by the NSA and who knows else???
Answer: You can't, and thus every American company is under violation of HIPPA laws and should be punished with damages.

Wrap your brain around that Congress :-)

HermanSeptember 11, 2013 4:15 PM

So the third shoe has now dropped. According to the Guardian, the NSA shares raw US data with both the UK and Israel. Other reports indicated they even collect credit card numbers. The fourth shoe to drop would be once the Guardian finds a document that indicates data sharing with Russia. All this may explain why I regularly need new credit cards due to fraudulent activity in my accounts.

DNS666September 11, 2013 5:05 PM

@gonzo
>The big shoe to fall, in my view, will be if it turns out our
>intelligence aparatus has been sharing "raw" data
>collected(aggregated, stored, whatever non-typical usage
>they have in mind for the interception and keeping of
>content) and then sending this to an ally over seas for
>their use -- probably G.B. or Israel, but possibly also to
>include France.

You mean like this?
-> http://www.theguardian.com/world/2013/sep/11/...

ThecaseforpeaceSeptember 11, 2013 5:07 PM

@David

I had a conversation with my whole team to the exact same effect last week. This puts everybody in a whole lot of trouble especially fiduciary institutions.

These revelations are the death toll to the US involvement in the international "cloud" industry. Billions will be lost to international competitors who have better privacy regulations. All that is needed is a country to step up and provide "Switzerland" like privacy laws on data and all the data will flee. There won't be so much as an itunes playlist stored in the USA.

gonzoSeptember 11, 2013 5:29 PM

@DNS666

I was thinking _sort of_ along those lines, and that story is disconcerting, but probably more "off the books" than that looks. Even under what the guardian is reporting, there are still some checks and at least a nod to Americans' privacy rights.

No, what I was really thinking of is a mainline of the data from the US data centers to off-shore "storage" services where, in actuality, persons hired by the US sift through the material with no checks or balances at all.

DNS666September 11, 2013 5:47 PM

@gonzo
The "Five Eyes" (US, UK, CA, NZ, AUS) share raw intelligence data. That much is known (and has been for a long time, actually).

The "checks and balances" outlined in the US-Israel agreement are a joke (and not even legally binding as per the document itself).

@gonzoSeptember 11, 2013 6:01 PM

@dns666

A good point. Maybe that shoe has fallen as well. The big reveal in that article I did not catch in my first readthrough is that they're sharing unfiltered sigint. Big issue there.

And still the press will yawn, the big providers will take their customers money advertising privacy and the government's money to break privacy, and the engineers and academics will continue to write papers about the math while being "too good" to dig into the implementations.

What we really need is a fund that pays brilliant coders and cryptographers to look into the implementations like truecrypt and others.

DNS666September 11, 2013 6:17 PM

@gonzo

Indeed, the point is raw SIGINT is apparently shared w/ Israel under laughably shady conditions re. privacy protections. Also note the distinction between normal citizens' and government officials' data in the source doc. One wonders how NSA even might have data on, say, Congress members. Anyway, there's your two class society right there.

Re. purely academic crypto maths vs. hands-on crypto implementation and auditing: We need both, now more than ever, methinks. But we sure could use more people who have a solid grounding in both the math and the coding. Those tend to be rare beasts, though.

kingsnakeSeptember 11, 2013 6:42 PM

Das Leben der Anderen is one of the five best movies I have ever seen. I get shivers thinking about it, and not because our government resembles the Stasi ...

RobertTSeptember 11, 2013 6:44 PM

When I read the Guardian story I could not get beyond the basic fact that the NSA wanted to reduce the incidence of average people using encryption on emails. So logically what steps could the NSA take to reduce the incidence of Email encryption? is it
a) create the belief that the PGP encryption is so good that even the NSA cant break it.
OR
b) foster the belief that encryption is a complete waste of time because everyone knows the NSA has systemically backdoored the whole process.

I think its case (b)

The truth is that even fairly basic encryption is extremely difficult to break(read compute intensive to brute force) AND even the most revealing of side channel attacks dont produce plain text, rather they just substantially weaken the encryption (unless you're talking full end run).

System End runs normally need to create hidden communications channels. Makes me wonder if the real help provided by these US companies is not via way of direct access to the raw internet comms so that the hidden sub channels can be decoded? Hmmm

Oh well my take is that real world security encryption is very strong but real world computing systems are very weak.

sscoobySeptember 11, 2013 8:18 PM

JHU's censorship was very likely the outcome of the absurd DoD policy of requiring people with security clearances to report incidents of reading the news.

"It is the responsibility of every DoD employee and contractor to protect classified information and to follow established procedures for accessing classified information only through authorized means." ...

"DoD employees or contractors who inadvertently discover potentially classified information in the public domain shall report its existence immediately to their Security Manager. Security Managers and Information Assurance Managers are instructed to document the occurrence and report the event to the Director of Security Policy and Oversight, Office of the Under Secretary of Defense for Intelligence (OUSD(I)). The offending material will be deleted by holding down the SHIFT key while pressing the DELETE key for Windows-based systems and clearing of the internet browser cache."

ActualFirstNameSeptember 11, 2013 8:32 PM

I think this really highlights the problem with completely trusting open source cryptography solely because it is open source. The thinking goes "Open source means anyone can review it, therefore it's safe".

The reality is that there are few people who have the ability to competently review source code for cryptographic software, or NIST standards. Fewer still have the time to do so. Fewer still actually will. Even then, they can make mistakes.

That said, open source is better than closed. I trust it more than closed source software and always will. But I'm not shocked that backdoors are being inserted in open source stuff, and even standards. OpenSSL and NIST standards are used everywhere. Of course the NSA will go after them. It would be foolish for them not to.

Aaron WSeptember 11, 2013 9:02 PM

bob said:
"I dont understand why no one has made a screen saver (like SETI at home) that when your PC is idle it just constantly sends craploads of random (but plausible looking) encrypted emails all over the world, just to give NSA something to do with all that spare time they obviously have."

Cory Doctorow proposed something very similar in Little Brother -- a distro called Paranoid Linux that forced a Tor connection, and for every web page you loaded, it loaded another 6 pages at random in the background.

NobodySpecialSeptember 11, 2013 10:54 PM

@sscooby that was the old security joke - you shouldn't read Pravda because it might reveal some Nato secret you weren't cleared for.

Christian RothSeptember 12, 2013 2:25 AM

Prof. Matthew Green was forced to remove the NSA logo from his blog post. He replaced it with a photo from the German Movie "Das Leben der Anderen" depicting an Eastern German Stasi officer eavesdropping on innocent citizens.

Original Blog Post

Updated Blog Post

Prof. Green, that is so subtle, yet so classy. You are my hero of the day!

Wesley ParishSeptember 12, 2013 3:18 AM

@gonzo and @DNS666 the really interesting thing is that Israel ignores the US trade embargoes etc, with impunity - see J-10 (Jian-10 Fighter aircraft 10) / F-10 on how the cancelled IAI Lavi got a new lease of life as the J-10 in the PRC.

Now add to that the comment I saw a year or two back in Haaretz - or it may have been another Israeli news outlet - commenting that since the US was looking rather sick, it was time to look for some new host. And they've got all this economically valuable data about US private citizens ... and if it's not economically valuable, then Google et alii are on a wild goose chase ...

That's not a conspiracy theory, btw, it's more a marketing projection. FWLIW.

TlaSeptember 12, 2013 3:20 AM

@RobertT "So logically what steps could the NSA take to reduce the incidence of Email encryption?"

(c) Ask Gmail, Yahoo and the likes not to add support for encrypted mail content (Proof that it is technically bearable: Thunderbird has a nice support for encrypted mail content).

AdamSeptember 12, 2013 3:24 AM

In order to "take back the web", perhaps it's time to produce an httpx protocol which properly addresses the problems with TLS, with the non-existent "trust" from CAs, with all the fallbacks & bandaids in TLS/SSL to broken or reduced forms of crypto.

Basically start afresh with something that at the very least guarantees all traffic is encrypted with a session key (even if it is still vulnerable to man in the middle it's better than nothing). But which steps up to support certs, certs signed with a web of trust etc. Browsers would be left with the problem of presenting a meaningful representation of the security proffered during the session (e.g. a traffic light system with a drop down check list of what the connection protects against - casual eavesdropping, man in the middle attacks, replay attacks etc.)

A true web of trust where businesses & organisations can can sign their cert with meaningful relationships rather than to just one CA. Imagine if the Bank of Abu Dhabi could sign its cert with the Bank of Qatar, the Abu Dhabi government, the International Monetary Fund etc.

I don't think this is an unreasonable thing to embark on but it needs a nucleus of support from prominent interested parties who know what they are doing and would do it in an open environment.

NullNillNoneSeptember 12, 2013 3:39 AM

@Adam: Your approach suffers from the same shortcomming as the current system. How do you know that the API that gives the green light is legit and can be trusted?
How do you know that the generated keys are strong and secure?

JacobSeptember 12, 2013 5:01 AM

From http://csrc.nist.gov/publications/nistbul/...

"In light of the concerns expressed regarding Dual_EC_DRBG, ITL is taking the following actions:

Recommending against the use of SP 800-90A Dual Elliptic Curve Deterministic Random Bit
Generation:
NIST strongly recommends that, pending the resolution of the security concerns and the re-issuance of SP 800-90A, the Dual_EC_DRBG, as specified in the January 2012 version of SP 800-90A, no longer be used.
Re-issuing SP 800-90A as a draft for public comment: Effective immediately, NIST Special Publication 800-90A is being re-issued as a draft for public comment for a period ending November 6, 2013. Any concerns or recommendations for improvement regarding the Recommendation for Random Number Generation Using Deterministic Random Bit Generators are solicited "

DavidSeptember 12, 2013 7:21 AM

@Jacob • September 12, 2013 5:01 AM

I hope NIST is beginning to recognize the reputational risk in being used as a means of promulgating NSA security vulnerabilities.

secret policeSeptember 12, 2013 8:12 AM

Anybody else notice "Quick Ant Tor QFD" in the leaked "Flying Pig" tracking software slides? They are tampering with Tor and breaking their own dissident network. If the NSA can reduce public key entropy and track everybody so can their adversaries. As for NIST they are now grovelling about this and promised a full review, but nobody will ever trust them again.

evil empireSeptember 12, 2013 9:55 AM

secret police


Anybody else notice "Quick Ant Tor QFD" in the leaked "Flying Pig" tracking software slides?

that sort of would not surprise me, considering the current situation. Tor is a honeytrap for wannabe dissidents.

Someone else commented on this blog (over a year ago) that they had checked the origin of TOR ip-addresses and they supposedly all came from Maryland.

Michael BradySeptember 12, 2013 10:55 AM

Christian Roth

+1

Prof. Matthew Green was forced to remove the NSA logo from his blog post. He replaced it with a photo from the German Movie 'Das Leben der Anderen' depicting an Eastern German Stasi officer eavesdropping on innocent citizens. Prof. Green, that is so subtle, yet so classy. You are my hero of the day!

The Lives of Others http://www.imdb.com/title/tt0405094/ finely-crafted historical drama, prescient cautionary tale, and training film...

antonio cSeptember 12, 2013 12:01 PM

@Adam


In order to "take back the web", perhaps it's time to produce an httpx protocol which properly addresses the problems with TLS, with the non-existent "trust" from CAs, with all the fallbacks & bandaids in TLS/SSL to broken or reduced forms of crypto.

We should also have our own routers that do not have the traditional separation between IP-addresses and URLs but some sort of scheme where the URL corresponds (converts) directly to a (hexadecimal?) ip-address.

Edd BlackSeptember 12, 2013 12:05 PM

Devil's Advocate what if ...

What if the NSA doesn't have the capabilities to the extent discussed? As when he's talking about the Intel Secure Keys:

Even if there's no problem, it's going to be an awfully hard job selling these internationally after today's news.

What if the goal is to push people to technologies they have cracked?

DavidSeptember 12, 2013 1:44 PM

@Edd Black

This whole affair is hugely damaging to the NSA's interests. It's highly unlikely it was orchestrated by the NSA.

It's also unlikely that they would have been able to insert themselves into the process in such a way as to seed false leads among the true revelations.

MarkHSeptember 12, 2013 3:09 PM

@NullNillNone

"Your approach suffers from the same shortcomming as the current system."

No -- in the current system, smart or powerful criminals (I mean this term to include NSA, now revealed as a criminal organization) can subvert certificate authorities EVEN IF THE CRYPTO TECHNOLOGY IS GOOD.

What Adam proposes -- essentially, as I recall, what Phil Zimmerman was proposing years ago -- would substantially end that vulnerability.

It is not a reasonable test of a security mechanism, that it close every possible attack vector. Defeating one vector -- especially the CA vector that has been known for years to be a gaping hole in the entire PKI system -- would not only be progress, but is (I think) essential to improving communication security.

Clive RobinsonSeptember 12, 2013 4:23 PM

@ Adam,

Whilst the "web of trust" was a nice idea it has a number of short commings.

One of which I call the "Facebook effect" on Facebook to many people "friend" way to many people, which means the trust may well be in effect diluted to meaningless.

Another is like reputations on E-Bay, in that sufficient accounts under the control of an entity can be used to favourably cross post a reputation upwards.

Then there is the unavoidable distance metric, I might well havr a meat space friend who would vouch for a book shop local to me, I doubt I know anybody personaly who could vouch for a book shop in New Zeland.

What we need is a hybrid system of some kind...

BuckSeptember 12, 2013 7:34 PM

@Clive

You may not personally know anybody in New Zealand who could vouch for a book shop, but you might trust a friend's reccomendation of a person (s)he knows in New Zealand who loves to read. Certainly one of your friends' friends at least knows someone (most likely, more than one) who's been to New Zealand!

I think any "web of trust" should have a level of granularity based on types of trust... I may trust Alice's taste in music, whilst I may trust Bob's ability to reliably & securely store copies of some of my encrypted data.

I've tried to think of a digital key protocol which would require an initial exchange to be done in meat space, but no luck thus far... :-\

Bonus points if the protocol could somehow boost confidence based on further mutual meat space meetings! And how to account for trust in corporations or groups of people..?

Leave a comment

Allowed HTML: <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre>

Photo of Bruce Schneier by Per Ervland.

Schneier on Security is a personal website. Opinions expressed are not necessarily those of Co3 Systems, Inc..