Diffie-Hellman, Explained

Even people who haven’t gotten too deep into cryptography have likely heard of “Diffie–Hellman.”  For reasons I won’t try to explain, understanding the Diffie-Hellman key exchange always eluded me, even after watching a great presentation on it at Strange Loop a few years back.

Then, while reading The Code Book by Simon Singh, everything suddenly clicked!  But… they say you don’t fully understand something until you’ve tried to teach it, so here it goes.

Wikipedia says:

Diffie–Hellman key exchange is a method of securely exchanging cryptographic keys over a public channel.

The Problem

First, why do we care about this?  Why would we want to exchange cryptographic keys (securely, but also over a public channel)?

Cryptography has existed for hundreds of years, allowing secrets to be passed to and from people, businesses, groups and governments.  The recipe was always pretty much the same:  the message (“plaintext”) is turned into an indecipherable “ciphertext” by means of putting the plaintext and a key through a known algorithm.  That same algorithm and key could turn the ciphertext back into plaintext for the recipient.

Algorithm(plaintext + key) –> ciphertext

A known algorithm doesn’t sound very secret, right?  The algorithm is the process that we’re putting the plaintext through.  The key is the secret sauce–and it needs to stay secret.

Back in the days of olde, you would have a physical copy of the key (which is, in cryptography, not a physical metal key but some kind of phrase, text, long string of numbers, etc.) sent to the person you want to securely communicate with.  Depending on how important you were (and how many people wanted your secrets), this might necessitate in-person meetings, which is time and money you’d rather spend doing something else.

Back in the 1970s, Data Encryption Standard (DES) started catching on–businesses could now secretly communicate.  The downside was that they had to ship copies of the keys to all involved parties, which is expensive (even before postage was 42 cents per envelope).  And what if your mail delivery person wasn’t trustworthy?

And imagine if one of your keys was compromised… if you wanted to keep talking to the recipient, you’d have to go through the key exchange all over again.  Eeeesh.

Thus, the problem that the Diffie-Hellman key changed solved was the same problem that cryptography had always had:  why is it so difficult and expensive to exchange keys?

There has to be a better way!

The Players

Whitfield Diffie and Martin Hellman are American cryptographers best known for, well, this concept (public key cryptography).

There was a third cryptologist, Ralph Merkle, who contributed to the idea but is frequently (almost always?) left un-mentioned.  He’s also known for Merkle trees.

What we’re looking for

So, we want an easy and inexpensive way to share cryptographic keys. Additionally, we’re not going to give up on the level of secrecy that physical delivery would offer us.  If our keys aren’t secret, then neither are our messages.

Physical delivery of keys is unrealistic (and it doesn’t scale!), so we want something digital.  Unfortunately, the internet is a very public place, so we’re going to have to make this exchange with other people listening… yet somehow (mathematically) be unable to steal our keys.

A metaphor might help

Imagine that Alice wants to send a message to Bob through the post office.  She knows that Eve (who is a woman, and thus of course jealous of Alice /s) might try to intercept and read her message… so she gets a metal box and puts her message inside, then puts a padlock on it.  Ain’t no one getting past that without the key (let’s ignore lockpicking for a minute… come on guys, this is a metaphor).

Then, she sends it to Bob.  Bob doesn’t have the key to her padlock… so what’s a guy to do?  Add another padlock.  Boom, two padlocks.  He ships it back to Alice.

Are we at an impasse here?  It sounds like we have a lot of padlocks and no actual communication.  And so far, you’d be correct.

Alice unlocks her padlock, so the metal box only has one padlock on it (Bob’s).  Unfortunately, Alice can’t open the box, but she doesn’t need to… she wrote the message in the first place.  She ships the box to Bob.

Bob receives the box and it has one (1) padlock on it… and it’s his!  He has the key, so he unlocks the remaining padlock, and he can finally read the message!  Woo!

It looks like we found a solution, if only a metaphorical one.  Now we just need to do that… but with computers.

