Sunday, August 16, 2015

The network is hostile

Yesterday the New York Times and ProPublica posted a lengthy investigation based on leaked NSA documents, outlining the extensive surveillance collaboration between AT&T and the U.S. government. This surveillance includes gems such as AT&T's assistance in tapping the main fiber connection supporting the United Nations, and that's only the start.

The usual Internet suspects are arguing about whether this is actually news. The answer is both yes and no, though I assume that the world at large will mostly shrug at this point. After all, we've learned so much about the NSA's operations at this point that we're all suffering from revelation-fatigue. It would take a lot to shock us now.

But this isn't what I want to talk about. Instead, the effect of this story was to inspire me to look back on the NSA leaks overall, to think about what they've taught us. And more importantly -- what they mean for the design of the Internet and our priorities as security engineers. That's what I'm going to ruminate about below.

The network is hostile

Anyone who has taken a network security class knows that the first rule of Internet security is that there is no Internet security. Indeed, this assumption is baked into the design of the Internet and most packet-switched networks -- systems where unknown third parties are responsible for handling and routing your data. There is no way to ensure that your packets will be routed as you want them, and there's absolutely no way to ensure that they won't be looked at.

Indeed, the implications of this were obvious as far back as ARPANET. If you connect from point A to point B, it was well known that your packets would traverse untrusted machines C, D and E in between. In the 1970s the only thing preserving the privacy of your data was a gentleman's agreement not to peek. If that wasn't good enough, the network engineers argued, you had to provide your own security between the endpoints themselves.

My take from the NSA revelations is that even though this point was 'obvious' and well-known, we've always felt it more intellectually than in our hearts. Even knowing the worst was possible, we still chose to believe that direct peering connections and leased lines from reputable providers like AT&T would make us safe. If nothing else, the NSA leaks have convincingly refuted this assumption.

We don't encrypt nearly enough

The most surprising lesson of the NSA stories is that 20 years after the development of SSL encryption, we're still sending vast amounts of valuable data in the clear.

Even as late as 2014, highly vulnerable client-to-server connections for services like Yahoo Mail were routinely transmitted in cleartext -- meaning that they weren't just vulnerable to the NSA, but also to everyone on your local wireless network. And web-based connections were the good news. Even if you carefully checked your browser connections for HTTPS usage, proprietary extensions and mobile services would happily transmit data such as your contact list in the clear. If you noticed and shut down all of these weaknesses, it still wasn't enough -- tech companies would naively transmit the same data through vulnerable, unencrypted inter-datacenter connections where the NSA could scoop them up yet again.

There is a view in our community that we're doing much better now, and to some extent we may be. But I'm less optimistic. From an attacker's point of view, the question is not how much we're encrypting, but rather, which valuable scraps we're not protecting. As long as we tolerate the existence of unencrypted protocols and services, the answer is still: way too much.

It's the metadata, stupid

Even if we, by some miracle, manage to achieve 100% encryption of communications content, we still haven't solved the whole problem. Unfortunately, today's protocols still leak a vast amount of useful information via session metadata. And we have no good strategy on the table to defend against it.

Examples of metadata leaked by today's protocols include protocol type, port number, and routing information such as source and destination addresses. It also includes traffic characteristics, session duration, and total communications bandwidth. Traffic analysis remains a particular problem: even knowing the size of the files requested by a TLS-protected browser connection can leak a vast amount of information about the user's browsing habits.

Absolutely none of this is news to security engineers. The problem is that there's so little we can do about it. Anonymity networks like Tor protect the identity of endpoints in a connection, but they do so at a huge cost in additional bandwidth and latency -- and they offer only limited protection in the face of a motivated global adversary. IPSec tunnels only kick the can to a different set of trusted components that themselves can be subverted.

'Full take' culture

Probably the most eye-opening fact of the intelligence leaks is the sheer volume of data that intelligence agencies are willing to collect. This is most famously exemplified by the U.S. bulk data collection and international call recording programs -- but for network engineers the more worrying incarnation is "full take" Internet collection devices like TEMPORA.

If we restrict our attention purely to the collection of such data -- rather than how it's accessed -- it appears that the limiting factors are almost exclusively technical in nature. In other words, the amount of data collected is simply a function of processing power, bandwidth and storage. And this is bad news for our future.

