Diffie-Hellman Key Exchange: How Does it Work?

If you want to send secure communication back and forth with someone else, you'll each need a key to encrypt and decrypt that communication. The challenge with that lies in communicating what that key is without anyone finding out. It's quite the catch-22 as you can't exchange any communication securely without that key, yet you can't exchange that key because you don't have a secure communication method. What are you to do?

Well, one way to exchange keys securely without previously having a shared secret is the Diffie-Hellman key exchange. What is Diffie-Hellman? In fact, you're making use of it right now by visiting this web page. The Diffie-Hellman key exchange is a crucial component in securing internet traffic. Let's look at how exactly it works.

A Paint Mixing Analogy

We'll begin by looking at this key exchange abstractly before discussing how it works mathematically. For now, just imagine two people (Alice and Bob) who'd like to have a shared secret key.

Let's imagine this shared secret key is a specific color of paint. They want to create this paint color secretly. How can they do that?

Alice and Bob both have access to some paint that anyone can access. For this example, it's yellow. They both take that yellow paint back to their rooms and add a color that only they know. For Alice, it's a specific shade of red, and for Bob, it's a specific shade of blue.

As a result, Alice now has a specific shade of orange that can only be made with her secret shade of red, and Bob now has a specific shade of green that can only be made with his secret shade of blue.

They leave their rooms and exchange their new mixes. This is done in public, but that's okay because someone won't be able to determine what exact shades were combined with the yellow to get these new colors. If you were perplexed why this cryptography metaphor uses paints, it's for this reason; a crucial part of the Diffie-Hellman key exchange is the difficulty in extracting the secret values, much like how it is difficult to determine what exact shade was mixed into paint.

Now, Alice has Bob's green paint and Bob has Alice's orange paint. They then add their secret shades to the other's paint. As a result, they each get the same shade of... most likely some type of brown. But a specific, non-reproducible shade of brown! Nobody else could have produced the same color, even if they had the same yellow paint they started with or even if they managed to grab some of the green or orange paint when Alice and Bob exchanged them in public.

Is this quite the simplification of a precise mathematical method? You betcha. But hopefully it helps you understand the main gist of what the Diffie-Hellman key exchange can accomplish. With this, you can exchange a shared secret key with another person without exposing it publicly, and thus prevent others from stealing that shared secret.

Calculating Numbers: An Explanation

Of course, your browser and a website's server aren't exchanging buckets of paint. They're going through a similar process using math, instead. We'll be looking at a simple implementation of Diffie-Hellman by looking at how two parties, Alice and Bob, can use it to establish a shared secret key.

Before we do that, however, it's important to understand the concept of [modular arithmetic]. What happens when you divide a number by something other than one of its multiples? Well, it doesn't divide evenly. Modular arithmetic isn't concerned with how many times a number can be divided by another, it only deals with the remainder that doesn't divide evenly. For example,

5 mod 2 = 1,

because 5 divided by 2 equals 4 with a remainder of 1. Why does Diffie-Hellman use modular arithmetic? Well, because it's incredibly hard to undo, much like unmixing paint.

Diffie-Hellman starts off with a combination of public and private components. There are the public components g and n where:

• g is a small prime number (specifically, a primitive root modulo)
• n is a large prime number.

Then Alice and Bob both have a private component where:

• a is an integer less than n only known to Alice
• b is an integer less than n only known to Bob

These are all the components needed to begin the key-exchange.

First, both are going to apply modular arithmetic in combination with g and their private component (either a or b), and then send it to the other. These are their public keys

• Alice sends Bob: A_public = g^a mod n
• Bob sends Alice: B_public = g^b mod n

They're public because these are being sent insecurely (as they have yet to establish an encrypted channel). That's okay though because it's incredibly hard to work out what the private values a and b are, because of how difficult modular arithmetic is to undo.

The difficulty of figuring out a and b from A_public and B_public is dependent on the size of n. The values of A_public and B_public can be anything between 0 and n-1, so the larger n is, the more secure a and b are.

Now that Alice and Bob have each other's public key, what can they do? They can use modular arithmetic again, first raising the other's public key to the power of their own private value, and then finding the remainder when divided by n:

• Alice calculates B_public^a mod n
• Bob calculates A_public^b mod n

What's great about this is that Alice's calculated value is equal to Bob's! Just like that, they now have a shared secret that nobody can calculate with their private keys. This is their shared secret key. These keys can then be used to securely exchange the more-efficient symmetric keys for encrypted communication.

Diffie-Hellman's Place in Today’s Encryption

We've discussed how Diffie-Hellman is used to securely exchange keys, but when does that actually happen on today's web? Well, Diffie-Hellman is a crucial part of the most widely used internet communication encryption protocol: TLS.

You may have heard of TLS and its handshake, but let's give a brief overview: Back in the wild west of the internet, aka the ’90s, most internet communication was not encrypted. For obvious reasons, that became an issue when people's private information, such as banking info, began to be sent across the internet. TLS was created to ensure data between a user and a web server was encrypted. Its implementation is represented by an appended 's' to HTTP, resulting in the common HTTPS we see in most websites today. This, and the padlock most browsers show alongside it, is how we assume our traffic is safe. But what exactly does that mean? (Hint: it involves using a Diffie-Hellman key exchange)

Let's look at a website using TLS 1.2. By investigating the site's security information, you'll see something like this:

(TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384, 256 bit keys, TLS 1.2)

This mashup of letters is the cipher suite, or the specific set of algorithms TLS is using to secure communication. We're only going to focus on a specific section: "ECDHE" Here, "ECDHE" is specifying the key exchange protocol used to exchange keys. In this case, you can explicitly see that the key exchange used is an Ephemeral Diffie-Hellman! If you're wondering what the ephemeral aspect entails, that just means a new key pair is generated for every exchange.

Nowadays, some websites you look at, including Ockam's, won't list Diffie-Hellman in the cipher suite:

(TLS_AES_256_GCM_SHA384, 256 bit keys, TLS 1.3)

Why's that? Well, it's not because Diffie-Hellman can't be secured; far from it. Many websites now use TLS 1.3, which is more secure than TLS 1.2 because it removed some insecure parameters as options. One of the most notable improvements was removing the option to use RSA as the key exchange. This is because TLS 1.3 only accepts Diffie-Hellman as the key exchange, so there's no point in specifying it in the cipher suite! TLS 1.3 also takes a step to make sure the Diffie-Hellman key exchange is secure by requiring a sufficiently large n.

So what does that all add up to? A secure web experience for today's internet users. The peace of mind you have when entering your bank information on a website is thanks to TLS, and the Diffie-Hellman key exchange is one part of what makes TLS so secure.

It's nice that your browser's traffic is encrypted like that, right? Of course, nowadays, you don't access the internet only through a computer browser. No, this is the IoT age, and it's crucial that all those devices can also keep your data secure. That's why Ockam is working to make it easier to implement encryption for IoT devices. If you're curious about how Ockam is doing that, be sure to check out our website.