Dog Fur Donuts

Part I of the series Diffie-Hellman key exchange.
May 11, 2015

Perfectly Secure

“I have it!”, Alice yells out to anyone who can hear her. Donuts are stacked precariously around her, gleaming in the fluorescents of her parents’ kitchen. She feels like a giant in a confectionery skyline. Which is what she wants, really. Her donut stand is about to pay for a new TV for the living room, entitling her to watch an entire season of House of Cards. Dad had promised.

Alice holds her wooden spoon aloft, victorious. She’s just created the most delicious donut her neighborhood will ever taste. But first, she’s got to check with her best friend, Bob, who really knows donuts…

The spoon lowers as she remembers Bob’s sister, Eve, a teenage brat who steals all of Alice’s recipes and posts them on a recipe site, where they are Five Starred and accrue glowing comments1. Alice has tried to use codewords for ingredients, or writing in really tiny letters, but somehow the recipes keep popping up online, just a few hours after Alice sends the recipe to Bob.

No way it’s happening to this recipe, Alice thinks. She needs a secure way to send her recipe to Bob, so that even if Eve intercepts everything Alice sends, Eve won’t be able to make any sense of it.

Alice brings up Google and slowly types her search query: perfect encryption.

A short aside on one-time pads

A one-time pad provides perfect security. It’s the only known encryption method that has an information-theoretic guarantee of unbreakability.

To perform one-time pad encryption, we need a plaintext (the message we want to encrypt), and a random key that’s at least as long as the plaintext. We then combine the key with the plaintext using modular addition2 to produce a ciphertext, which we send to a recipient. The recipient must have a copy of the key, which they’ll use to reverse the encryption and obtain the plaintext.

We use modular addition in one-time pad encryption because it produces ciphertexts that have the same randomness as the key used to generate it. We call this property of modular addition randomness preserving3. If you produce an -bit ciphertext with a randomness preserving one-time pad function, and then give the ciphertext to someone who doesn’t know the key, to them, it’ll look equally likely to have been generated from any -bit string. The ciphertext dazfdooefldgsk could be encoding password123456 or bbbbbbbbbbbbbb or strike at dawn or any other possible permutation of 14 characters, and it’s provably impossible to distinguish between these possibilities without knowing the key.

Dog Fur Donuts

“Tails.”

Alice is four pages into generating her random one-time pad, and she’s feeling pretty smug as she imagines Eve trying to decode her recipe, trying key after key, growing older and more withered, until finally Eve hits a donut recipe, but it turns out to be the recipe for, say, Smelly Sock and Dog Fur Donuts, a definite un-Five-Star-Worthy recipe that will garner a few amused comments, at best.

“Tails.”

“Wait a minute…”

Alice stops writing down the coin flips, staring at the four pages of HHHTTTHTHTTTHTHTHHTHTHTHTHTHTTHTH she had neatly inscribed.

If Eve has managed to intercept every recipe she’s sent to Bob, what’s to stop her from intercepting this key too? If Eve has the key, Alice may as well post the recipe online herself, for all the good the encryption is going to do.

Maybe- maybe she could encrypt the key before she sends it, but then of course she’d need to send Bob another key to decrypt the first key, and her recipe would be posted online before the first batch came out of the deep fryer.

Alice puts away the coins, carefully stacks up the pages, and begins to think.

Perfectly useless

Despite its perfect security, the classic one-time pad is exquisitely impractical. A one-time pad key can never be reused4, because key reuse makes ciphertexts vulnerable to standard cryptanalysis, nullifying their pefect security guarantee. This means we need to securely send an -bit key to securely send an -bit message. If the key is intercepted, the ciphertext can be trivally decrypted- thus, the security of the one-time pad is equivalent to the security of the method used to transmit the key! If the transmission method isn’t secure, the one-time pad isn’t secure either, and if the method is secure, why not just use that method to transmit the plaintext itself? It seems like one-time pad encryption just passes the cryptocurrency-denominated buck to the key transmission method.

Fortunately, Diffie-Hellman is a smarter type of key transmission, one that’s eager to accept said buck, and allows us to solve the key transmission problem without actually transmitting the key proper.

The Idea

Using a one-time pad doesn’t require Bob to have Alice’s key- they just need the same key, and it was this realisation that led Alice to her Idea. Sure, the Idea was incomplete and quite possibly a waste of time, but hey, she’d just spent two hours flipping some coins.

Alice’s reasoning went like this: Eve seemed like she could intercept everything Alice sent Bob. But what if Alice and Bob each had a private secret, that they would never send to each other. All the five-stars in the world wouldn’t let Eve intercept what they don’t send.

They could then send something to each other that they could each combine with their private secret, and somehow5 they would arrive at the same key, without ever having sent that key to each other. Alice grabbed a piece of paper and started sketching out the Idea:

Then, at the very bottom, Alice writes:

What could that serve as that operation, , that would allow that equation to be satisfied? What kind of data was and and and , and how did they relate? There were so many gaps in the scheme, but at least Alice felt like she was making progress. And she had a friend who might be able to help her.

Diffie-Hellman

Alice has unwittingly sketched out a skeletal framework for Diffie-Hellman key exchange. Here’s how it should work:

1. Alice and Bob each choose a private key, which they never tell anyone.
2. Alice and Bob each calculate a public key from their private key.
3. Alice and Bob exchange their public keys. It doesn’t matter if anyone intercepts the public keys- they’re public, after all.
4. Alice and Bob each combine their own private key with their counterpart’s public key, to arrive at a shared key.
5. Through the magic of Diffie-Hellman, they calculate exactly the same shared key!

Yvonne

Alice decides to visit her friend, Yvonne, who has this habit of getting full marks in every math test, and yet somehow managing to seem modest about the way she did not, in fact, have to try at all, what with math coming as naturally to her as walking did to Alice.