That's because while meaningful human communication bandwidth (emails, texts, Facebook posts, Snapchats) continues to increase substantially, storage and processing power increase faster. With some filtration, and no ubiquitous encryption, 'full take' is increasingly going to be the rule rather than the exception.

We've seen the future, and it's not American

Even if you're not inclined to view the NSA as an adversary -- and contrary to public perception, that view is not uniform even inside Silicon Valley -- America is hardly the only intelligence agency capable of subverting the global communications network. Nations like China are increasingly gaining market share in telecommunications equipment and services, especially in developing parts of the world such as Africa and the Middle East.

While it's cheap to hold China out as some sort of boogeyman, it's significant that someday a large portion of the world's traffic will flow through networks controlled by governments that are, at least to some extent, hostile to the core values of Western democracies.

If you believe that this is the future, then the answer certainly won't involve legislation or politics. The NSA won't protect us through cyber-retaliation or whatever plan is on the table today. If you're concerned about the future, then the answer is to finally, truly believe our propaganda about network trust. We need to learn to build systems today that can survive such an environment. Failing that, we need to adjust to a very different world.

Monday, July 20, 2015

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, the TL;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.

Friday, May 22, 2015

Attack of the week: Logjam

In case you haven't heard, there's a new SSL/TLS vulnerability making the rounds. Nicknamed Logjam, the new attack is 'special' in that it may admit complete decryption or hijacking of any TLS connection you make to an improperly configured web or mail server. Worse, there's at least circumstantial evidence that similar (and more powerful) attacks might already be in the toolkit of some state-level attackers such as the NSA.

This work is the result of an unusual collaboration between a fantastic group of co-authors spread all around the world, including institutions such as the University of Michigan, INRIA Paris-Rocquencourt, INRIA Paris-Nancy, Microsoft Research, Johns Hopkins and the University Of Pennsylvania. It's rare to see this level of collaboration between groups with so many different areas of expertise, and I hope to see a lot more like it. (Disclosure: I am one of the authors.)

The absolute best way to understand the Logjam result is to read the technical research paper. This post is mainly aimed at people who want a slightly less technical form. For those with even shorter attention spans, here's the TL;DR:
It appears that the the Diffie-Hellman protocol, as currently deployed in SSL/TLS, may be vulnerable to a serious downgrade attack that restores it to 1990s "export" levels of security, and offers a practical "break" of the TLS protocol against poorly configured servers. Even worse, extrapolation of the attack requirements -- combined with evidence from the Snowden documents -- provides some reason to speculate that a similar attack could be leveraged against protocols (including TLS, IPSec/IKE and SSH) using 768- and 1024-bit Diffie-Hellman. 
I'm going to tackle this post in the usual 'fun' question-and-answer format I save for this sort of thing.
What is Diffie-Hellman and why should I care about TLS "export" ciphersuites?
Diffie-Hellman is probably the most famous public key cryptosystem ever invented. Publicly discovered by Whit Diffie and Martin Hellman in the late 1970s (and a few years earlier, in secret, by UK GCHQ), it allows two parties to negotiate a shared encryption key over a public connection.

Diffie-Hellman is used extensively in protocols such as SSL/TLS and IPSec, which rely on it to establish the symmetric keys that are used to transport data. To do this, both parties must agree on a set of parameters to use for the key exchange. In traditional ('mod p') Diffie-Hellman, these parameters consist of a large prime number p, as well as a 'generator' g. The two parties now exchange keys as shown below:

Classical Diffie-Hellman (source).
TLS supports several variants of Diffie-Hellman. The one we're interested in for this work is the 'ephemeral' non-elliptic ("DHE") protocol variant, which works in a manner that's nearly identical to the diagram above. The server takes the role of Alice, selecting (p, g, ga mod p) and signing this tuple (and some nonces) using its long-term signing key. The client responds gb mod p and the two sides then calculate a shared secret.

Just for fun, TLS also supports an obsolete 'export' variant of Diffie-Hellman. These export ciphersuites are a relic from the 1990s when it was illegal to ship strong encryption out of the country. What you need to know about "export DHE" is simple: it works identically to standard DHE, but limits the size of p to 512 bits. Oh yes, and it's still out there today. Because the Internet.
How do you attack Diffie-Hellman?
The best known attack against a correct Diffie-Hellman implementation involves capturing the value gand solving to find the secret key a. The problem of finding this value is known as the discrete logarithm problem, and it's thought to be a mathematically intractable, at least when Diffie-Hellman is implemented in cryptographically strong groups (e.g., when p is of size 2048 bits or more).

