Imperfect Forward Secrecy: The Coming Cryptocalypse
If the Snowden debacle has accomplished anything, it’s raising public awareness in cryptography. This has spawned some sort of meme that if we use “perfect forward secrecy”, our communications are protected from the NSA! Various blog posts and articles in major newspapers have conferred all sorts of magical secret powers onto perfect forward secrecy, specifically surrounding its NSA-fighting powers, going as far to say that perfect forward secrecy is NSA-proof.
First off, let me say that forward secrecy is great, and you should try to deploy it if you can. However, even if you run a stack that supports it (many hardware SSL terminators do not, for example), it’s still pretty hard to implement properly (you need to rotate session ticket keys frequently to gain anything from it, for example).
But let’s not beat around the bush: perfect forward secrecy isn’t some magical silver bullet against the NSA. To understand why we need to take a look at what it actually does: generate short-term public keys that are used to establish a shared secret between two parties, then sign these short-term keys with long-term keys that tie back into PKI certificate chains we can use to validate them. Since the long-term private keys are only used for creating digital signatures, and not encrypting the session, future compromises of the long-term keys will not affect the security of past sessions, since the past sessions were protected by the (randomly generated) short-term keys.
Forward secrecy comes from the fact that shortly after the session is established (sometimes days, sometimes minutes) the private keys are forgotten by all parties involved. If everyone does their due diligence to ensure all the private keys are destroyed, we are protected from future key compromises, because you can’t compromise what’s not there anymore. Since all parties involved have destroyed the private keys, it should be impossible to recover the session, hence the “perfect” part of perfect forward secrecy, right?
Wrong. There’s a problem: in order to use a short-term key to establish a session, we need to transmit it to another party in plaintext. This is, after all, a public key we use to set up the actual encrypted session, so at this point we don’t really have any way of encrypting it. Signing it takes care of ensuring the key is authentic, trusted, and otherwise unmanipulated by a malicious middleman, but we have no way to keep it confidential if we want to use it to set up a session with another party and we have no shared secrets.
So we send it in the clear. What’s wrong with that? Isn’t that what public key cryptography is all about? Well, there’s a problem: the NSA has just sniffed the short-term public key that was used to establish a particular session. If you are a Person of Interest, they could easily sniff all of the encrypted packets that make up a particular session, and not just for that session, they could repeat this for all of your Internet communications, including things like PGP encrypted emails (of the sort that Edward Snowden sent to Glenn Greenwald).
They are building a massive datacenter in Utah that’s rumored to have an asston of storage, certainly enough for them to suck down all the Internet traffic of people they’re suspicious of, and they’ve got beam splitters giving them access to backbone Internet traffic in 10 major datacenters around the country. If they find you suspicious enough they want to archive all your traffic, and you talk over anything they have tapped, they can easily download and store everything you do online.
If the NSA can break the public keys used for your sessions, and derive their corresponding private keys, it can decrypt all of your sessions, regardless of whether you used “perfect” forward secrecy.
How can the NSA break your public key and derive the corresponding private key? If the NSA wanted to break one of your HTTPS sessions with https://encrypted.google.com, which uses ECDHE for forward secrecy, they would need to break an ECDSA key associated with that session. To do that, they would need to have some way of solving the discrete logarithm problem, the problem which makes public key cryptography hard in one direction, so deriving private keys from public ones is not practical, but easy in another, so calculating public keys from private ones is fast, particularly with the elliptic curve cryptography ECDHE uses.
ECDHE works great today, but for how long? Unfortunately, there’s doom on the horizon, not just for ECDHE, but for RSA, DSA, and practically all forms of public key cryptography we use today. That doom comes in the form of quantum computers.
Quantum computers are odd beasts that need very specialized programs in order to work efficiently. However, one of the areas where they can be extremely effective is cryptography. Shor’s algorithm, devised in 1994, can leverage the potential power of quantum computers to efficiently factor large numbers, and thus break public keys and derive the private ones. Unfortunately, at the time it was created, quantum computers didn’t exist.
Fast forward to today: quantum computing has been taking its first baby steps into practicality in the form of the 512-qubit D-Wave 2 (where a qubit is the quantum analogue of a bit). Some of the first commercial quantum computers were just sold to Google and NASA. You might relax for now, because the D-Wave 2 doesn’t come close to having what it takes to challenge modern public key cryptography, which would require several orders of magnitude more qubits. But it was only last year that an 84-qubit computer was making headlines.
We’ll see if there’s a Moore’s Law of quantum computing or not, but given past trends it seems like a reasonable wager that quantum computers will continue to get more powerful, and perhaps exponentially so like we saw with transistor-based computers. D-Wave’s (undoubtedly optimistic) CEO claims “In 10 years’ time, I’d be hugely disappointed if we didn’t have a machine capable of factoring a 1,000-bit number, involving millions of qubits”.
What happens in 10-20 years (or what have you) when quantum computers, like their classical predecessors, are no longer confined to the labs of NASA (or the NSA), and do start reaching the millions of qubits range at which they become practically useful for breaking public keys, at least the kind we use today? When this happens, it means that anyone (not just the NSA!) who can get their hands on a quantum computer, and has captured one of your HTTPS sessions, can break your session and recover the plaintext. Perfect forward secrecy be damned!
When that happens, we’ll have entered the age of post-quantum cryptography:
Imagine that it’s fifteen years from now. Somebody announces that he’s built a large quantum computer. RSA is dead. DSA is dead. Elliptic curves, hyperelliptic curves, class groups, whatever, dead, dead, dead. So users are going to run around screaming and say “Oh my God, what do we do?” Well, we still have secret-key cryptography, and we still have some public-key systems. There’s hash trees. There’s NTRU. There’s McEliece. There’s multivariate-quadratic systems. But we need more experience with these. We need algorithms. We need paddings, like OAEP. We need protocols. We need software, working software for these systems. We need speedups.
In order to defeat quantum computers, we will need to switch to a new class of algorithms which are at least NP-hard, such as McEliece (which is based on linear codes) or Lamport Signatures (which are based on hash functions). Switching to these schemes today has a number of drawbacks: no good implementations, giant keys, and in the case of Lamport Signatures a single-use problem.
The good news is that Dan Bernstein (owner of the cr.yp.to domain, what other credentials do you need?) has been working on a practical post-quantum public key encryption system called McBits. More good news: quantum computers suck at breaking symmetric encryption, great if you just want to encrypt something with a password or have shared it with someone in advance, but unfortunately most of the time symmetric keys are established using the kinds of public key algorithms that quantum computers can destroy.
If we really want to keep our communications secure from the NSA, what do we need to do? All this talk about post-quantum cryptography might scare you, and maybe we do need to jump on better algorithms soon, but there are way bigger problems that might give the NSA access to your data today, like sending email in plaintext because encryption apps are too damn hard to use, or the fact that computer systems are riddled with all sorts of vulnerabilities (which companies like Microsoft handed over to the NSA before they were made public, which could potentially be used to break into the computers of Persons of Interest). Cryptography won’t help you if someone can break into your computer and steal all the plaintexts right out of your computer’s RAM.
All that said, does truly perfect, NSA-proof encryption exist? Yes, it’s called the one-time pad, in which data is encrypted with a single-use pad of the same size by performing an XOR operation. OTP is the only truly perfect encryption system, and with the continuing growth in capacity of things like USB keychain drives, OTP is a great practical choice if you want to have truly confidential (so long as you have truly random numbers), futureproof (so long as you don’t lose or reuse your keys!) encrypted conversations with anyone you can swap USB keychains with in person. Reuse the pad though, and it’s all over!