SMBlog — December 2015

Cryptography is Hard

In the debate about "exceptional access" to encrypted conversations, law enforcement says they need such access to prevent and solve crimes; cryptographers, on the other hand, keep saying it’s too complicated to do safely. That claim is sometimes met with skepticism: what’s so hard about encryption? After all, you learn someone’s key and just start encrypting, right? I wish it were that simple—but it’s not. I’m going to try the impossible: I’m going to give an example of how cryptography is really used, and how it can fail. I warn you in advance that this blog post is considerably more technical than most that I write. If at any point you get lost, skip ahead to the Summary.

I’m first going to describe a cryptographic protocol, a stylized set of messages used to set up an encrypted session in the real world. The particular protocol I’m going to describe was devised in 1978 by Roger Needham and Michael Schroeder; it’s the oldest protocol in the unclassified literature. I’m going to focus on their Protocol 2.

Before I start, though, I need to describe some concepts and notation. We’ll assume that everyone has a "key pair", a public key that is used to encrypt messages and a private key to decrypt them. If I write

{M}_Ka

I mean "encrypt message M with the public key Ka belonging to A". Only A has the private key necessary to decrypt it.

Cryptographers also make use of numbers known as nonces. A nonce is a random number used one time and one time only. We use nonces for a variety of purposes. One is to make sure that a message is "fresh": it’s not an old message that is being replayed. We also use nonces to generate session keys, the actual key used to encrypt some traffic. (Why do we use session keys? There are many reasons; the simplest to understand is that if through some accident today’s session key is revealed, you don’t want yesterday’s or tomorrow’s traffic to be at risk.) If a nonce is only used once and a session key is made from a nonce, you know that the session key will only be used once.

Cryptographers also speak of the threat model: what we assume the enemy can and cannot do. Much of the time, it’s pretty simple: just assume that any time you want to send a messages to someone, you do it by giving the message to your enemy to deliver. When you receive a message, it’s handed to you by the enemy. In other words, you can’t trust the network. The enemy can discard your messages, copy them, deliver them multiple times, rearrange them, invent messages, even create messages made up of pieces of older messages that may or may not have been delivered. It sounds preposterous, but there are real-world examples of attackers doing all of those things.

The attackers are pretty good at hacking; they can penetrate some (but not all) of the computers involved. We’ll assume that she can’t hack the computers belonging to either of the two parties who really want to talk securely, or we wouldn’t have to do any more.

Oddly enough, there’s one thing we generally assume the enemy can’t do: break the encryption algorithm. That is, if I send

{M}_Ka

to A, even via an enemy-controlled network, I can safely assume that the attacker can’t read it. It turns out that we know a lot about encryption algorithms today, and we have a pretty good handle on what can and cannot be done. ("What about Enigma?" I hear you say. Apart from the fact that it’s an 80-year-old design and the state of the art has advanced considerably since then, the real problem wasn’t that the design was weak. Rather, it was that the Germans often used it incorrectly. For example, when creating a sesion key, some soldiers would type things like XXX. The British caught on to patterns like that… There were other errors, too, in the analog of what today would be called a cryptographic protocol.) We’ll also assume that an encrypted message can’t be tampered with; if it is, it won’t decrypt properly and the recipient will notice. This itself isn’t a trivial property to achieve, but we’ll ignore that today.

Are you still with me? Good. It’s time to begin!

Suppose that computer A wants to talk securely to computer B. (Cryptographers anthropomorphize their computers and say that Alice wants to talk to Bob.) To do that, Alice and Bob have to set up a session key. Alice also wants to be sure she’s talking to Bob and not to some enemy whom I’ll dub E, Eve, the eavesdropper. In other words, authentication—making sure you’re talking to the right party—is a vital part of the process, too. It’s not enough to set up a session key, it has to be set up with exactly the right party, and both parties have to know the identity of the other party.

