Is Apple’s Cloud Key Vault a crypto backdoor?

TL;DR: No, it isn’t. If that’s all you wanted to know, you can stop reading.

Still, as you can see there’s been some talk on Twitter about the subject, and I’m afraid it could lead to a misunderstanding. That would be too bad, since Apple’s new technology is kind of a neat experiment.

So while I promise that this blog is not going to become all-Apple-all-the-time, I figured I’d take a minute to explain what I’m talking about. This post is loosely based on an explanation of Apple’s new escrow technology that Ivan Krstic gave at BlackHat. You should read the original for the fascinating details.

What is Cloud Key Vault (and what is iCloud Keychain)?

A few years ago Apple quietly introduced a new service called iCloud Keychain. This service is designed to allow you to back up your passwords and secret keys to the cloud. Now, if backing up your sensitive passwords gives you the willies, you aren’t crazy. Since these probably include things like bank and email passwords, you really want these to be kept extremely secure.

And — at least going by past experience — security is not where iCloud shines:

The problem here is that passwords need to be secured at a much higher assurance level than most types of data backup. But how can Apple ensure this? We can’t simply upload our secret passwords the way we upload photos of our kids. That would create a number of risks, including:

  1. The risk that someone will guess, reset or brute-force your iCloud password. Password resets are a particular problem. Unfortunately these seem necessary for normal iCloud usage, since people do forget their passwords. But that’s a huge risk when you’re talking about someone’s entire password collection.
  2. The risk that someone will break into Apple’s infrastructure. Even if Apple gets their front-end brute-forcing protections right (and removes password resets), the password vaults themselves are a huge target. You want to make sure that even someone who hacks Apple can’t get them out of the system.
  3. The risk that a government will compel Apple to produce data. Maybe you’re thinking of the U.S. government here. But that’s myopic: Apple stores iCloud data all over the world.

So clearly Apple needs a better way to protect these passwords. How do to it?

Why not just encrypt the passwords?

It is certainly possible for an Apple device to encrypt your password vault before sending it to iCloud. The problem here is that Apple doesn’t necessarily have a strong encryption key to do this with. Remember that the point of a backup is to survive the loss of your device, and thus we can’t assume the existence of a strong recovery key stored on your phone.

This leaves us with basically one option: a user password. This could be either the user’s iCloud password or their device passcode. Unfortunately for the typical user, these tend to be lousy. They may be strong enough to use as a login password — in a system that allows only a very limited number of login attempts. But the kinds of passwords typical users choose to enter on mobile devices are rarely strong enough to stand up to an offline dictionary attack, which is the real threat when using passwords as encryption keys.

(Even using a strong memory-hard password hash like scrypt — with crazy huge parameters — probably won’t save a user who chooses a crappy password. Blame phone manufacturers for making it painful to type in complicated passwords by forcing you to type them so often.)

So what’s Apple to do?

So Apple finds itself in a situation where they can’t trust the user to pick a strong password. They can’t trust their own infrastructure. And they can’t trust themselves. That’s a problem. Fundamentally, computer security requires some degree of trust — someone has to be reliable somewhere.

Apple’s solution is clever: they decided to make something more trustworthy than themselves. To create a new trust anchor, Apple purchased a bunch of fancy devices called Hardware Security Modules, or HSMs. These are sophisticated, tamper-resistant specialized computers that store and operate with cryptographic keys, while preventing even malicious users from extracting them. The high-end HSMs Apple uses also allow the owner to include custom programming.

Rather than trusting Apple, your phone encrypts its secrets under a hardcoded 2048-bit RSA public key that belongs to Apple’s HSM. It also encrypts a function of your device passcode, and sends the resulting encrypted blob to iCloud. Critically, only the HSM has a copy of the corresponding RSA decryption key, thus only the HSM can actually view any of this information. Apple’s network sees only an encrypted blob of data, which is essentially useless.

When a user wishes to recover their secrets, they authenticate themselves directly to the HSM. This is done using a user’s “iCloud Security Code” (iCSC), which is almost always your device passcode — something most people remember after typing it every day. This authentication is done using the Secure Remote Password protocol, ensuring that Apple (outside of the HSM) never sees any function of your password.

Now, I said that device passcodes are lousy secrets. That’s true when we’re talking about using them as encryption keys — since offline decryption attacks allow the attacker to make an unlimited number of attempts. However, with the assistance of an HSM, Apple can implement a common-sense countermeasure to such attacks: they limit you to a fixed number of login attempts. This is roughly the same protection that Apple implements on the devices themselves.

The encrypted contents of the data sent to the HSM (source).

The upshot of all these ideas is that — provided that the HSM works as designed, and that it can’t be reprogrammed — even Apple can’t access your stored data except by logging in with a correct passcode. And they only get a limited number of attempts to guess correctly, after which the account locks.

This rules out both malicious insiders and government access, with one big caveat.

What stops Apple from just reprogramming its HSM?

This is probably the biggest weakness of the system, and the part that’s driving the “backdoor’ concerns above. You see, the HSMs Apple uses are programmable. This means that — as long as Apple still has the code signing keys — the company can potentially update the custom code it includes onto the HSM to do all sort sorts of things.

These things might include: programming the HSM to output decrypted escrow keys. Or disabling the maximum login attempt counting mechanism. Or even inserting a program that runs a brute-force dictionary attack on the HSM itself. This would allow Apple to brute-force your passcode and/or recover your passwords.

Fortunately Apple has thought about this problem and taken steps to deal with it. Note that on HSMs like the one Apple is using, the code signing keys live on a special set of admin smartcards. To remove these keys as a concern, once Apple is done programming the HSM, they run these cards through a process that they call a “physical one-way hash function”.

If that sounds complicated, here’s Ivan’s slightly simpler explanation.

So, with the code signing keys destroyed, updating the HSM to allow nefarious actions should not be possible. Pretty much the only action Apple can take is to  wipe the HSM, which would destroy the HSM’s RSA secret keys and thus all of the encrypted records it’s responsible for. To make sure all admin cards are destroyed, the company has developed a complex ceremony for controlling the cards prior to their destruction. This mostly involves people making assertions that they haven’t made copies of the code signing key — which isn’t quite foolproof. But overall it’s pretty impressive.

The downside for Apple, of course, is that there had better not be a bug in any of their programming. Because right now there’s nothing they can do to fix it — except to wipe all of their HSMs and start over.

Couldn’t we use this idea to implement real crypto backdoors?

A key assertion I’ve heard is that if Apple can do this, then surely they can do something similar to escrow your keys for law enforcement. But looking at the system shows isn’t true at all.

To be sure, Apple’s reliance on a Hardware Security Module indicates a great deal of faith in a single hardware/software solution for storing many keys. Only time will tell if that faith is really justified. To be honest, I think it’s an overly-strong assumption. But iCloud Keychain is opt-in, so individuals can decide for themselves whether or not to take the risk. That wouldn’t be true of a mandatory law enforcement backdoor.

But the argument that Apple has enabled a law enforcement backdoor seems to miss what Apple has actually done. Instead of building a system that allows the company to recover your secret information, Apple has devoted enormous resources to locking themselves out. Only customers can access their own information. In other words, Apple has decided that the only way they can hold this information is if they don’t even trust themselves with it.

