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. 

Wednesday, February 18, 2015

Another update on the Truecrypt audit

There's a story on Hacker News asking what the hell is going on with the Truecrypt audit. I think that's a fair question, since we have been awfully quiet lately. To everyone who donated to the project, first accept my apologies for the slow pace. I want to promise you that we're not spending your money on tropical vacations (as appealing as that would be). In this post I'd like to offer you some news, including an explanation of why this has moved slowly.

For those of you who don't know what the Truecrypt audit is: in late 2013 Kenn White, myself, and a group of advisors started a project to undertake a crowdfunded audit of the Truecrypt disk encryption program. To the best of my knowledge, this is the first time anyone's tried this. The motivation for the audit is that lots of people use Truecrypt and depend on it for their security and safety -- yet the authors of the program are anonymous and somewhat mysterious to boot. Being anonymous and mysterious is not a crime, but it still seemed like a nice idea to take a look at their code.

We had an amazing response, collecting upwards of $70,000 in donations from a huge and diverse group of donors. We then went ahead and retained iSEC Partners to evaluate the bootloader and other vulnerability-prone areas of Truecrypt. The initial report was published here.

That initial effort was Part 1 of a two-part project. The second -- and much more challenging part -- involves a detailed look at the cryptography of Truecrypt, ranging from the symmetric encryption to the random number generator. We had some nice plans for this, and were well on our way to implementing them. (More on those in a second.)

Then in late Spring of 2014, something bizarre happened. The Truecrypt developers pulled the plug on the entire product -- in their typical, mysterious way.

This threw our plans for a loop. We had been planning a crowdsourced audit to be run by Thomas Ptacek and some others. However in the wake of TC pulling the plug, there were questions. Was this a good use of folks' time and resources? What about applying those resources to the new 'Truecrypt forks' that have sprung up (or are being developed?) There were a few other wrinkles as well, which Thomas talks about here -- although he takes on too much of the blame.

It took us a while to recover from this and come up with a plan B that works within our budget and makes sense. We're now implementing this. A few weeks ago we signed a contract with the newly formed NCC Group's Cryptography Services practice (which grew out of iSEC, Matasano and Intrepidus Group). The project will evaluate the original Truecrypt 7.1a which serves as a baseline for the newer forks, and it will begin shortly. However to minimize price -- and make your donations stretch farther -- we allowed the start date to be a bit flexible, which is why we don't have results yet.

In our copious spare time we've also been looking manually at some portions of the code, including the Truecrypt RNG and other parts of the cryptographic implementation. This will hopefully complement the NCC/iSEC work and offer a bit more confidence in the implementation.

I don't really have much more to say -- except to thank all of the donors for their contributions and their patience. This project has been a bit slower than any of us would like, but results are coming. Personally, my hope is that they'll be completely boring.

Tuesday, February 10, 2015

How do we pay for privacy?

(source)
If you haven't read Julia Angwin's excellent profile of GnuPG's lead developer Werner Koch, now would be a great time to check it out. Koch, who single-handedly wrote GnuPG in 1997, has been doggedly maintaining the codebase ever since -- and not getting paid very well for it. Despite good intentions on all sides, Koch has been essentially going broke.

The news is not all bad. In response to Angwin's piece, 'the Internet' rallied to GnuPG's aid. So far individual and corporate donors have coughed up over EU 200,000 to pay Koch and even hire him some help. It looks like GnuPG is saved, and so are its users — for the moment.

But is this model really sustainable? I'm pretty skeptical.

Sooner or later this money will run out. And next time this happens, the Internet might not have a quarter million in spare change to fork over. In fact, that's already the normal state of affairs for most privacy tools -- software ranging from GPGTools to OTR -- most of which subsist on meager donations and volunteer time. The scary part is that thousands of people depend on these tools for their privacy and even their physical safety.

This raises a question: how can we support the long-term development and maintenance of privacy tools? It turns out that nobody really knows the answer to this -- but a few people are groping towards a solution. In this (entirely non-technical) post I'm going to talk a bit about what people are doing today -- and how we might do better in the future.

NB: I should mention that most of the smart ideas in this post come from Meredith Whittaker, who leads Google’s Open Source Research Group, and helped found Simply Secure. The dumb ideas are all mine.

How we support privacy tools today