Unfortunately, the story changes dramatically when p is relatively small -- for example, 512 bits in length. Given a value gmod p for a 512-bit p, itshould at least be possible to efficiently recover the secret a and read traffic on the connection.
Most TLS servers don't use 512-bit primes, so who cares?
The good news here is that weak Diffie-Hellman parameters are almost never used purposely on the Internet. Only a trivial fraction of the SSL/TLS servers out there today will organically negotiate 512-bit Diffie-Hellman. For the most part these are crappy embedded devices such as routers and video-conferencing gateways.

However, there is a second class of servers that are capable of supporting 512-bit Diffie-Hellman when clients request it, using a special mode called the 'export DHE' ciphersuite. Disgustingly, these servers amount to about 8% of the Alexa top million sites (and a whopping 29% of SMTP/STARTLS mail servers). Thankfully, most decent clients (AKA popular browsers) won't willingly negotiate 'export-DHE', so this would also seem to be a dead end.

It isn't. 

ServerKeyExchange message (RFC 5246)
You see, before SSL/TLS peers can start engaging in all this fancy cryptography, they first need to decide which ciphers they're going to use. This is done through a negotiation process in which the client proposes some options (e.g., RSA, DHE, DHE-EXPORT), and the server picks one.

This all sound simple enough. However, one of the early, well known flaws in SSL/TLS is the protocol's failure to properly authenticate these 'negotiation' messages. In very early versions of SSL they were not authenticated at all. SSLv3 and TLS tacked on an authentication process -- but one that takes place only at the end of the handshake.* 

This is particularly unfortunate given that TLS servers often have the ability to authenticate their messages using digital signatures, but don't really take advantage of this. For example, when two parties negotiate Diffie-Hellman, the parameters sent by the server are transmitted within a signed message called the ServerKeyExchange (shown at right). The signed portion of this message covers the parameters, but neglects to include any information about which ciphersuite the server thinks it's negotiating. If you remember that the only difference between DHE and DHE-EXPORT is the size of the parameters the server sends down, you might start to see the problem.

Here it is in a nutshell: if the server supports DHE-EXPORT, the attacker can 'edit' the negotiation messages sent from the a client -- even if the client doesn't support export DHE -- replacing the client's list of supported ciphers with only export DHE. The server will in turn send back a signed 512-bit export-grade Diffie-Hellman tuple, which the client will blindly accept -- because it doesn't realize that the server is negotiating the export version of the ciphersuite. From its perspective this message looks just like 'standard' Diffie-Hellman with really crappy parameters. 

Overview of the Logjam active attack (source: paper).
All this tampering should run into a huge snag at the end of the handshake, when he client and server exchange Finished messages embedding include a MAC of the transcript. At this point the client should learn that something funny is going on, i.e., that what it sent no longer matches what the server is seeing. However, the loophole is this: if the attacker can recover the Diffie-Hellman secret quickly -- before the handshake ends -- she can forge her own Finished messages. In that case the client and server will be none the wiser.

The upshot is that executing this attack requires the ability to solve a 512-bit discrete logarithm before the client and server exchange Finished messages. That seems like a tall order.
Can you really solve a discrete logarithm before a TLS handshake times out?
In practice, the fastest route to solving the discrete logarithm in finite fields is via an algorithm called the Number Field Sieve (NFS). Using NFS to solve a single 512-bit discrete logarithm instance requires several core-years -- or about week of wall-clock time given a few thousand cores -- which would seem to rule out solving discrete logs in real time.

However, there is a complication. In practice, NFS can actually be broken up into two different steps:
  1. Pre-computation (for a given prime p). This includes the process of polynomial selection, sieving, and linear algebra, all of which depend only on p. The output of this stage is a table for use in the second stage.
  2. Solving to find a (for a given gmod p). The final stage, called the descent, uses the table from the precomputation. This is the only part of the algorithm that actually involves a specific g and ga.
The important thing to know is that the first stage of the attack consumes the vast majority of the time, up to a full week on a large-scale compute cluster. The descent stage, on the other hand, requires only a few core-minutes. Thus the attack cost depends primarily on where the server gets its Diffie-Hellman parameters from. The best case for an attacker is when p is hard-coded into the server software and used across millions of machines. The worst case is when p is re-generated routinely by the server.