But holy shit, that was a lot of work for ONE message.  While in real life, shipping a metal box 3 times per message is costly and time consuming and ridiculous, it isn’t a problem for computers.

But first, some math

Math has the concept of two-way functions, and one-way functions.  Two way functions are easily reversible, like A + B = C.  Knowing A and C, you can easily deduce the value of B.

One-way functions, however, are not easily reversible.  Not at all.  One such example is modulo.  You probably know this operator as “%” or “remainder”.  It might bring back memories of introductory C courses (as it does for me).  11%2 = 1, but I can’t easily see a way to take 1 and 2 to get back to 11.  Plus, there are other equations that would give me the same answer, e.g. 13%2 also equals 1.

How it works

Alice and Bob will each choose a number.  Alice’s number will be represented as A and Bob’s number will be represented as B.  Neither one tell each other their number (it’s a secret!).

They each choose a base (g) and a modulus (p).  These can be shared publicly without hurting our secrecy goals.  Alice and Bob call each other on an unsecured line and pick two numbers.**

Now Alice takes her values for A, g and p and puts them into this equation:

Alice writes down the value “3”, which we’ll call α.

Bob does the same thing with a similar equation:

Bob writes down the value “5”, which we’ll call β.

Alice sends Bob the value of α (3), Bob sends Alice the value of β (5).

Alice plugs this new value into an equation:

Bob does something similar:

They both got 3!  This is their shared key, which they generated in plain sight of Eve.

But that seems trivially easy

Well, yeah.  For the sake of example, the numbers (A, B, g, p and the resulting key) were very small. 

p needs to be prime, and g needs to be ‘primitive root modulo p’.

A, B and p need to be much larger (g can be small, though).

Are you sure that Eve doesn’t know the secret key?

Pretty sure, yeah.

Alice and Bob never shared A and B over the phone.  Eve could know p and g, which isn’t enough to get either of the first equations solved:

But she could eavesdrop and learn about α and β, right?  Since Diffie-Hellman is widely known (you’re reading about it right now…), she knows the equations.

If she successfully eavesdropped on everything we did and she knows g = 5, p = 11, α = 3,  β = 5…

Can you solve for A and B?  A = 2 correctly solves the equation (and it’s Alice’s number), but A = 22 solves it too.  Same thing for B.  B = 6 and B = 31 both solve our equation (along with tons of other seemingly correct solutions).

Well, if she can’t find A and B, what about the key?  Can she deduce that?  No, because she needs A and B to determine the key:

She could plug in values for A and B but she’s in the same boat as before.  There are tons of values of A and B that seemingly solve the equation, but only one set is correct… and those two numbers are the only ones that Eve couldn’t know.  Womp womp.

Hats off to the discrete logarithm problem.

Okay, but what about like, NSA Eve?

Difficult to say.  If your values aren’t sufficiently large, or were generated by something that isn’t really random, and/or you don’t guard against a man-in-the-middle attack (where another person could set up key exchanges between themselves and Alice, and themselves and Bob), your communication is much less secure.  It’s recommended that prime number p be at least a 2048-bit number, as smaller numbers have been shown to be vulnerable to unwanted decryption.

The paint example

The Diffie-Hellman exchange is often explained in terms of paint mixing.  Similar to Alice and Bob picking their private keys A and B, each picks a secret color.  They agree on a “starting” color too, analogous to p and g.

Alice mixes the starting color (yellow) with her secret color (red).  Bob mixes the starting color (yellow) with his secret color (blue).  Alice gets a orange and Bob gets green.

Then they exchange the two colors (much like α and β).  Finally, they mix their secret color with the shared color, so Alice mixes red with Bob’s green and Bob mixes orange with blue.

I’m not an art major, but the final result is that they each have a color mixture that is the same (some kind of brown-ish color).  This is the shared key.

Just like the modulo equations, it’d be very difficult for Eve to piece together what the “final” (brown) color was based on the publicly shared colors of yellow, orange and green.

TL;DR

Prime numbers are magical, and so is math.  😀