If you're developing, or are interested in developing privacy tools in 2015, there are a handful of funding sources for you to choose from. They include:

  1. Self-funding. The vast majority of privacy tools come from engineers working in their spare time. This is a great way to develop prototypes and simple tools, but it tends not to be very sustainable -- particularly when developers have to choose between family and code maintenance.
  2. Donations, charges and crowd-funding. A few major projects pull in some cash through donations, but this seems to work well only during a catastrophe or when the spotlight is on a particular project. GnuPG, for example, made a ton of money following their recent publicity, but before that they averaged a minuscule $20k per year — and this is for one of the most widely used privacy tools on the Internet! Projects like GPG Tools recently began charging for their software, which may work a bit better. Unfortunately this is anathema for young projects that rely on network effect for their success.
  3. Industry grants. From time to time major corporations give out modest chunks of money to tool developers, particularly when those companies use tools internally. Case in point: Google Stripe and Facebook just gave $50k each to GnuPG, and the Linux Foundation Core Infrastructure Initiative (essentially an industry funding group*) kicked in an additional $60k. Unfortunately this money is tragically difficult to come by -- for the average developer it might as well not exist.
  4. Government and NGOs. Perhaps the most promising source of money comes from the U.S. government, and a set of NGOs that have sprung up to disburse it. The State Dept. directly funds the Tor Project, and the government also provides block grants to groups such as the Open Technology Fund (via Radio Free Asia) and the -- confusingly similar -- Open Technology Institute (at New America Foundation). OTF in particular has done a phenomenal job at funding both development and audit of privacy tools.
  5. Internal industry funding. Once in a blue moon a company proposes to internally develop a privacy tool like Google/Yahoo End-to-End. I’ll believe this works when I see it.
  6. Academic research funding. A few academic tools have managed to slip into this space, most notably OTR and Tor. But this model is awfully hard to sustain, mostly because academics don't get paid to do things. We get paid to teach and write papers. It's hard to sustain software development this way.
  7. Bitcoin wallet theft. This is mostly a joke.

Of these funding sources, the U.S. government is by far the heaviest hitter -- responsible for funding many well-known projects such as Tor and TextSecure. While I tend to think any money is good money in the hands of right people, I should point out that this view is not universally shared. In part this is because we, admittedly, don’t have much of a process to validate code and convince non-experts that this process isn’t producing compromised code. 

As Jillian York points out, US government funding also comes with some political baggage, and sadly, tends to attract more than its fair share of paranoia.

Developers need more than just money!

If you give a starving privacy tool a million bucks, you get a well-fed privacy tool. Unfortunately it may not actually be a better privacy tool. That's not because people are trying to waste your cash. It turns out that software development, crypto, and security are just plain hard.

So yes, people need to eat -- that's a baseline. But beyond that what developers also need are things like expert guidance, security audits, analysis tools, and collaboration with other developers. They also really need help with the hardest problem in computer science, which is turning a pile of code into a product that people want to use.

A few groups like OTF (in case you're not getting the hint, I really like them*) are trying to help with some of this. They fund professional code audits through groups like iSEC Partners. They fund usability resources and provide communications help. They host regular meetings where project members can get together and dork out about how to handle encrypted spam. A friend calls this a 'dog park for developers who haven't been outside for a while.' This sounds silly, but it really, really helps.

Beyond those things, there's still an awful problem of coordinating all of this technical stuff so that auditing results adhere to some consistent standard and produce knowledge that gets retained within the organization, as well as seeing that tools get proper academic analysis where necessary. And finally, there are useful services such as connecting developers with UI designers and helping them to turn their tools into real, usable products.

A few groups have done well at this all on their own. Moxie's Open Whisper Systems not only launched a popular messaging app, but managed to get TextSecure (the protocol) into 600 million WhatsApp clients. Unfortunately this kind of success doesn't come easy to people and requires a lot of assistance. Institutions can really help.

How can we do better?

There are a lot of answers to this question. But since this is a blog post, let's swing for the fences. What's really needed is a privacy incubator. A place that provides both funding (or at least, guides funding) as well as in-house technical staff and researchers, non-technical help such a communications, infrastructure, a great advisory board, and access to tools and engineers.

In essence this center would combine all the best parts of NGOs, academic institutions, and corporate research into one center. It would help with projects ranging from research to development, and would also provide infrastructure for developers -- helping to keep them from re-inventing the wheel with each new idea, and perhaps even helping projects to merge when one has strengths. Connecting them with corporations who could conceivably deploy their tool.

This organization could also provide resources ranging from legal advice to marketing, two areas that software developers are notoriously bad at. It might even provide important, but miscellaneous resources healthcare.
Please keep in mind I'm not advocating the creation of an entirely new organization -- god forbid, we have enough of those already (the XKCD cartoon at right comes to mind). Instead, the goal should be to identify organizations that are already working and either connect that, or build up their capabilities with a large infusion of cash.

Anyway, we can all dream. But this is a dream that would actually make some difference.

So will this happen?

I guess it depends on the will and the money. It also depends on us: that is, on the willingness of the technically focused privacy/security community to accept that many of the elements we need to succeed are outside of our personal realm of expertise, and we need help with them.

Friends of mine also keep telling me that there are major philanthropic organizations out there looking to make a difference in this area. I'm still waiting to see it happen, but wheels turn slowly. One thing I can tell you: it wouldn't take much to do better than what we have today.

* Full disclosure: I'm on the advisory board for Linux Foundation's Core Infrastructure Initiative. I also once sat in on an advisory board meeting for OTF. Nobody paid me -- but they did feed me lunch.

Wednesday, January 14, 2015

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.