I'll let you guess what real TLS servers actually do.

In fact, large-scale Internet scans by the team at University of Michigan show that most popular web servers software tends to re-use a small number of primes across thousands of server instances. This is done because generating prime numbers is scary, so implementers default to using a hard-coded value or a config file supplied by your Linux distribution. The situation for export Diffie-Hellman is particularly awful, with only two (!) primes used across up 92% of enabled Apache/mod_ssl sites.
Number of seconds to solve a
512-bit discrete log (source: paper).

The upshot of all of this is that about two weeks of pre-computation is sufficient to build a table that allows you to perform the downgrade against most export-enabled servers in just a few minutes (see the chart at right). This is fast enough that it can be done before the TLS connection timeout. Moreover, even if this is not fast enough, the connection can often be held open longer by using clever protocol tricks, such as sending TLS warning messages to reset the timeout clock.

Keep in mind that none of this shared prime craziness matters when you're using sufficiently large prime numbers (on the order of 2048 bits or more). It's only a practical issue you're using small primes, like 512-bit, 768-bit or -- and here's a sticky one I'll come back to in a minute -- 1024 bit.
How do you fix the downgrade to export DHE?
The best and most obvious fix for this problem is to exterminate export ciphersuites from the Internet. Unfortunately, these awful configurations are the default in a number of server software packages (looking at you Postfix), and getting people to update their configurations is surprisingly difficult (see e.g., FREAK).

A simpler fix is to upgrade the major web browsers to resist the attack. The easy way to do this is to enforce a larger minimum size for received DHE keys. The problem here is that the fix itself causes some collateral damage -- it will break a small but significant fraction of lousy servers that organically negotiate (non-export) DHE with 512 bit keys.

The good news here is that the major browsers have decided to break the Internet (a little) rather than allow it to break them. Each has agreed to raise the minimum size limit to at least 768 bits, and some to a minimum of 1024 bits. It's still not perfect, since 1024-bit DHE may not be cryptographically sound against powerful attackers, but it does address the immediate export attack. In the longer term the question is whether to use larger negotiated DHE groups, or abandon DHE altogether and move to elliptic curves.
What does this mean for larger parameter sizes?
The good news so far is that 512-bit Diffie-Hellman is only used by a fraction of the Internet, even when you account for active downgrade attacks. The vast majority of servers use Diffie-Hellman moduli of length at least 1024 bits. (The widespread use of 1024 is largely due to a hard-cap in older Java clients. Go away Java.)

While 2048-bit moduli are generally believed to be outside of anyone's reach, 1024-bit DHE has long been considered to be at least within groping range of nation-state attackers. We've known this for years, of course, but the practical implications haven't been quite clear. This paper tries to shine some light on that, using Internet-wide measurements and software/hardware estimates.

If you recall from above, the most critical aspect of the NFS attack is the need to perform large amounts of pre-computation on a given Diffie-Hellman prime p, followed by a relatively short calculation to break any given connection that uses p. At the 512-bit size the pre-computation only requires about a week. The question then is, how much does it cost for a 1024-bit prime, and how common are shared primes?

While there's no exact way to know how much the 1024-bit attack would cost, the paper attempts to provide some extrapolations based on current knowledge. With software, the cost of the pre-computation seems quite high -- on the order of 35 million core-years. Making this happen for a given prime within a reasonable amount of time (say, one year) would appear to require billions of dollars of computing equipment if we assume no algorithmic improvements. Even if we rule out such improvements, it's conceivable that this cost might be brought down to a few hundred million dollars using hardware. This doesn't seem out of bounds when you consider leaked NSA cryptanalysis budgets.

What's interesting is that the descent stage, required to break a given Diffie-Hellman connection, is much faster. Based on some implementation experiments by the CADO-NFS team, it may be possible to break a Diffie-Hellman connection in as little as 30 core-days, with parallelization hugely reducing the wall-clock time. This might even make near-real-time decryption of Diffie-Hellman connections practical.
Is the NSA actually doing this?
So far all we've noted is that NFS pre-computation is at least potentially feasible when 1024-bit primes are re-used. That doesn't mean the NSA is actually doing any of it.