That’s radically different from what would be required to build a mandatory key escrow system for law enforcement. In fact, one of the big objections to such a backdoor — which my co-authors and I recently outlined in a report — is the danger that any of the numerous actors in such a system could misuse it. By eliminating themselves from the equation, Apple has effectively neutralized that concern.

If Apple can secure your passwords this way, then why don’t they do the same for your backed up photos, videos, and documents?

That’s a good question. Maybe you should ask them?

On the Juniper backdoor

You might have heard that a few days ago, Juniper Systems announced the discovery of “unauthorized code” in the ScreenOS software that underlies the NetScreen line of devices. As a result of this discovery, the company announced a pair of separate vulnerabilities, CVE-2015-7755 and CVE-2015-7756 and urged their customers to patch immediately.

The first of these CVEs (#7755) was an authentication vulnerability, caused by a malicious hardcoded password in SSH and Telnet. Rapid7 has an excellent writeup of the issue. This is a pretty fantastic vulnerability, if you measure by the impact on security of NetScreen users. But on the technological awesomeness scale it rates about a two out of ten, maybe a step above ‘hit the guy with a wrench‘.

The second vulnerability is a whole different animal. The advisory notes that CVE-7756 — which is independent of the first issue — “may allow a knowledgeable attacker who can monitor VPN traffic to decrypt that traffic.” This is the kind of vulnerability that makes applied cryptographers cry tears of joy. It certainly did that for me:

 

And while every reasonable person knows you can’t just drop “passive decryption vulnerability” and expect the world to go on with its business, this is exactly what Juniper tried to do. Since they weren’t talking about it, it fell to software experts to try to work out what was happening by looking carefully at firmware released by the company.

Now I want to be clear that I was not one of those software experts. IDA scares the crap out of me. But I’m fortunate to know some of the right kind of people, like Steve Checkoway, who I was able to get on the job, mostly by encouraging him to neglect his professional obligations. I also follow some talented folks on Twitter, like H.D. Moore and Ralf Philipp Weinmann. So I was fortunate enough to watch them work, and occasionally (I think?) chip in a helpful observation.

And yes, it was worth it. Because what Ralf and Steve et al. found is beyond belief. Ralf’s excellent post provides all of the technical details, and you should honest just stop reading now and go read that. But since you’re still here, the TL;DR is this:

For the past several years, it appears that Juniper NetScreen devices have incorporated a potentially backdoored random number generator, based on the NSA’s Dual_EC_DRBG algorithm. At some point in 2012, the NetScreen code was further subverted by some unknown party, so that the very same backdoor could be used to eavesdrop on NetScreen connections. While this alteration was not authorized by Juniper, it’s important to note that the attacker made no major code changes to the encryption mechanism — they only changed parameters. This means that the systems were potentially vulnerable to other parties, even beforehand. Worse, the nature of this vulnerability is particularly insidious and generally messed up.

In the rest of this post I’m going to try to fill in the last part of that statement. But first, some background.

Dual EC DRBG

Pretty much every cryptographic system depends on a secure random number generator, or RNG. These algorithms produce the unpredictable random bits that are consumed by cryptographic protocols. The key word in this description is unpredictable: if an attacker can predict the output of your RNG, then virtually everything you build on it will end up broken.

This fact has not been lost on attackers! The most famous (alleged) example of deliberate random number generator subversion was discovered in 2007 by Dan Shumow and Neils Ferguson from Microsoft, when they announced the possibility of a backdoor in a NIST standard called Dual_EC_DRBG.

I’ve written extensively about the design of the Dual_EC generator and the process that led to it its standardization. Omitting the mathematics, the short version is that Dual EC relies on a special 32-byte constant called Q, which — if generated by a malicious attacker — can allow said attacker to predict future outputs of the RNG after seeing a mere 30 bytes of raw output from your generator.

The NIST specification of Dual_EC comes with a default value for Q that was generated by the NSA. Nobody has ever been able to determine how NSA generated this value, but leaks by Edward Snowden in 2013 provide strong evidence that NSA may have generated it maliciously. It certainly doesn’t smell good.

But enough with the ancient history. We’re here to talk about Juniper.

Juniper ScreenOS — before the “unauthorized code”

Although it was not widely publicized before this week, Juniper’s ScreenOS devices have used Dual EC for some time — probably since before Juniper acquired NetScreen Technologies. Prior to this week, the only place you might have learned about this was on this tiny page posted by the company after the Snowden leaks.

The decision to use Dual EC is strange all by itself. But it gets weirder.

First, ScreenOS doesn’t use the NSA’s default Q. Instead, they use an alternative Q value that was generated by Juniper and/or NetScreen. If Juniper had really wanted to rule out the possibility of surveillance, this would have been a good opportunity to do so. They could have generated the new constant in a “provably” safe way — e.g., by hashing some English-language string. Since we have no evidence that they did so, a conservative view holds that the Juniper/NetScreen constant may also have been generated maliciously, rendering it useful for eavesdropping.

Next, ScreenOS uses Dual EC in a strange, non-standard way. Rather than generating all of their random numbers with Dual EC (which would be slow), they only use Dual EC to generate a seed for a fast 3DES-based generator called ANSI X9.17. Since that generator is actually FIPS-140 approved and generally believed to be sufficient to the purpose, it’s not clear what value Dual EC is really adding to the system in the first place — except, of course, its usefulness as a potential backdoor.

The good news here is that the post-processing by ANSI X9.17 should kill the Dual EC backdoor, since the attack relies on the attacker seeing raw output from Dual EC. The ANSI generator appears to completely obfuscate this output, thus rendering Dual EC “safe”. This is indeed the argument Juniper made in 2013 when it decided to leave the Dual EC code in ScreenOS.

The problem with this argument is that it assumes that no other code could ever “accidentally” exfiltrate a few bytes bit of raw Dual EC output. Yet this is exactly the kind of threat you’d worry about in a deliberately backdoored system — the threat that, just maybe, the developers are not your friend. Thus Dual EC is safe only if you assume no tiny bug in the code could accidentally leak out 30 bytes or so of raw Dual EC output. If it did, this would make all subsequent seeding calls predictable, and thus render all numbers generated by the system predictable. In general, this would spell doom for the confidentiality of VPN connections.

And unbelievably, amazingly, who coulda thunk it, it appears that such a bug does exist in many versions of ScreenOS, dating to both before and after the “unauthorized code” noted by Juniper. This issue was discovered by Willem Pinckaers and can be illustrated by the following code snippet, which Steve Checkoway decompiled (see full context here):

void prng_generate()
{
  int index; // eax@4
  unsigned int bytes_generated; // ebx@4
  int v2; // eax@9
  int v3; // eax@12
  char v4; // ST04_1@12
  int time[2]; // [sp+10h] [bp-10h]@1

  time[0] = 0;
  time[1] = get_cycles();
  prng_output_index = 0; // this is a global
  ++blocks_generated_since_reseed;
  if ( !do_not_need_to_reseed() )
    // the routine below fills a buffer with raw Dual EC output
    prng_reseed(); // internally sets prng_output_index to 32
  for ( ; (unsigned int)prng_output_index <= 0x1F; prng_output_index += 8 )
  {
    // this loop is supposed to process the same buffer
    // through the ANSI (3DES) generator. However, since the
    // value of prng_output_index was set to 32 above, it never executes
    memcpy(prev_prng_seed, prng_seed, 8);
    memcpy(prev_prng_block, prng_block, 8);
    ANSI_X9_31_generate_block(time, prng_seed, prng_key, prng_block);

Thus what comes out from this function is 32 bytes of raw Dual EC output, which is all you need to recover the internal Dual EC generator state and predict all future outputs.

So if this was the authorized code, what the hell was the unauthorized code?

The creepiest thing about CVE-2015-7756 is that there doesn’t seem to be any unauthorized code. Indeed, what’s changed in the modified versions is simply the value of the Q point. According to Ralf this point changed in 2012, presumably to a value that the hacker(s) generated themselves. This would likely have allowed these individuals to passively decrypt ScreenOS VPN sessions.

In the more recent Juniper patch to fix the vulnerability, is simply set back to the the original Juniper/NetScreen value.

The attacker also replaced some test vectors. But that appears to be it.

To sum up, some hacker or group of hackers noticed an existing backdoor in the Juniper software, which may have been intentional or unintentional — you be the judge! They then piggybacked on top of it to build a backdoor of their own, something they were able to do because all of the hard work had already been done for them. The end result was a period in which someone — maybe a foreign government — was able to decrypt Juniper traffic in the U.S. and around the world.

And all because Juniper had already paved the road.

So why does this matter?

For the past several months I’ve been running around with various groups of technologists, doing everything I can to convince important people that the sky is falling. Or rather, that the sky will fall if they act on some of the very bad, terrible ideas that are currently bouncing around Washington — namely, that our encryption systems should come equipped with “backdoors” intended to allow law enforcement and national security agencies to access our communications.

One of the most serious concerns we raise during these meetings is the possibility that encryption backdoors could be subverted. Specifically, that a backdoor intended for law enforcement could somehow become a backdoor for people who we don’t trust to read our messages. Normally when we talk about this, we’re concerned about failures in storage of things like escrow keys. What this Juniper vulnerability illustrates is that the danger is much broader and more serious than that.

The problem with cryptographic backdoors isn’t that they’re the only way that an attacker can break into our cryptographic systems. It’s merely that they’re one of the best. They take care of the hard work, the laying of plumbing and electrical wiring, so attackers can simply walk in and change the drapes.

This post made possible by Ralf Philipp Weinmann, H. D. Moore, Steve Checkoway, Willem Pinckaers, Nadia Heninger, Shaanan Cohney and the letter Q.

A history of backdoors

 

Credit
The past several months have seen an almost eerie re-awakening of the ‘exceptional access’ debate — also known as ‘Crypto Wars’. For those just joining the debate, theTL;DR is that law enforcement wants software manufacturers to build wiretapping mechanisms into modern encrypted messaging systems. Software manufacturers, including Google and Apple, aren’t very thrilled with that.
The funny thing about this debate is that we’ve had it before. It happened during the 1990s with the discussion around Clipper chip, and the outcome was not spectacular for the pro-‘access’ side. But not everyone agrees.

Take, for example, former NSA general counsel Stewart Baker, who has his own reading of history:

A good example is the media’s distorted history of NSA’s 1994 Clipper chip. That chip embodied the Clinton administration’s proposal for strong encryption that “escrowed” the encryption keys to allow government access with a warrant. … The Clipper chip and its key escrow mechanism were heavily scrutinized by hostile technologists, and one, Matthew Blaze, discovered that it was possible with considerable effort to use the encryption offered by the chip while bypassing the mechanism that escrowed the key and thus guaranteed government access. … In any event, nothing about Matt Blaze’s paper questioned the security being offered by the chip, as his paper candidly admitted.

The press has largely ignored Blaze’s caveat.  It doesn’t fit the anti-FBI narrative, which is that government access always creates new security holes. I don’t think it’s an accident that no one talks these days about what Matt Blaze actually found except to say that he discovered “security flaws” in Clipper.  This formulation allows the reader to (falsely) assume that Blaze’s research shows that government access always undermines security. 

It’s not clear why Mr. Baker is focusing on Clipper, rather than the much more recent train wreck of NSA’s ‘export-grade crypto’ access proposals. It’s possible that Baker just isn’t that familiar with the issue. Indeed, it’s the almost proud absence of technological expertise on the pro-‘government access’ side that has made this debate so worrying.

But before we get to the more recent history, we should clarify a few things. Yes: the fact that Clipper — a multi-million dollar, NSA designed technology — emerged with fundamental flaws in its design is a big deal. It matters regardless of whether the exploit led to plaintext recovery or merely allowed criminals to misuse the technology in ways they weren’t supposed to.

But Clipper is hardly the end of the story. In fact, Clipper is only one of several examples of ‘government access’ mechanisms that failed and blew back on us catastrophically. More recent examples have occurred as recently as this year with the FREAK and LogJam attacks on TLS, resulting in vulnerabilities that affected nearly 1/3 of secure websites — including (embarrassingly) the FBI and NSA themselves. And these did undermine security.

With Mr. Baker’s post as inspiration, I’m going to spend the rest of this post talking about how real-world government access proposals have fared in practice — and how the actual record is worse than any technologist could have imagined at the time.

The Clipper chip

 image: Travis Goodspeed
(CC BY 2.0 via Wikimedia)
Clipper is the most famous of government access proposals. The chip was promoted as a ubiquitous hardware solution for voice encryption in the early 1990s — coincidentally, right on the eve of a massive revolution in software-based encryption and network voice communications. In simple terms, this meant that technologically Clipper was already a bit of a dinosaur by the time it was proposed.

Clipper was designed by the NSA, with key pieces of its design kept secret and hidden within tamper-resistant hardware. One major secret was the design of the Skipjack block cipher it used for encryption. All of this secrecy made it hard to evaluate the design, but the secrecy wasn’t simply the result of paranoia. Its purpose was to inhibit the development of unsanctioned Clipper-compatible devices that bypass Clipper’s primary selling point — an overt law enforcement backdoor.

The backdoor worked as follows. Each Clipper chip shipped with a unique identifier and unit key that was programmed by blowing fuses during manufacture. Upon negotiating a session key with another Clipper, the chip would transmit a 128-bit Law Enforcement Access Field (LEAF) that contained an encrypted version of the ID and session key, wrapped using the device’s unit key. The government maintained a copy of each device’s access key, split and stored at two different sites.

To protect the government’s enormous investment in hardware and secret algorithms, the Clipper designers also incorporated an authentication mechanism consisting of a further 16-bit checksum on the two components of the LEAF key, further encrypted using a family key shared between all devices. This prevented a user from tampering with or destroying the LEAF checksum as it transited the wire — any other compatible Clipper could decrypt and verify the checksum, then refuse the connection if it was invalid.

A simple way to visualize the Clipper design is to present it as three legs of a tripod, (badly) illustrated as follows:

The standout feature of Clipper’s design is its essential fragility. If one leg of the tripod fails, the entire construction tumbles down around it. For example: if the algorithms and family keys became public, then any bad actor can build a software emulator that produced apparently valid but useless LEAFs. If tamper resistance failed, the family key and algorithm designs would leak out. And most critically: if the LEAF checksum failed to protect against on-the-wire modification, then all the rest of would be a waste of money and time. Criminals could hack legitimate Clippers to interoperate without fear of interception.

In other words, everything had to work, or nothing made any sense at all. Moreover, since most of the design was secret, users were forced to trust in its security. One high-profile engineering failure would tend to undermine that confidence.

Which brings us to Matt Blaze’s results. In a famous 1994 paper, Blaze looked specifically at the LEAF authentication mechanism, and outlined several techniques for bypassing it on real Clipper prototypes. These ranged from the ‘collaborative’ — the sender omits the LEAF from its transmission, and the receiver reflects its own LEAF back into its device — to the ‘unidirectional’ where a sender simply generates random garbage LEAFs and until it finds one with a valid checksum. With only a 16-bit checksum, the latter techniques requires on average 65,536 attempts, and the sender’s own device can be used as an oracle to check the consistency of each candidate. Blaze was able to implement a system that did this in minutes — and potentially in seconds, with parallelization.

That was essentially the ballgame for Clipper.

And now we can meditate on both the accuracy and utter irrelevance of Mr. Baker’s point. It’s true that Blaze’s findings didn’t break the confidentiality of Clipper conversations, nor were the techniques themselves terribly practical. But none of that mattered. 

What did matter were the implications for the Clipper system as a whole. The flaws in authentication illustrated that the designers and implementers of Clipper had made elementary mistakes that fundamentally undermined the purpose of all those other, expensive design componentsWithout the confidence of users or law enforcement, there was no reason for Clipper to exist. 

SSL/TLS Export ciphersuites: FREAK and LogJam

This would be the end of story if Clipper was the only ‘government access’ proposal to run off the road due to bad design and unintended consequences. Mr. Baker and Matt Blaze could call it a draw and go their separate ways. But of course, the story doesn’t end with Clipper.

Mr. Baker doesn’t mention this in his article, but we’re still living with a much more pertinent example of a ‘government access’ system that failed catastrophically. Unlike Clipper, this failure really did have a devastating impact on the security of real encrypted connections. Indeed, it renders web browsing sessions completely transparent to a moderately clever attacker. Even worse, it affected hundreds of thousands of websites as recently as 2015.

The flaws I’m referring to stem from the U.S. government’s pre-2000 promotion of ‘export’-grade cryptography in the SSL and TLS protocols, which are used to secure web traffic and email all over the world. In order to export cryptography outside of the United States, the U.S. government required that web browsers and servers incorporate deliberately weakened ciphers that were (presumably) within the NSA’s ability to access.

Unsurprisingly, while the export regulations were largely abandoned as a bad job in the late 1990s, the ciphersuites themselves live on in modern TLS implementations because that’s what happens when you inter a broken thing into a widely-used standard. 

For the most part these weakened ciphers lay abandoned and ignored (but still active on many web servers) until this year, when researchers showed that it was possible to downgrade normal TLS connections to use export-grade ciphers. Ciphers that are, at this point, so weak that they can be broken in seconds on single personal computer.

Logjam is still unpatched in Chrome/MacOS as of the date of this post.

At the high watermark in March of this year, more than one out of three websites were vulnerable to either FREAK or LogJam downgrade attacks. This included banks, e-commerce sites, and yes — the NSA website and FBI tip reporting line. Hope you didn’t care much about that last one.

Now you could argue that the export requirements weren’t designed to facilitate law enforcement access. But that’s just shifting the blame from one government agency to another. Worse, it invites us to consider the notion that the FBI is going to get cryptography right when the NSA didn’t. This is not a conceptual framework you want to hang your policies on.

Conclusion

This may sound disingenuous, but the truth is that I sympathize with Mr. Baker. It’s frustrating that we’re so bad at building security systems in this day and age. It’s maddening that we can’t engineer crypto reliably even when we’re trying our very best.

But that’s the world we live in. It’s a world where we know our code is broken, and a world where a single stupid Heartbleed or Shellshock can burn off millions of dollars in a few hours. These bugs exist, and not just the ones I listed. They exist right now as new flaws that we haven’t discovered yet. Sooner or later maybe I’ll get to write about them.

The idea of deliberately engineering weakened crypto is, quite frankly, terrifying to experts. It gives us the willies. We’re not just afraid to try it. We have seen it tried — in the examples I list above, and in still others — and it’s just failed terribly.

How do we build encryption backdoors?

(photo source/cc)

They say that history repeats itself, first as tragedy, then as farce. Never has this principle been more apparent than in this new piece by Washington Post reporters Ellen Nakashima and Barton Gellman: ‘As encryption spreads, U.S. grapples with clash between privacy, security‘.

The subject of the piece is a renewed effort by U.S. intelligence and law enforcement agencies to mandate ‘backdoors’ in modern encryption systems. This is ostensibly a reaction to the mass adoption of strong encryption in smartphones, and a general fear that police are about to lose wiretapping capability they’ve come to depend on.

This is not the first time we’ve been here. Back in the 1990s the Federal government went as far as to propose a national standard for ‘escrowed’ telephone encryption called the ‘Clipper’ chip. That effort failed in large part because the technology was terrible, but also because — at least at the time — the idea of ordinary citizens adopting end-to-end encryption was basically science fiction.

Thanks to the advent of smartphones and ‘on-by-default’ encryption in popular systems like Apple’s iMessage, and WhatsApp, Americans are finally using end-to-end encryption at large scale and seem to like it. This is scaring the bejesus out of the powers that be.

Hence crypto backdoors.

As you might guess, I have serious philosophical objections to the idea of adding backdoors to any encryption system — for excellent reasons I could spend thousands of words on. But I’m not going to do that. What I’d like to do in this post is put aside my own value judgements and try to take these government proposals at face value.

Thus the question I’m going to consider in this post:

Let’s pretend that encryption backdoors are a great idea. From a purely technical point of view, what do we need to do to implement them, and how achievable is it?

First some background.

End-to-end encryption 101

Modern encryption schemes break down into several categories. For the purposes of this discussion we’ll consider two: those systems for which the provider holds the key, and the set of systems where the provider doesn’t.

We’re not terribly interested in the first type of encryption, which includes protocols like SSL/TLS and Google Hangouts, since those only protect data at the the link layer, i.e., until it reaches your provider’s servers. I think it’s fairly well established that if Facebook, Apple, Google or Yahoo can access your data, then the government can access it as well — simply by subpoenaing or compelling those companies. We’ve even seen how this can work.

The encryption systems we’re interested all belong to the second class — protocols where even the provider can’t decrypt your information. This includes:

This seems like a relatively short list, but in practice w’re talking about an awful lot of data. The iMessage and WhatsApp systems alone process billions of instant messages every day, and Apple’s device encryption is on by default for everyone with a recent(ly updated) iPhone.

How to defeat end-to-end encryption

If you’ve decided to go after end-to-end encryption through legal means, there are a relatively small number of ways to proceed.

By far the simplest is to simply ban end-to-end crypto altogether, or to mandate weak encryption. There’s some precedent for this: throughout the 1990s, the NSA forced U.S. companies to ship ‘export‘ grade encryption that was billed as being good enough for commercial use, but weak enough for governments to attack. The problem with this strategy is that attacks only get better — but legacy crypto never dies.

Fortunately for this discussion, we have some parameters to work with. One of these is that Washington seems to genuinely want to avoid dictating technological designs to Silicon Valley. More importantly, President Obama himself has stated that “there’s no scenario in which we don’t want really strong encryption“. Taking these statements at face value should mean that we can exclude outright crypto bans, mandated designs, and any modification has the effect of fundamentally weakening encryption against outside attackers.

If we mix this all together, we’re left with only two real options:

  1. Attacks on key distribution. In systems that depend on centralized, provider-operated key servers, such as WhatsApp, Facetime, Signal and iMessage,** governments can force providers to distribute illegitimate public keys, or register shadow devices to a user’s account. This is essentially a man-in-the-middle attack on encrypted communication systems.
  2. Key escrow. Just about any encryption scheme can be modified to encrypt a copy of a decryption (or session) key such that a ‘master keyholder’ (e.g., Apple, or the U.S. government) can still decrypt. A major advantage is that this works even for device encryption systems, which have no key servers to suborn.

Each approach requires some modifications to clients, servers or other components of the system.

Attacking key distribution

Key lookup request for Apple iMessage. The phone
number is shown at top right, and the response at bottom left.

Many end-to-end encrypted messaging systems, including WhatsApp and iMessage, generate a long-term public and secret keypair for every device you own. The public portion of this keypair is distributed to anyone who might want to send you messages. The secret key never leaves the device.

Before you can initiate a connection with your intended recipient, you first have to obtain a copy of the recipient’s public key. This is commonly handled using a key server that’s operated by the provider. The key server may hand back one, or multiple public keys (depending on how many devices you’ve registered). As long as those keys all legitimately belong to your intended recipient, everything works fine.

Intercepting messages is possible, however, if the provider is willing to substitute its own public keys — keys for which it (or the government) actually knows the secret half. In theory this is relatively simple — in practice it can be something of a bear, due to the high complexity of protocols such as iMessage.

Key fingerprints.

The main problem with key distribution attacks is — unlike a traditional wiretap — substitute keys are at least in theory detectable by the target. Some communication systems, like Signal, allow users to compare key fingerprints in order to verify that each received the right public key. Others, like iMessage and WhatsApp, don’t offer this technology — but could easily be modified to do so (even using third party clients). Systems like CONIKS may even automate this process in the future — allowing applications to monitor changes to their own keys in real time as they’re distributed by a server.

A final, and salient feature on the key distribution approach is that it allows only prospective eavesdropping — that is, law enforcement must first target a particular user, and only then can they eavesdrop on her connections. There’s no way to look backwards in time. I see this is a generally good thing. Others may disagree.

Key Escrow 


Structure of the Clipper ‘LEAF’.

The techniques above don’t help much for systems without public key servers, Moreover, they do nothing for systems that don’t use public keys at all, the prime example being device encryptionIn this case, the only real alternative is to mandate some sort of key escrow.

Abstractly, the purpose of an escrow system is to place decryption keys on file (‘escrow’ them) with some trusted authority, who can break them out when the need arises. In practice it’s usually a bit more complex.

The first wrinkle is that modern encryption systems often feature many decryption keys, some of which can be derived on-the-fly while the system operates. (Systems such as TextSecure/WhatsApp actually derive new encryption keys for virtually every message you send.) Users with encrypted devices may change their password from time to time.

To deal with this issue, a preferred approach is to wrap these session keys up (encrypt them) under some master public key generated by the escrow authority — and to store/send the resulting ciphertexts along with the rest of the encrypted data. In the 1990s Clipper specification these ciphertexts were referred to as Law Enforcement Access Fields, or LEAFs.***

With added LEAFs in your protocol, wiretapping becomes relatively straightforward. Law enforcement simply intercepts the encrypted data — or obtains it from your confiscated device — extract the LEAFs, and request that the escrow authority decrypt them. You can find variants of this design dating back to the PGP era. In fact, the whole concept is deceptively simple — provided you don’t go farther than the whiteboard. 

Conceptual view of some encrypted data (left) and a LEAF (right).

It’s only when you get into the details of actually implementing key escrow that things get hairy. These schemes require you to alter every protocol in your encryption system, at a pretty fundamental level — in the process creating the mother of all security vulnerabilities — but, more significantly, they force you to think very seriously about who you trust to hold those escrow keys.

Who does hold the keys?

This is the million dollar question for any escrow platform. The Post story devotes much energy to exploring various proposals for doing this.

Escrow key management is make-or-break, since the key server represents a universal vulnerability in any escrowed communication system. In the present debate there appear to be two solutions on the table. The first is to simply dump the problem onto individual providers, who will be responsible for managing their escrow keys — using whatever technological means they deem appropriate. A few companies may get this right. Unfortunately, most companies suck at cryptography, so it seems reasonable to believe that the resulting systems will be quite fragile.

The second approach is for the government to hold the keys themselves. Since the escrow key is too valuable to entrust to one organization, one or more trustworthy U.S. departments would hold ‘shares‘ of the master key, and would cooperate to provide decryption on a case-by-case basis. This was, in fact, the approach proposed for the Clipper chip.

The main problem with this proposal is that it’s non-trivial to implement. If you’re going to split keys across multiple agencies, you have to consider how you’re going to store those keys, and how you’re going to recover them when you need to access someone’s data. The obvious approach — bring the key shares back together at some centralized location — seems quite risky, since the combined master key would be vulnerable in that moment.

A second approach is to use a threshold cryptosystem. Threshold crypto refers to a set of techniques for storing secret keys across multiple locations so that decryption can be done in place without recombining the key shares. This seems like an ideal solution, with only one problem: nobody has deployed threshold cryptosystems at this kind of scale before. In fact, many of the protocols we know of in this area have never even been implemented outside of the research literature. Moreover, it will require governments to precisely specify a set of protocols for tech companies to implement — this seems incompatible with the original goal of letting technologists design their own systems.

Software implementations

A final issue to keep in mind is the complexity of the software we’ll need to make all of this happen. Our encryption software is already so complex that it’s literally at the breaking point. (If you don’t believe me, take a look at OpenSSL’s security advisories for the last year) While adding escrow mechanisms seems relatively straightforward, it will actually require quite a bit of careful coding, something we’re just not good at.

Even if we do go forward with this plan, there are many unanswered questions. How widely can these software implementations be deployed? Will every application maker be forced to use escrow? Will we be required to offer a new set of system APIs in iOS, Windows and Android that we can use to get this right? Answering each of these questions will result in dramatic changes throughout the OS software stack. I don’t envy the poor developers who will have to answer them.

How do we force people to use key escrow?

Leaving aside the technical questions, the real question is: how do you force anyone to do this stuff? Escrow requires breaking changes to most encryption protocols; it’s costly as hell; and it introduces many new security concerns. Moreover, laws outlawing end-to-end encryption software seem destined to run afoul of the First Amendment.

I’m not a lawyer, so don’t take my speculation too seriously — but it seems intuitive to me that any potential legislation will be targeted at service providers, not software vendors or OSS developers. Thus the real leverage for mandating key escrow will apply to the Facebooks and Apples of the world. Your third-party PGP and OTR clients would be left alone, for the tiny percentage of the population who uses these tools.

Unfortunately, even small app developers are increasingly running their own back-end servers these days (e.g., Whisper Systems and Silent Circle) so this is less reassuring than it sounds. Probably the big takeaway for encryption app developers is that it might be good to think about how you’ll function in a world where it’s no longer possible to run your own back-end data transport service — and where other commercial services may not be too friendly to moving your data for you.

In conclusion

If this post has been more questions than answers, that’s because there really are no answers right now. A serious debate is happening in an environment that’s almost devoid of technical input, at least from technical people who aren’t part of the intelligence establishment.

And maybe that by itself is reason enough to be skeptical.

Notes:

* Not an endorsement. I have many thoughts on Telegram’s encryption protocols, but they’re beyond the scope of this post.

** Telegram is missing from this list because their protocol doesn’t handle long term keys at all. Every single connection must be validated in person using a graphical key fingerprint, which is, quite frankly, terrible.

*** The Clipper chip used a symmetric encryption algorithm to encrypt the LEAF, which meant that the LEAF decryption key had to be present inside of every consumer device. This was completely nuts, and definitely a bullet dodged. It also meant that every single Clipper had to be implemented in hardware using tamper resistant chip manufacturing technology. It was a truly awful design.

How to paint yourself into a corner (Lenovo edition)

The information security news today is all about Lenovo’s default installation of a piece of adware called “Superfish” on a number of laptops shipped before February 2015. The Superfish system is essentially a tiny TLS/SSL “man in the middle” proxy that attacks secure connections by making them insecure — so that the proxy can insert ads in order to, oh, I don’t know, let’s just let Lenovo tell it:

“To be clear, Superfish comes with Lenovo consumer products only and is a technology that helps users find and discover products visually,” the representative continued. “The technology instantly analyses images on the web and presents identical and similar product offers that may have lower prices, helping users search for images without knowing exactly what an item is called or how to describe it in a typical text-based search engine.”

Whatever.

The problem here is not just that this is a lousy idea. It’s that Lenovo used the same certificate on every single Laptop it shipped with Superfish. And since the proxy software also requires the corresponding private key to decrypt and modify your web sessions, that private key was also shipped on every laptop. It took all of a day for a number of researchers to find that key and turn themselves into Lenovo-eating interception proxies. This sucks for Lenovo users.

If you’re a Lenovo owner in the affected time period, go to this site to find out if you’re vulnerable and (hopefully) what to do about it. But this isn’t what I want to talk about in this post.

Instead, what I’d like to discuss is some of the options for large-scale automated fixes to this kind of vulnerability. It’s quite possible that Lenovo will do this by themselves — pushing an automated patch to all of their customers to remove the product — but I’m not holding my breath. If Lenovo does not do this, there are roughly three options:

  1. Lenovo users live with this and/or manually patch. If the patch requires manual effort, I’d estimate it’ll be applied to about 30% of Lenovo laptops. Beware: the current uninstall package does not remove the certificate from the root store!
  2. Microsoft drops the bomb. Microsoft has a nuclear option themselves in terms of cleaning up nasty software — they can use the Windows Update mechanism or (less universally) the Windows Defender tool to remove spyware/adware. Unfortunately not everyone uses Defender, and Microsoft is probably loath to push out updates like this without massive testing and a lot of advice from the lawyers.
  3. Google and Mozilla fix internally. This seems like a more promising option. Google Chrome in particular is well known for quickly pushing out security updates that revoke keys, add public key pins, and generally make your browsing experience more secure.

It seems unlikely that #1 and #2 will happen anytime soon, so the final option looks initially like the most promising. Unfortunately it’s not that easy. To understand why, I’m going to sum up some reasoning given to me (on Twitter) by a couple of members of the Chrome security team.

The obvious solution to fixing things at the Browser level is to have Chrome and/or Mozilla push out an update to their browsers that simply revokes the Superfish certificate. There’s plenty of precedent for that, and since the private key is now out in the world, anyone can use it to build their own interception proxy. Sadly, this won’t work! If Google does this, they’ll instantly break every Lenovo laptop with Superfish still installed and running. That’s not nice, or smart business for Google.

A more promising option is to have Chrome at least throw up a warning whenever a vulnerable Lenovo user visits a page that’s obviously been compromised by a Superfish certificate. This would include most (secure) sites any Superfish-enabled Lenovo user visits — which would be annoying — and just a few pages for those users who have uninstalled Superfish but still have the certificate in their list of trusted roots.

This seems much nicer, but runs into two problems. First, someone has to write this code — and in a hurry, because attacks may begin happening immediately. Second, what action item are these warnings going to give people? Manually uninstalling certificates is hard, and until a very nice tool becomes available a warning will just be an irritation for most users.

One option for Google is to find a way to deal with these issues systemically — that is, provide an option for their browser to tunnel traffic through some alternative (secure) protocol to a proxy, where it can then go securely to its location without being molested by Superfish attackers of any flavor. This would obviously require consent by the user — nobody wants their traffic being routed through Google otherwise. But it’s at least technically feasible.

Google even has an extension for Android/iOS that works something like this: it’s a compressing proxy extension that you can install in Chrome. It will shrink your traffic down and send it to a proxy (presumably at Google). Unfortunately this proxy won’t work even if it was available for Windows machines — because Superfish will likely just intercept its connections too 😦

So that’s out too, and with it the last obvious idea I have for dealing with this in a clean, automated way. Hopefully the Google team will keep going until they find a better solution.

The moral of this story, if you choose to take one, is that you should never compromise security for the sake of a few bucks — because security is so terribly, awfully difficult to get back.

Hopefully the last post I’ll ever write on Dual EC DRBG

I’ve been working on some other blog posts, including a conclusion of (or at least an installment in) this exciting series on zero knowledge proofs. That’s coming soon, but first I wanted to take a minute to, well, rant.

The subject of my rant is this fascinating letter authored by NSA cryptologist Michael Wertheimer in February’s Notices of the American Mathematical Society. Dr. Wertheimer is currently the Director of Research at NSA, and formerly held the position of Assistant Deputy Director and CTO of the Office of the Director of National Intelligence for Analysis.

In other words, this is a guy who should know what he’s talking about.

The subject of Dr. Wertheimer’s letter is near and dear to my heart: the alleged subversion of NIST’s standards for random number generation — a subversion that was long suspected and apparently confirmed by classified documents leaked by Edward Snowden. The specific algorithm in question is called Dual EC DRBG, and it very likely contains an NSA backdoor. Those who’ve read this blog should know that I think it’s as suspicious as a three dollar bill.

Reading Dr. Wertheimer’s letter, you might wonder what I’m so upset about. On the face of it, the letter appears to express regret. To quote (with my emphasis):

With hindsight, NSA should have ceased supporting the Dual_EC_DRBG algorithm immediately after security researchers discovered the potential for a trapdoor. In truth, I can think of no better way to describe our failure to drop support for the Dual_EC_DRBG algorithm as anything other than regrettable. The costs to the Defense Department to deploy a new algorithm were not an adequate reason to sustain our support for a questionable algorithm. Indeed, we support NIST’s April 2014 decision to remove the algorithm. Furthermore, we realize that our advocacy for the Dual_EC_DRBG casts suspicion on the broader body of work NSA has done to promote secure standards. 

I agree with all that. The trouble is that on closer examination, the letter doesn’t express regret for the inclusion of Dual EC DRBG in national standards. The transgression Dr. Wertheimer identifies is merely that NSA continued to support the algorithm after major questions were raised. That’s bizarre.

Even worse, Dr. Wertheimer reserves a substantial section of his letter for a defense of the decision to deploy Dual EC. It’s those points that I’d like to address in this post.

Let’s take them one at a time.

1: The Dual_EC_DRBG was one of four random number generators in the NIST standard; it is neither required nor the default.

It’s absolutely true that Dual EC was only one of four generators in the NIST standard. It was not required for implementers to use it, and in fact they’d be nuts to use it — given that overall it’s at least two orders of magnitude slower than the other proposed generators.

The bizarre thing is that people did indeed adopt Dual EC in major commercial software packages. Specifically, RSA Security included it as the default generator in their popular BSAFE software library. Much worse, there’s evidence that RSA was asked to do this by NSA, and were compensated for their compliance.

This is the danger with standards. Once NIST puts its seal on an algorithm, it’s considered “safe”. If the NSA came to a company and asked it to use some strange, non-standard algorithm, the request would be considered deeply suspicious by company and customers alike. But how can you refuse to use a standard if your biggest client asks you to? Apparently RSA couldn’t.

2: The NSA-generated elliptic curve points were necessary for accreditation of the Dual_EC_DRBG but only had to be implemented for actual use in certain DoD applications.

This is a somewhat misleading statement, one that really needs to be unpacked.

First, the original NSA proposal of Dual EC DRBG contained no option for alternate curve points. This is an important point, since its the selection of curve points that give Dual EC its potential for a “back door”. By generating two default points (P, Q) in a specific way, the NSA may have been able to create a master key that would allow them to very efficiently decrypt SSL/TLS connections.

If you like conspiracy theories, here’s what NIST’s John Kelsey was told when he asked how the NSA’s points were generated:

In 2004-2005, several participants on the ANSI X9 tools committee pointed out the potential danger of this backdoor. One of them even went so far as to file a patent on using the idea to implement key escrow for SSL/TLS connections. (It doesn’t get more passive aggressive than that.)

In response to the discovery of such an obvious flaw, the ANSI X9 committee immediately stopped recommending the NSA’s points — and relegated them to be simply an option, one to be used by the niche set of government users who required them.

I’m only kidding! Actually the committee did no such thing.

Instead, at the NSA’s urging, the ANSI committee retained the original NSA points as the recommended parameters for the standard. It then added an optional procedure for generating alternative points. When NIST later adopted the generator in its SP800-90A standard, it mirrored the ANSI decision. But even worse, NIST didn’t even bother to publish the alternative point generation algorithm. To actually implement it, you’d need to go buy the (expensive) non-public-domain ANSI standard and figure it out to implement it yourself:

This is, to paraphrase Douglas Adams, the standards committee equivalent of putting the details in the bottom of a locked filing cabinet stuck in a disused lavatory with a sign on the door saying ‘Beware of the Leopard’.

To the best of our knowledge, nobody has ever used ANSI’s alternative generation procedure in a single one of the many implementations of Dual EC DRBG in commercial software.  It’s not even clear how you could have used that procedure in a FIPS-certified product, since the FIPS evaluation process (conducted by CMVP) still requires you to test against the NSA-generated points.

3. The trapdoor concerns were openly studied by ANSI X9F1, NIST, and by the public in 2007. 

This statement has the benefit of being literally true, while also being pretty damned misleading.

It is true that in 2007 — after Dual EC had been standardized — two Microsoft researchers, Dan Shumow and Neils Ferguson openly raised the alarm about Dual EC. The problem here is that the flaws in Dual EC were not first discovered in 2007. They were discovered much earlier in the standardization process and nobody ever heard about them.

As I noted above, the ANSI X9 committee detected the flaws in Dual EC as early as 2004, and in close consultation with NSA agreed to address them — in a manner that was highly beneficial to the NSA. But perhaps that’s understandable, given that the committee was anything but ‘open’.

In fact, this is an important aspect of the controversy that even NIST has criticized. The standardization of these algorithms was conducted through ANSI. And the closed ANSI committee consisted of representatives from a few select companies, NIST and the NSA. No public notice was given of the potential vulnerabilities discovered in the RNG. Moreover, a patent application that might have shone light on the backdoor was mired in NSA pre-publication review for over two years.

This timeline issue might seem academic, but bear this in mind: we now know that RSA Security began using the Dual EC DRBG random number generator in BSAFE — as the default, I remind you — way back in 2004. That means for three years this generator was widely deployed, yet serious concerns were not communicated to the public.

To state that the trapdoor concerns were ‘openly’ studied in 2007 is absolutely true. It’s just completely irrelevant.

In conclusion

I’m not a mathematician, but like anyone who works in a mathematical area, I find there are aspects of the discipline that I love. For me it’s the precision of mathematical statements, and the fact that the truth or falsity of a statement can — ideally — be evaluated from the statement itself, without resorting to differing opinions or understandings of the context.

While Dr. Wertheimer’s letter is hardly a mathematical work, it troubles me to see such confusing statements in a publication of the AMS. As a record of history, Dr. Wertheimer’s letter leaves much to be desired, and could easily lead people to the wrong understanding.

Given the stakes, we deserve a more exact accounting of what happened with Dual EC DRBG. I hope someday we’ll see that.

On the new Snowden documents

If you don’t follow NSA news obsessively, you might have missed yesterday’s massive Snowden document dump from Der Spiegel. The documents provide a great deal of insight into how the NSA breaks our cryptographic systems. I was very lightly involved in looking at some of this material, so I’m glad to see that it’s been published.

Unfortunately with so much material, it can be a bit hard to separate the signal from the noise. In this post I’m going to try to do that a little bit — point out the bits that I think are interesting, the parts that are old news, and the things we should keep an eye on.

Background

Those who read this blog will know that I’ve been wondering for a long time how NSA works its way around our encryption. This isn’t an academic matter, since it affects just about everyone who uses technology today.

What we’ve learned since 2013 is that NSA and its partners hoover up vast amounts of Internet traffic from fiber links around the world. Most of this data is plaintext and therefore easy to intercept. But at least some of it is encrypted — typically protected by protocols such as SSL/TLS or IPsec.

Conventional wisdom pre-Snowden told us that the increasing use of encryption ought to have shut the agencies out of this data trove. Yet the documents we’ve seen so far indicate just the opposite. Instead, the NSA and GCHQ have somehow been harvesting massive amounts of SSL/TLS and IPSEC traffic, and appear to be making inroads into other technologies such as Tor as well.

How are they doing this? To repeat an old observation, there are basically three ways to crack an encrypted connection:

  1. Go after the mathematics. This is expensive and unlikely to work well against modern encryption algorithms (with a few exceptions). The leaked documents give very little evidence of such mathematical breaks — though a bit more on this below.
  2. Go after the implementation. The new documents confirm a previously-reported and aggressive effort to undermine commercial cryptographic implementations. They also provide context for how important this type of sabotage is to the NSA.
  3. Steal the keys. Of course, the easiest way to attack any cryptosystem is simply to steal the keys. Yesterday we received a bit more evidence that this is happening.
I can’t possibly spend time on everything that’s covered by these documents — you should go read them yourself — so below I’m just going to focus on the highlights.

Not so Good Will Hunting

First, the disappointing part. The NSA may be the largest employer of cryptologic mathematicians in the United States, but — if the new story is any indication — those guys really aren’t pulling their weight.

In fact, the only significant piece of cryptanalytic news in the entire stack comes is a 2008 undergraduate research project looking at AES. Sadly, this is about as unexciting as it sounds — in fact it appears to be nothing more than a summer project by a visiting student. More interesting is the context it gives around the NSA’s efforts to break block ciphers such as AES, including the NSA’s view of the difficulty of such cryptanalysis, and confirmation that NSA has some ‘in-house techniques’.

Additionally, the documents include significant evidence that NSA has difficulty decrypting certain types of traffic, including Truecrypt, PGP/GPG, Tor and ZRTP from implementations such as RedPhone. Since these protocols share many of the same underlying cryptographic algorithms — RSA, Diffie-Hellman, ECDH and AES — some are presenting this as evidence that those primitives are cryptographically strong.

As with the AES note above, this ‘good news’ should also be taken with a grain of salt. With a small number of exceptions, it seems increasingly obvious that the Snowden documents are geared towards NSA’s analysts and operations staff. In fact, many of the systems actually seem aimed at protecting knowledge of NSA’s cryptanalytic capabilities from NSA’s own operational staff (and other Five Eyes partners). As an analyst, it’s quite possible you’ll never learn why a given intercept was successfully decrypted.

 To put this a bit more succinctly: the lack of cryptanalytic red meat in these documents may not truly be representative of the NSA’s capabilities. It may simply be an artifact of Edward Snowden’s clearances at the time he left the NSA.

Tor

One of the most surprising aspects of the Snowden documents — to those of us in the security research community anyway — is the NSA’s relative ineptitude when it comes to de-anonymizing users of the Tor anonymous communications network.

The reason for our surprise is twofold. First, Tor was never really designed to stand up against a global passive adversary — that is, an attacker who taps a huge number of communications links. If there’s one thing we’ve learned from the Snowden leaks, the NSA (plus GCHQ) is the very definition of the term. In theory at least, Tor should be a relatively easy target for the agency.

The real surprise, though, is that despite this huge signals intelligence advantage, the NSA has barely even tested their ability to de-anonymize users. In fact, this leak provides the first concrete evidence that NSA is experimenting with traffic confirmation attacks to find the source of Tor connections. Even more surprising, their techniques are relatively naive, even when compared to what’s going on in the ‘research’ community.

This doesn’t mean you should view Tor as secure against the NSA. It seems very obvious that the agency has identified Tor as a high-profile target, and we know they have the resources to make much more headway against the network. The real surprise is that they haven’t tried harder. Maybe they’re trying now.

SSL/TLS and IPSEC

 A few months ago I wrote a long post speculating about how the NSA breaks SSL/TLS. Because it’s increasingly clear that the NSA does break these protocols, and at relatively large scale.

The new documents don’t tell us much we didn’t already know, but they do confirm the basic outlines of the attack. The first portion requires endpoints around the world that are capable of performing the raw decryption of SSL/TLS sessions provided they know the session keys. The second is a separate infrastructure located on US soil that can recover those session keys when needed.

All of the real magic happens within the key recovery infrastructure. These documents provide the first evidence that a major attack strategy for NSA/GCHQ involves key databases containing the private keys for major sites. For the RSA key exchange ciphersuites of TLS, a single private key is sufficient to recover vast amounts of session traffic — in real time or even after the fact.

The interesting question is how the NSA gets those private keys. The easiest answer may be the least technical. A different Snowden leak shows gives some reason to believe that the NSA may have relationships with employees at specific named U.S. entities, and may even operate personnel “under cover”. This would certainly be one way to build a key database.

 

But even without the James Bond aspect of this, there’s every reason to believe that NSA has other means to exfiltrate RSA keys from operators. During the period in question, we know of at least one vulnerability (Heartbleed) that could have been used to extract private keys from software TLS implementations. There are still other, unreported vulnerabilities that could be used today.

 Pretty much everything I said about SSL/TLS also applies to VPN protocols, with the additional detail that many VPNs use broken protocols and relatively poorly-secured pre-shared secrets that can in some cases be brute-forced. The NSA seems positively gleeful about this.

Open Source packages: Redphone, Truecrypt, PGP and OTR

The documents provide at least circumstantial evidence that some open source encryption technologies may thwart NSA surveillance. These include Truecrypt, ZRTP implementations such as RedPhone, PGP implementations, and Off the Record messaging. These packages have a few commonalities:

  1. They’re all open source, and relatively well studied by researchers.
  2. They’re not used at terribly wide scale (as compared to e.g., SSL or VPNs)
  3. They all work on an end-to-end basis and don’t involve service providers, software distributers, or other infrastructure that could be corrupted or attacked.

What’s at least as interesting is which packages are not included on this list. Major corporate encryption protocols such as iMessage make no appearance in these documents, despite the fact that they ostensibly provide end-to-end encryption. This may be nothing. But given all we know about NSA’s access to providers, this is definitely worrying.

A note on the ethics of the leak

Before I finish, it’s worth addressing one major issue with this reporting: are we, as citizens, entitled to this information? Would we be safer keeping it all under wraps? And is this all ‘activist nonsense‘?

This story, more than some others, skates close to a line. I think it’s worth talking about why this information is important.

To sum up a complicated issue, we live in a world where targeted surveillance is probably necessary and inevitable. The evidence so far indicates that NSA is very good at this kind of work, despite some notable failures in actually executing on the intelligence it produces.

Unfortunately, the documents released so far also show that a great deal of NSA/GCHQ surveillance is not targeted at all. Vast amounts of data are scooped up indiscriminately, in the hope that some of it will someday prove useful. Worse, the NSA has decided that bulk surveillance justifies its efforts to undermine many of the security technologies that protect our own information systems. The President’s own hand-picked review council has strongly recommended this practice be stopped, but their advice has — to all appearances — been disregarded. These are matters that are worthy of debate, but this debate hasn’t happened.

Unfortunate if we can’t enact changes to fix these problems, technology is probably about all that’s left. Over the next few years encryption technologies are going to be widely deployed, not only by individuals but also by corporations desperately trying to reassure overseas customers who doubt the integrity of US technology.

In that world, it’s important to know what works and doesn’t work. Insofar as this story tells us that, it makes us all better off.