I’m going to assume that Alice knows Bob’s public key Kb and Bob knows Alice’s key Ka. I won’t go into how they know it; let it suffice to say that if there’s another party whom they both trust, it’s a solved problem. (In the real world, that sort of mutual trust is hard to come by, but that’s a post for another day, too.)

Alice starts by sending a message to Bob:

A → B: {Na, A}_Kb

In English, this says, "I, Alice, am sending my name and a nonce Na; those are encrypted with Bob’s public key Kb, and no one else can read or tamper with that part of the message." After this message is sent and received, both Alice and Bob know that Alice wants to talk to Bob and that she has sent Na. Eve knows who wants to talk to whom, but doesn’t know Na.

The next message, from Bob to Alice, is a bit more subtle:

B → A: {Na,Nb}_Ka

Bob has returned Alice’s nonce to her, generated his own nonce Nb, and encrypted both with Alice’s key Ka. Why does Bob send Alice’s nonce back to her? It serves two different purposes. First, it assures freshness: this is a response to Alice’s message from this session, not from some other run of the protocol. It’s not an old message that Eve has saved up to confuse things. At least as important, it shows that the message really came from Bob: Na was sent encrypted to Bob, so no one else could have read it. In other words, Alice now knows that despite Eve’s best efforts, her message got through to Bob and Bob got his reply through to Alice. (Recall that if Eve tampered with an encrypted message, it wouldn’t decrypt properly, which Alice would have noticed.)

At this point, both Alice and Bob know Na and Nb; Eve knows neither.

In the third and last message, Alice returns Bob’s nonce to him:

A → B: {Nb}_Kb

This proves that Alice received message 2 correctly; otherwise, she wouldn’t know Nb.

At the end of this protocol, Alice and Bob each know both nonces; more important, both know that the other party knows both nonces. They also know who the other party is; only Bob can read messages encrypted with Kb and only Alice can read messages encrypted with Ka. They can then use those nonces to generate a session key. (I won’t go into how that’s done, but today that isn’t that hard.) Problem solved, right? There are two values that they and only they know.

The point here is that encryption, even in a simple scenario, isn’t that simple. You really need a session key; setting that up properly takes several messages and things like nonces. This isn’t even a realistic scenario—where does Alice’s private key come from? Her password is the obvious answer, but she doesn’t want to type it constantly. For a more realistic design—that is, one more usable in the real world—see this dialog about the design of the Kerberos system. It’s not easy going, but it’s probably easier than the rest of this essay.

As complex as those two protocols seem, I’ve still oversimplified things. For example, I completely ignored the difficulty of actually doing the encryptions, and that matters. The most straightforward way of doing {Na,A}_Kb only operates on blocks of exactly 256 bytes when using today’s normal key sizes. How do you handle that? It turns out to matter; padding messages inappropriately can also lead to security failures. I (and for that matter Needham and Schroeder) assumed that it was possible to encrypt messages so that they can’t be tampered with. That’s not easy, either. We know how to do it properly now (though even today not everyone gets it right); back in 1978, not that long after the dawn of academic cryptography, the correct way to do it was not known.

And in the real world? Let’s put it like this: the specification for TLS, the protocol used for secure web transactions, is over 100 pages long, and that’s without the seven additional RFCs describing extensions and extra features.

All of this complexity introduces danger, and it doesn’t take a 100+ page document to encounter it. That three-line protocol I presented? It’s got a security flaw; can you find it? Stare at it for a bit. I won’t blame you if you don’t see it; it took 17 years and automated assistance for the flaw to be discovered…

In 1996, Gavin Lowe published a remarkable paper. He had developed an automated protocol analyzer; when he fed it the Needham-Schroeder protocol, it found a flaw that had gone unnoticed since 1978. Eve’s goal here is to impersonate Alice, something she presumably can’t do; after all, she can’t read messages that Bob encrypts with Ka. She does this by hacking some other party with whom Alice communicates, C (Carol). (Alternatively, maybe Alice doesn’t know Eve is an attacker (though perhaps she should) and simply talks to Eve directly.) Eve then uses part of Alice’s dialog with Carol to allow her to impersonate Alice when talking with Bob. Ready? Here’s where things get complicated. (Again, if you get confused you can skip ahead to the Summary.)