There is some evidence, however, that suggests the NSA has decryption capability that's at least consistent with such a break. This evidence comes from a series of Snowden documents published last winter in Der Spiegel. Together they describe a large-scale effort at NSA and GCHQ, capable of decrypting 'vast' amounts of Internet traffic, including IPSec, SSH and HTTPS connections.

NSA slide illustrating exploitation
of IPSec encrypted traffic (source: Spiegel).
While the architecture described by the documents mentions attacks against many protocols, the bulk of the energy seems to be around the IPSec and IKE protocols, which are used to establish Virtual Private Networks (VPNs) between individuals and corporate networks such as financial institutions.

The nature of the NSA's exploit is never made clear in the documents, but diagram at right gives a lot of the architectural details. The system involves collecting Internet Key Exchange (IKE) handshakes, transmitting them to the NSA's Cryptanalysis and Exploitation Services (CES) enclave, and feeding them into a decryption system that controls substantial high performance computing resources to process the intercepted exchanges. This is at least circumstantially consistent with Diffie-Hellman cryptanalysis.

Of course it's entirely possible that the attack is based on a bad random number generator, weak symmetric encryption, or any number of engineered backdoors. There are a few pieces of evidence that militate towards a Diffie-Hellman break, however:

  1. IPSec (or rather, the IKE key exchange) uses Diffie-Hellman for every single connection, meaning that it can't be broken without some kind of exploit, although this doesn't rule out the other explanations.
  2. The IKE exchange is particularly vulnerable to pre-computation, since IKE uses a small number of standardized prime numbers called the Oakley groups, which are going on 17 years old now. Large-scale Internet scanning by the Michigan team shows that a majority of responding IPSec endpoints will gladly negotiate using Oakley Group 1 (768 bit) or Group 2 (1024 bit), even when the initiator offers better options.
  3. The NSA's exploit appears to require the entire IKE handshake as well as any pre-shared key (PSK). These inputs would be necessary for recovery of IKEv1 session keys, but are not required in a break that involves only symmetric cryptography.
  4. The documents explicitly rule out the use of malware, or rather, they show that such malware ('TAO implants') is in use -- but that malware allows the NSA to bypass the IKE handshake altogether.
I would stipulate that beyond the Internet measurements and computational analysis, this remains firmly in the category of  'crazy-eyed informed speculation'. But while we can't rule out other explanations, this speculation is certainly consistent with a hardware-optimized break of Diffie-Hellman 768 and 1024-bit, along with some collateral damage to SSH and related protocols.
So what next?
The paper gives a detailed set of recommendations on what to do about these downgrade attacks and (relatively) weak DHE groups. The website provides a step-by-step guide for server administrators. In short, probably the best long-term move is to switch to elliptic curves (ECDHE) as soon as possible. Failing this, clients and servers should enforce at least 2048-bit Diffie-Hellman across the Internet. If you can't do that, stop using common primes.

Making this all happen on anything as complicated as the Internet will probably consume a few dozen person-lifetimes. But it's something we have to do, and will do, to make the Internet work properly.

Notes:

* There are reasons for this. Some SSL/TLS ciphersuites (such as the RSA encryption-based ciphersuites) don't use signatures within the protocol, so the only way to authenticate the handshake is to negotiate a ciphersuite, run the key exchange protocol, then use the resulting shared secret to authenticate the negotiation messages after the fact. But SSL/TLS DHE involves digital signatures, so it should be possible to achieve a stronger level of security than this. It's unfortunate that the protocol does not.

Thursday, April 16, 2015

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.

Thursday, April 2, 2015

Truecrypt report

A few weeks back I wrote an update on the Truecrypt audit promising that we'd have some concrete results to show you soon. Thanks to some hard work by the NCC Crypto Services group, soon is now. We're grateful to Alex, Sean and Tom, and to Kenn White at OCAP for making this all happen.

You can find the full report over at the Open Crypto Audit Project website. Those who want to read it themselves should do so. This post will only give a brief summary.

The TL;DR is that based on this audit, Truecrypt appears to be a relatively well-designed piece of crypto software. The NCC audit found no evidence of deliberate backdoors, or any severe design flaws that will make the software insecure in most instances.

That doesn't mean Truecrypt is perfect. The auditors did find a few glitches and some incautious programming -- leading to a couple of issues that could, in the right circumstances, cause Truecrypt to give less assurance than we'd like it to.

