How messages can be encrypted without sharing an encryption key in advance
The primary method of exchanging keys online used today
Eavesdropping communications through the internet can be done at many points: the Wi-Fi hotspot you’re directly connected to, your internet service provider, the server hosting the web pages you visit, national gateways, and the vast array of routers and switches in between.
Without encryption, all these communications would be readable by an eavesdropper, be that a stalker, a hacker, or a government agency. But in order to encrypt your communications, you need to agree on a key with the party you are communicating with. If you are visiting a website, how do you safely exchange a key with the server that hosts the website? We need a method for two parties (e.g., two people, a person and a server, or two servers) to efficiently agree on a key without meeting and while only being able to communicate over insecure channels, such as the internet.
A Physical Example: Exchanging a Message without Exchanging a Key
First consider a physical example, illustrated below. Suppose Assata wants to send Bobby a package. She puts it in a strong box with a large clasp that can take multiple locks (1). She puts a lock on the box, but Bobby doesn’t have a key to the lock. Assata mails the box to Bobby, who cannot open it (and neither can anyone else while the box is in transit). Bobby puts his own lock on the box (2), a lock that Assata doesn’t have the key to. When Assata receives the box, she removes her lock and sends the box back to Bobby (3). Now Bobby can open the box because it is only secured with his lock (4). The box cannot be opened in transit—an eavesdropper would have to break Assata’s lock, Bobby’s lock, or both.
Exchanging a secure message without sharing a key
This illustrates that it is possible to send something securely without meeting first to exchange (agree on) a key. However, we aren’t about to start physically mailing lockboxes in order to exchange encryption keys. What we need is a mathematical version of this that we can use for digital communications.
A Mathematical Example: Exchanging a Message without Exchanging a Key
Let’s see how we would do this without physical boxes and locks. Suppose you have an encryption protocol where you can encrypt any text (as we always expect), that you can apply multiple times for layers of encryption (as we also always expect), and that you can encrypt and decrypt the layers in any order you wish and end up with the same result. A mathematical operation satisfying this last property is said to be commutative. (All the encryption protocols we describe in the chapter “What Is Encryption?” are commutative.) Let’s see this with an example, using the Vigenère cipher.
Assata encrypts the message
AT ONE TIME IN THE WORLD THERE WERE WOODS THAT NO ONE OWNED
with a Vigenère cipher and key ALDO to get the ciphertext
and sends the result to Bobby. Bobby doesn’t have the key! But Bobby encrypts this ciphertext with a Vigenère cipher and key LEOPOLD to get the doubly encrypted text
LI FQS POLI HF VSS KGFLU SKAYG LDFV HDFGG PNZX MG QYS COBEU
and sends the result back to Assata. Assata “decrypts” the message from Bobby with her key (ALDO) to get (the still encrypted message)
and sends the result to Bobby. Finally, Bobby decrypts this with his key (LEOPOLD) and gets the message that Assata wanted to send Bobby in the first place:
AT ONE TIME IN THE WORLD THERE WERE WOODS THAT NO ONE OWNED
Note that, in this example, Assata did not share her key (ALDO) with anyone, and Bobby did not share his key (LEOPOLD) with anyone either. Because the Vigenère cipher is commutative, it did not matter that the message was encrypted with Assata’s key, then encrypted with Bobby’s key, then decrypted with Assata’s key, and finally decrypted with Bobby’s key. All that matters is that the message was encrypted and decrypted once with each key. Any eavesdropper would only see one of the three intermediate ciphertexts.
A Physical Example: Agreeing on a Secret over an Insecure Channel
In modern cryptographic systems, rather than sending the entire message back and forth with different layers in this way, one has an initial exchange, much like in the above examples, to settle on a key to use for the intended communication. You could imagine that Assata, rather than sending the message AT ONE TIME IN THE WORLD . . . , sent an encryption key to use for a longer communication. We will describe the mathematical basis for key exchange as it is used by almost all modern communication, called the Diffie-Hellman key exchange.
First, let’s see how this is done with paints instead of mathematics (illustrated below). We will assume that if you mix two colors of paint together, you can’t unmix them; specifically, even if you know what one of the two colors was, you can’t figure out what color was mixed with it to get the resulting mixed color.
Crafting a shared secret, in paints
Assata and Bobby start by agreeing on one paint color (in this example, yellow) and an amount, say 10 mL (1). They can do this over an insecure communication channel and should assume that an eavesdropper will know what the color and amount are too. Then Assata picks a color (in this case, rusty orange) and keeps it secret (2). She mixes 10 mL of yellow with 10 mL of rusty orange to get a coralish color (3). She sends this to Bobby over the insecure channel, understanding that an eavesdropper will see it. Bobby does the same thing, with his own secret color (4).
Now to the paint sample received from Bobby (5): Assata mixes in 10 mL of her secret color (6), resulting in a dark purple (7). Bobby does the same thing. Assata’s unpleasant brown–dark purple is obtained from a mix of 10 mL each of yellow, her secret color, and Bobby’s secret color. Bobby’s resulting paint mix is obtained from a mix of 10 mL of yellow, his secret color, and Assata’s secret color. So Bobby also ends up with the same unpleasant brown–dark purple (8)! Can the eavesdropper create the dark purple? The eavesdropper sees yellow (1), the mix of yellow and Assata’s secret color (3), and the mix of yellow and Bobby’s secret color (5). But to create the unpleasant brown, the eavesdropper would have to unmix in order to obtain Assata’s or Bobby’s secret colors, which they can’t do.
Diffie-Hellman Key Exchange
Let’s revisit this process mathematically. We do so with a commutative mathematical operation that is hard or impossible to reverse. A mathematical operation or function that is hard to reverse is called a one-way function. Let’s represent our mathematical operation with the symbol ☆—that is, a ☆ b = c for some numbers a, b, and c. Commutative means that a ☆ b = b ☆ a. That ☆ is one way means that if you know b and c, you cannot easily figure out what a is. In practice, one should only be able to figure out what a is by a brute-force (or close to brute-force) attack: by trying every possibility for a. You may think of ☆ as the multiplication sign (which is commutative but is not one way). (For those mathematically inclined, ☆ can be modular exponentiation for real implementations of Diffie-Hellman.)
Illustrated below, Assata and Bobby agree on a number p, which is public (1). Assata chooses a secret number a (2), computes p ☆ a (3), and sends the result to Bobby. Since ☆ is one way, an eavesdropper will know p and p ☆ a but will not be able to (easily) determine a. Bobby chooses a secret number b (4), computes p ☆ b, and sends the result to Assata (5). An eavesdropper knows p ☆ b but not b. Assata computes (p ☆ b) ☆ a (7), using the message from Bobby (5) and her own secret number (6). Bobby computes (p ☆ a) ☆ b (8), using the message from Assata (3) and his own secret number (4). Since ☆ is commutative, (p ☆ b) ☆ a = (p ☆ a) ☆ b, and so Assata and Bobby now have computed a common number. Since the eavesdropper only knows p ☆ a, p ☆ b, and p, and since ☆ is one way, the eavesdropper has no efficient means of computing Assata and Bobby’s shared common number: it is secret to Assata and Bobby. Assata and Bobby can use this shared number as their cryptographic key.
Agreeing on a secret key
Using Diffie-Hellman Key Exchange
Diffie-Hellman key exchange is used all over the place as a means of agreeing on a cryptographic key. It is used as the basis for most forms of encrypted communications that you will encounter. Most notably, it forms the basis of key exchange when you connect to a website via https. When you visit a website, the URL will either start with http:// or https://. In the former case, none of your communications with the server of the website are encrypted. In the latter, communications are encrypted, and the key used to encrypt those communications is generated using Diffie-Hellman key exchange.
In Context: When Good Things Go Bad
Remember that the first thing that Assata and Bobby do is agree on a number p that forms the basis of their key exchange. This number is public, but we assumed that our mathematical operation ☆ was one way, so it was OK for p to be public. However, someone with a lot of computational resources (such as a wealthy nation-state) can invert the operation ☆ (for functions such as modular exponentiation used for ☆ in the real world) using two phases. The first phase takes a very long time and must be done for a specific value of p. The second phase can be done very quickly (in real time) for the same value of p, assuming that the first phase has been completed. This means that everyone should not be using the same value p but should be using different values of p and changing them often.
However, in 2015, researchers showed that 18 percent of the top one million https domains use the same value of p. Two other communication protocols that depend on Diffie-Hellman key exchange are SSH (secure shell) and VPN (virtual private network). The same researchers showed that 26 percent of SSH servers and 66 percent of VPN servers used the same value of p in their Diffie-Hellman key exchange. This means that a powerful adversary would have little trouble breaking the encryption.
While the Diffie-Hellman protocol is strong and reliable, this highlights that those who implement the protocols need to do so with care to ensure that they are in fact secure.
External Resources
Adrian, David, Karthikeyan Bhargavan, Zakir Durumeric, Pierrick Gaudry, Matthew Green, J. Alex Halderman, Nadia Heninger, et al. “Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice.” In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, 5–17. Denver: ACM, 2015.