We start with Alice trying to talk to Carol and sending a nonce, encrypted with Carols’ public key:

A → C: {Na,A}_Kc

Instead of replying immediately to Alice, though, Eve sends a message to Bob while pretending to be Alice:

E(A) → B: {Na,A}_Kb

(I use E(A) to mean "Eve, who is pretending to be Alice.")

Bob can’t tell the difference; all he knows is that there’s a message that claims to be from Alice. He replies to Alice—but remember that Eve has tremendous powers over the network; she can intercept that message and make sure that it never reaches Alice. So:

B → E(A): {Na,Nb}_Ka

You’d think that Eve would be stymied here, since only Alice can read that message. But she’s cleverer than that. Alice is expecting a nonce pair from Carol; Eve, pretending to be Carol, sends it to Alice as if it were really from Carol:

E(C) → A: {Na,Nb}_Ka

At this point, Alice knows Na and Nb, though she thinks that Nb is really Nc. Eve only knows Na, not Nb. But Alice, who knows nothing of the attack, is about to solve that for her by replying:

A → C: {Nb}_Kc

In other words, Alice has decrypted the message from Bob and sent it to Carol—in other words, to Eve. Eve now knows Na and Nb. She can now complete the protocol by sending Nb to Bob, again pretending to be Alice:

E(A) → B: {Nb}_Kb

I know that this is confusing. Let’s take a higher-level look at what just happened. Eve was able to trick Alice into decrypting a message for her. She could do this because Alice thought it came from Carol, whereas in reality it came from Bob. Because of this protocol flaw, the protocol doesn’t do what it’s supposed to. Eve didn’t break the encryption; she still can’t read messages encrypted to Alice or Bob. But she was able to trick Alice into doing a decryption for her. Eve is thus able to impersonate Alice when talking to Bob. If Bob (a computer, after all) is really Alice’s mail server, this means that Eve can now read all of Alice’s email. The failure was a system failure.

There’s a simple fix, though I’ll present it later. If you want to try to figure out yourself, here’s a hint: you have to prevent Alice from being fooled about whom she is talking to.

Summary

Cryptographic protocols are hard. The Needham-Schroeder protocol was actually mathematically proven correct, but the proof was flawed. (More accurately, the proof system wasn’t powerful enough to detect this sort of attack.) It allowed Eve to impersonate Alice, even though that should have been impossible.

There’s complexity all the way down. Did you look at that Kerberos protocol design dialog that I linked to? As it turns out, my very first paper on cryptography identified flaws in the detailed specifications for Kerberos. They fixed the flaws— but a fix in the code to answer one of our criticisms resulted in a different and more serious bug.

We don’t use Needham-Schroeder today; there are newer and better protocols. I present this as an illustration of how difficult the problem is. Cryptography, it turns out, is really hard. It’s hard even for experts. Trying to add new functionality to allow for exceptional access is far, far harder. Remember: the goal of the original protocol was to set up a secure session between two parties, with no one else able to read the traffic or to impersonate anyone. Our solution was only three messages long, but it was wrong and it took 17 years to find the flaw. Modern, real-world protocols are far more complex; there are very many real-world requirements that have to be met. Why should anyone have any confidence that adding yet more complexity in order to bring a third party into the conversation would be correct? I certainly wouldn’t trust it.

The Fix

The fix to the protocol is simple. Consider again that second message:

B → E(A): {Na,Nb}_Ka

This is the message that Eve forwarded to Alice, getting her to decrypt it. Bob thought he was talking to Alice; Alice thought she was hearing from Carol. Both, of course, were dealing with Eve. If that message is changed to include Bob’s name in the encryption,

B → E(A): {Na,Nb,B}_Ka

Alice won’t be fooled: she’ll see a message that’s from Bob when she was expecting one from Carol. She therefore will know that monkey business is going on and won’t complete her part of the protocol, thereby foiling the attack.