For example: the most significant issue in the Truecrypt report is a finding related to the Windows version of Truecrypt's random number generator (RNG), which is responsible for generating the keys that encrypt Truecrypt volumes. This is an important piece of code, since a predictable RNG can spell disaster for the security of everything else in the system.

The Truecrypt developers implemented their RNG based on a 1998 design by Peter Guttman that uses an entropy pool to collect 'unpredictable' values from various sources in the system, including the Windows Crypto API itself. A problem in Truecrypt is that in some extremely rare circumstances, the Crypto API can fail to properly initialize. When this happens, Truecrypt should barf and catch fire. Instead it silently accepts this failure and continues to generate keys.


This is not the end of the world, since the likelihood of such a failure is extremely low. Moreover, even if the Windows Crypto API does fail on your system, Truecrypt still collects entropy from sources such as system pointers and mouse movements. These alternatives are probably good enough to protect you. But it's a bad design and should certainly be fixed in any Truecrypt forks.

In addition to the RNG issues, the NCC auditors also noted some concerns about the resilience of Truecrypt's AES code to cache timing attacks. This is probably not a concern unless you're perform encryption and decryption on a shared machine, or in an environment where the attacker can run code on your system (e.g., in a sandbox, or potentially in the browser). Still, this points the way to future hardening of any projects that use Truecrypt as a base.

Truecrypt is a really unique piece of software. The loss of Truecrypt's developers is keenly felt by a number of people who rely on full disk encryption to protect their data. With luck, the code will be carried on by others. We're hopeful that this review will provide some additional confidence in the code they're starting with.

Tuesday, March 3, 2015

Attack of the week: FREAK (or 'factoring the NSA for fun and profit')

Cryptography used to be considered
'munitions'.
This is the story of how a handful of cryptographers 'hacked' the NSA. It's also a story of encryption backdoors, and why they never quite work out the way you want them to.

But I think I'm getting ahead of myself a bit here.

Today's Washington Post has the story of a nasty bug in some TLS/SSL servers and clients, one that has the potential to downgrade the security of your TLS connections to something that isn't really secure at all. In this post I'm going to talk about the technical aspects of the attack, why it matters, and how bad it is.

If you don't want to read a long blog post, let me give you a TL;DR:
A group of cryptographers at INRIA, Microsoft Research and IMDEA have discovered some serious vulnerabilities in OpenSSL (e.g., Android) clients and Apple TLS/SSL clients (e.g., Safari) that allow a 'man in the middle attacker' to downgrade connections from 'strong' RSA to 'export-grade' RSA. These attacks are real and exploitable against a shocking number of websites -- including government websites. Patch soon and be careful. 
You can find a detailed description of the work by the researchers -- Beurdouche, Bhargavan, Delignat-Lavaud, Fournet, Kohlweiss, Pironti, Strub, Zinzindohoue, Zanella-B├ęguelin -- at their site SmackTLS.com. You should go visit that site and read about the exploits directly. The proof of concept implementation also involved contributions from Nadia Heninger at U. Penn.

I'm going to explain the rest of it in the 'fun' question and answer format I save for this kind of attack.
What is SSL/TLS and what are ‘EXPORT cipher suites’ anyway?
In case you’re not familiar with SSL and its successor TLS, what you should know is that they're the most important security protocols on the Internet. In a world full of untrusted networks, SSL and TLS are what makes modern communication possible.

Or rather, that’s the theory. In practice, SSL and TLS have been a more like a work in progress. In part this is because they were developed during an era when modern cryptographic best practices weren't nailed down yet. But more to the point: it's because even when the crypto is right, many software implementations still get things wrong.

With all that in mind, there’s a third aspect of SSL/TLS that doesn't get nearly as much attention. That is: the SSL protocol itself was deliberately designed to be broken

Let me explain what I mean by that.

Back in the early 1990s when SSL was first invented at Netscape Corporation, the United States maintained a rigorous regime of export controls for encryption systems. In order to distribute crypto outside of the U.S., companies were required to deliberately 'weaken' the strength of encryption keys. For RSA encryption, this implied a maximum allowed key length of 512 bits.*