Alice explains the Idea to Yvonee, who looks at Alice’s equation, and tells her that it’s all quite simple really, you just need to use integer addition6 and the Idea will work.

So the Idea works! Alice wants to try it out right away, so they begin to work out the details.

For their secret, Yvonne explains, they should each pick a random number between 1 and 100. They keep this number a secret. It’s their private key. But they can calculate their public key if they each add the same arbitrary number- the group parameter- to their private key. Yvonne picks 23, because she likes that number. They eventually sketch this out:

This is great- they’ve arrived at a shared key- 109- without ever sending their private keys over the wire! If Eve wanted to decrypt their transmissions, Yvonne explains, Eve would need to solve the addition inverse problem, also known as subtraction, to recover the private keys, and thereby calculate the shared key.

“But…” Alice is unsure if she’s being stupid.

“But what?”

“Isn’t subtraction… really easy? I mean, even I could do it in first grade, and I’m not a Certified Math Genius like you.”

Symmetry Breaking

Alice is right: the addition inverse problem isn’t very difficult. When Alice tells Bob that the group parameter is 23, Eve will just intercept it, along with Alice’s public key, and then she can just calculate Alice’s private key by computing 75 - 23 = 52.
They could try to make the addition inverse problem more difficult by picking really large numbers, but then it would take as much effort to encrypt the message as Eve would take to calculate the private key from the public key and group parameter.
Using integer addition really does let us reach a shared key, however, so it’s probably worthwhile figuring out why it works, before we try to beef up the security.

The capital letters are the public keys, and the lowercase letters are the private keys. We generate public keys from private keys by combining them with the group parameter7. Let’s substitute this into :

Yvonne knew that integer addition would work here. If we write:

…we can see that’s obviously true. But what properties of addition let it substitute for ? Put another way, what’s the minimum we can assume about to ensure that holds?

Let’s start with associativity8. If we assume that is associative, we can drop the brackets from , and we get:

Look at that! Now the only difference between the two sides is the order of the terms. If we assume that is commutative9, we can rearrange the order of the terms however we like:

…and that’s obviously true.

Now we know that if we have an operation that’s commutative and associative, it can be successfully used in Alice’s scheme to arrive at a shared key. Integer addition has those two properties, but it’s about as computationally intensive to add as it is to subtract. This means that breaking a message’s encryption would take around the same amount of time as encrypting the message in the first place!

What Alice is really looking for is an operation that has three properties: commutativity, associativity, and computational asymmetry. Of course, Yvonne already knows all this, and has another idea for what to use as the operator.

Another Operation

“So… Eve knows how to do subtraction,” Yvonne says, sounding slightly surprised.

Alice isn’t sure whether she has a particularly low opinion of Eve, or just a really poorly calibrated sense of other people’s abilities. She doesn’t ask.

“Is there another operation we can use, apart from integer addition? Something that we can easily calculate, but isn’t so easy to reverse?”

Yvonne thinks for a while.

“Commutativity, associativity, and computational asymmetry,” she says.

Alice knows Yvonne is thinking aloud, so she just waits.

“Modular exponentiation10,” Yvonne finally says.

Alice grabs some paper and they start working through the protocol again.

It works! Alice is worried that Yvonne is underestimating Eve’s abilities again, though.

“Couldn’t Eve just solve for in , and work out my private key?”

The Problem

As it turns out, the in , is known as the discrete logarithm. Calculating , given and , is the best known way to defeat Diffie-Hellman. Fortunately, there’s no known polynomial-time algorithm for calculating discrete logarithms- finding such an algorithm is known as the discrete logarithm problem, and it’s an unsolved problem in computer science.

Some people suspect that efficient non-quantum11 algorithms exist, but until or unless one is discovered, Alice can simply pick a key size that is far too large to be brute-forced, and Eve will never get her hands on that donut recipe.

1. Amazing donuts! I used to get these from a little donut stand down the road, but now I’ll never return! Five Stars!

2. XOR can be thought of as a special case of modular addition.

3. An easy way to get an intuition for why modular addition is randomness preserving is to imagine that I’ve got two numbers between one and ten, and , where is a number I’ve picked, and is a random number. I then calculate and tell you that . An unfortunate attacker who wants to know will find that for every possible value of , there’s a value that will give . If , for instance: when . If : when , and so on. Because is random, we have no reason to suppose that is any particular integer between one and ten, and thus knowing only gives us no information about what is. We can repeat this entire process for as many numbers as we like, allowing us to “transfer” randomness between two arbitrary strings of identical size. We’ve built up a cryptographic system from known primitives in a mathematically sound way- something that’s a recurring motif in cryptography.

4. This non-reusability of keys is why it’s called one-time pad encryption, incidentally.

5. This was a big somehow.

6. Technically, Diffie-Hellman only usefully generalizes to finite cyclic groups, and so integer addition, an infinite cyclic group, won’t be very useful. From a pedagogical point of view, however, it’s easier to motivate a computationally asymmetric commutative operation if we have already attained an intuition for the usefulness of commutative/associative operations to key exchange via insecure channels.

7. We combine a private key, , with the group parameter, , to get a public key, , like this: .

8. A binary operator is said to be associative when , that is, the order in which you perform the operations does not change the result.

9. A binary operator is said to be commutative when , that is, the order of the operands does not change the result.

10. Modular exponentiation is indeed commutative, associative, and computationally asymmetric. It’s even more computationally asymmetric than it might seem at first, because there are far more efficient algorithms for performing modular exponentiation than the naive repeated-multiplication-and-take-the-remainder approach.

11. There’s already an efficient quantum algorithm that can calculate discrete logarithms in polynomial time.