The 512-bit export grade encryption was a compromise between dumb and dumber. In theory it was designed to ensure that the NSA would have the ability to 'access' communications, while allegedly providing crypto that was still 'good enough' for commercial use. Or if you prefer modern terms, think of it as the original "golden master key".

The need to support export-grade ciphers led to some technical challenges. Since U.S. servers needed to support both strong and weak crypto, the SSL designers used a 'cipher suite' negotiation mechanism to identify the best cipher both parties could support. In theory this would allow 'strong'
EXP-RC4-MD5.
clients to negotiate 'strong' ciphersuites with servers that supported them, while still providing compatibility to the broken foreign clients.

This story has a happy ending, after a fashion. The U.S eventually lifted the most onerous of its export policies. Unfortunately, the EXPORT ciphersuites didn't go away. Today they live on like zombies -- just waiting to eat our flesh.
If EXPORT ciphers are known to be broken, what's the news here?
We don't usually worry about export-grade cipher suites very much, because supposedly they aren't very relevant to the modern Internet. There are three general reasons we don't think they matter anymore:
  1. Most 'modern' clients (e.g., web browsers) won't offer export grade ciphersuites as part of the negotiation process. In theory this means that even if the server supports export-grade crypto, your session will use strong crypto.
  2. Almost no servers, it was believed, even offer export-grade ciphersuites anymore.
  3. Even if you do accidentally negotiate an export-grade RSA ciphersuite, a meaningful attack still requires the attacker to factor a 512-bit RSA key (or break a 40-bit symmetric cipher). This is doable, but it's generally considered too onerous if you have to do it for every single connection.
This was the theory anyway. It turns out that theory is almost always different than practice. Which brings us to the recent work by Beurdouche et al. from INRIA, Microsoft Research and IMDEA.

What these researchers did was develop a fairly beautiful piece of formal analysis tooling that allows them to 'fuzz' the state machines of most modern SSL/TLS implementations. They found a bunch of wonderful things in the course of doing this -- some of them quite nasty. I'm not going to cover all of them in this post, but the one we care about here is quite simple.

You see, it turns out that some modern TLS clients -- including Apple's SecureTransport and OpenSSL -- have a bug in them. This bug causes them to accept RSA export-grade keys even when the client didn't ask for export-grade RSA. The impact of this bug can be quite nasty: it admits a 'man in the middle' attack whereby an active attacker can force down the quality of a connection, provided that the client is vulnerable and the server supports export RSA.

The MITM attack works as follows:
  1. In the client's Hello message, it asks for a standard 'RSA' ciphersuite.
  2. The MITM attacker changes this message to ask for 'export RSA'.
  3. The server responds with a 512-bit export RSA key, signed with its long-term key.
  4. The client accepts this weak key due to the OpenSSL/SecureTransport bug.
  5. The attacker factors the RSA modulus to recover the corresponding RSA decryption key.
  6. When the client encrypts the 'pre-master secret' to the server, the attacker can now decrypt it to recover the TLS 'master secret'.
  7. From here on out, the attacker sees plaintext and can inject anything it wants.
So that's bad news and it definitely breaks our assumption in point (1) above. But at least in theory we should still be safe based on points (2) and (3).

Right?
How common are export-enabled TLS servers?
No matter how bad you think the Internet is, it can always surprise you. The surprise in this case is that export-grade RSA is by no means as extinct as we thought it was.

Based on some recent scans by Alex Halderman, Zakir Durumeric and David Adrian at University of Michigan, it seems that export-RSA is supported by as many as 5.2% 36.7% (!!!!) of the 14 million sites serving browser-trusted certs. The vast majority of these sites appear to be content distribution networks (CDN) like Akamai. Those CDNs are now in the process of removing export grade suites.

While the numbers are impressive, the identity of those sites is a bit more worrying. They include U.S. government sites like www.nsa.gov (Oy vey), www.whitehouse.gov and www.irs.gov. It turns out that the FBI tip reporting site (tips.fbi.gov) was also vulnerable.

Vulnerable sites also included connect.facebook.net, which is the source of the famous Facebook 'Like' button which shows up on secure web pages all over the Internet. Attacks on these connections could lead to content injection on a huge number of web pages.

(Facebook have updated their configuration as a result of this work.)
Factoring an RSA key seems pretty expensive for breaking one session.
This brings us to the most awful part of this attack. You don't have to be that fast.

You see, it turns out that generating fresh RSA keys is a bit costly. So modern web servers don't do it for every single connection. In fact, Apache mod_ssl by default will generate a single export-grade RSA key when the server starts up, and will simply re-use that key for the lifetime of that server.

What this means is that you can obtain that RSA key once, factor it, and break every session you can get your 'man in the middle' mitts on until the server goes down. And that's the ballgame.
PoC or GTFO.
This is what happens to EC2 spot pricing
when Nadia runs 75 'large' instances
to factor a 512-bit key.
Just because someone says an implementation is vulnerable doesn't mean it actually is. You should ask for proof. 

Fortunately, a proof of concept for this attack requires only a few ingredients. First, you need some tooling to actually run the MITM attack. Then you need the ability to (quickly) factor 512-bit RSA keys. From there it's just a question of finding a vulnerable client and server.

The guts of the PoC were put together by Karthik Bhargavan and Antoine Delignat-Lavaud at INRIA. They assembled an MITM proxy that can intercept connections and re-write them to use export-RSA against a willing website.

To factor the 512-bit export keys, the project enlisted the help of Nadia Heninger at U. Penn, who has been working on "Factoring as a Service" for exactly this purpose. Her platform uses cado-nfs on a cluster of EC2 virtual servers, and (with Nadia doing quite a bit of handholding to deal with crashes) was able to factor a bunch of 512-bit keys -- each in about 7.5 hours for $104 in EC2 time.

From there all you need is a vulnerable website. 

Since the NSA was the organization that demanded export-grade crypto, it's only fitting that they should be the first site affected by this vulnerability. There's great video on the SmackTLS site. After a few hours of factoring, one can take the original site (which looked like this):



And change it into this:

Attack images courtesy Karthik, Antoine INRIA.

Very dramatic.

Some will point out that an MITM attack on the NSA is not really an 'MITM attack on the NSA' because NSA outsources its web presence to the Akamai CDN (see obligatory XKCD at right). These people may be right, but they also lack poetry in their souls.
Is it patched?
The most recent of OpenSSL does have a patch. This was announced (though not very loudly) in January of this year.

Apple is working on a patch.

Akamai and other CDNs are also rolling out a patch to solve these problems. Over the next two weeks we will hopefully see export ciphersuites extinguished from the Internet. In the mean time, try to be safe.
What does it all mean?
You might think this is all a bit absurd and doesn’t affect you very much. In a strictly technical sense you’re probably right. The client bugs will soon be patched (update your devices! unless you have Android in which case you're screwed). With good luck, servers supporting export-grade RSA cipher suites will soon be rare curiosity.

Still, to take this as the main lesson of the work would, I think, be missing the forest for the trees. There’s a much more important moral to this story.

The export-grade RSA ciphers are the remains of a 1980s-vintage effort to weaken cryptography so that intelligence agencies would be able to monitor foreign traffic. This was done badly. So badly, that while the policies were ultimately scrapped, they’re still hurting us today.

This might be an academic point if it was only a history lesson. However, for the past several months, U.S. and European politicians have been publicly mooting the notion of a new set of cryptographic backdoors in systems we use today. While the proposals aren't explicit, they would presumably involve deliberately weakening encryption tech so that governments can intercept and read our conversations. While officials carefully avoid the term “back door” — or any suggestion of weakening our encryption systems against real attackers — this is wishful thinking. These systems are already so complex that even normal issues stress them to the breaking point. There's just no room for new backdoors.

To be blunt about it, the moral is pretty simple:
Encryption backdoors will always turn around and bite you in the ass. They are never worth it.
Acknowledgements

Special thanks to Karthik and Antoine for sharing this with me, Nadia for factoring, Ivan Ristic for interrupting his vacation to get us data, and the CADO-NFS team for the software that made this possible.

Notes:

* Export controls might have made some sense in the days when ‘encryption’ meant big clunky pieces of hardware, but it was nonsensical in a world of software. Non-U.S. users could easily skirt the paltry IP-address checks to download strong versions of browsers such as Netscape, and — when that was too much trouble — they could easily re-implement the crypto themselves or use foreign open source libraries. (The requirements became so absurd that mainstream U.S. companies like RSA Security wound up hiring foreign developers to build their encryption libraries, since it was easier to import strong encryption than to export it.)

Thursday, February 19, 2015

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.