7. Diffie–Hellman–Merkle key exchange

I understood Diffie–Hellman key exchange after watching Brian Yu's video on YouTube. This article is heavily inspired from his video. If you are a video person, then I will recommend you to watch that video and then move to the next lesson. Remember, do come back and continue from the next lesson :)

This lesson contains lots of diagrams, you can click on any image to enlarge it for proper viewing experience.

In the first lesson of symmetric key encryption, we told you about a story where the Greek emperor gave his army commander the key so that the army commander could decrypt emperor's encrypted messages.

In those old times, the emperor was able to physically give the encryption key to the army commander. But with time as computer networking came along, communication between computers sitting seven oceans apart became a thing. Giving the encryption key physically was now not a solution.

Now imagine, I live in India and I want to send a confidential message to my friend living in the US. How can I share the encryption key with my friend in the US so that I can send encrypted message to his computer via the internet?

If I generate an encryption key and send it to my friend in the US, an attacker (called eavesdropper) could read the data packets and will get to know my encryption key. Now when I send confidential messages to my friend, the eavesdropper will be able to decrypt my confidential messages because he has access to the encryption key.

This problem was a pain in the ass to deal with. There was no way one could send encrypted messages over the network because the eavesdropper was able to read the encryption key. We needed a way through which two people can share their encryption key without the eavesdropper being able to read the key.

This was the problem that Diffie, Hellman and Merkle solved with their key exchange algorithm.

The Diffie–Hellman–Merkle key exchange also known as Diffie–Hellman key exchange is a mathematical algorithm that allows two people to arrive at the same key without the eavesdropper getting access to that key.

Once they have arrived at the same key, now they can use that key as their symmetric encryption key!

Intuition behind the Diffie–Hellman key exchange

The Diffie–Hellman key exchange algorithm was the first ever practical key exchange algorithm. It was one of the most fundamental discoveries in cryptography. And all of the Internet use Diffie–Hellman key exchange to this date!

Diffie–Hellman key exchange is a four step process. Let us understand the intuition behind it with a flawed implementation.

Step 1: Generate initial

We have two parties -- Mr. Ant and Mr. Bug.

Mr. Ant generates a random number, we call this number the initial number. This initial number is passed to Mr. Bug over Internet. The eavesdropper sees this number and stores it in his computer.

Step 2: Both generate their private number

Ant and Bug both generate a random number which they keep it with themselves, they don't share it. We call this number as the private number. Remember, this is not passed over Internet, they both keep this number private to themselves.

Ant has generated 10 as his private number and Bug has generated 19 as his private number.

Step 3: Ant and Bug share with each other their public number

Ant sums the initial and his private number. That is, 25 + 10 = 35. And passes it to Bug. We call this 35 as a public number because this number is shared with the other party.

Bug do the same. Bug sums the initial and his private number. That is, 25 + 19 = 44. This get passed to Ant. Here, 44 is the public number.

Both the sums -- 35 and 44 are seen by the eavesdropper. He stores these as well in his computer.

Now, comes the last step.

Step 4: arriving at the same secret key

Ant adds his private number to the value he received from Bug in the previous step, which will be 44 + 10 = 54.

Bug adds his private number to the sum he received from Ant, that comes out to be 35 + 19 = 54.

See, finally they both have arrived at the same number 54. They share a number that just they both know. Not the eavesdropper. Hence, this number 54 is called as a shared secret number. Or shared secret key. Sometimes simply referred to as just secret key.

Now if Ant wants to send an encrypted message to Bug, he can encrypt it using the shared key that is 54, and only Bug will be able to decrypt it because only Bug has access to that key not anyone else!

Before you move forward, please make sure you understand these four steps intuitively. If it didn't click, then go through the four steps just once more and I'm sure it will click!

How do they arrive at the same shared key at the end?

This is a fundamental question! Let us understand how.

If you look at the step 4 image above. You will see that Ant is doing: 44 + Ant's private [10] to arrive at the shared secret key 54.

=> 44 + Ant's private [10]

Now look at the step 3 image above. Ant received 44 from Bug in step 3. Bug calculated 44 by doing: initial [25] + Bug's private [19].

So on the Ant's side, we can expand 44 as: initial [25] + Bug's private [19]. Putting it together:

Now, similarly on the Bug's side we can expand 35 as: (initial [25] + Ant's private [10]):

If you look at the above two equations that we ended up with, you will see that we are actually doing the same calculation in both the equations, just the order in which we are adding secrets is different. And in addition order of adding numbers doesn't matter.

If you do 3 + 2 + 1 OR you do 1 + 2 + 3, result will be the same.

That's the reason behind how we arrived at the same key at the end. Isn't this a simple concept used in an astonishingly smart way?

But there's a major flaw!

There's a major flaw in the above algorithm we discussed. Let us uncover it. It will help us understand the real Diffie–Hellman algorithm.

Remember, in the first lesson, we told you about the Kerckhoffs' principle. According to Kerckhoffs' principle, it should be assumed that the cryptographic algorithm is known to everyone. A secure cryptographic algorithm is the one which remains secure even if everybody knows about its implementation.

So, the eavesdropper knows about the implementation we talked above. Let us see what happens next.

Look at the step three image above. Ant is sending initial [25] + private [10] = 35 to Bug.

Eavesdropper reads 35 as it was passed to Bug via Internet. Eavesdropper already has seen initial. According to Kerckhoffs' principle, eavesdropper knows the formula:

Now, eavesdropper has 35 and initial [25]. Can he find the private number? Ofcourse, he can easily find Ant's private number by subtracting: 35 - initial [25] = private [10].

Ant's private number is revealed to the eavesdropper! This compromises the whole security of our key exchange algorithm.

Look at the step four image above, if the eavesdropper has figured out Ant's private number and eavesdropper is already aware of 44, he can simply sum them and he will get to know the shared secret 54!

With the eavesdropper having access to the shared secret 54, he will be able to decrypt the messages and read them. And all sorts of bad things can happen!

The real Diffie–Hellman key exchange

The problem with the above implementation was that --

Look at this formula: initial [25] + private [10] = 35. The eavesdropper had access to 35 and initial [25]. So he could simply subtract and find the private number. Addition can easily be reversed by subtraction. Same with multiplication, easily reversed with division.

If we can find a way via which its extremely hard to reverse the operation when the attacker has access to all the values of the equation except the private number then we can create a secure key exchange.

Diffie and Hellman solved this using modular exponentiation: xy mod z = result.

But what does mod do?

Suppose we are doing 10 mod 3. The result will be the remainder when 10 is divided by 3. When we divide 10 by 3, we get 1 as the remainder, right? So, 1 will be result of 10 mod 3.

In programming languages, % (percent sign) is the modulo operator. If you type 10 % 3 in your DevTools console, you will get 1 as the output.

Now we have understood mod. Let us look at modular exponentiation.

For example let us take: 36 mod 520 = 209. We have 3 to the power 6, when there's power or also called exponent in the mod equation, that equation then comes in the category of modular exponentiation.

This is fascinating because even if the eavesdropper knows about: 3, 520 and 209 in our equation 3? mod 520 = 209. It's hard for him to find the correct exponent that is 6. Why?

Because he will need to brute-force the exponent, he will first try 1 then 2 then 3... and so on. There's no easy way to find the exponent.

The modulus and exponent are always very large numbers (more than 600 digits long) and they are chosen with such mathematical properties that it becomes computationally infeasible for an attacker to compute the exponent.

That's why, Diffie and Hellman made the exponent as the private number. Even if the eavesdropper knows about the base, modulus and result, its going to be practically infeasible for the eavesdropper to find the exponent which is going to be the private numbers of Ant and Bug.

For our learning purposes, we will be using very small numbers. But you know it's not like this in the real world ;)

In the actual Diffie–Hellman key exchange, the intuition will remain the same as the flawed one. In the actual algorithm, instead of playing with addition, we will be playing with modular exponentiation.

The real Diffie–Hellman key exchange

Step 1: Ant and Bug agrees on base and modulus

Ant and Bug talk to each other via the Internet and they both agree on the same base and modulus. Eavesdropper sees these values.

Step 2: Both generate their private number

Ant and Bug generate their respective private numbers. Eavesdropper can't see these private numbers.

Step 3: Ant and Bug share with each other their public number

Ant calculates (baseant's private number mod modulus). It comes out to be: 28 mod 19 = 9. The result 9 (public number) gets sent to Bug.

Similarly, Bug calculates (basebug's private number mod modulus). It equals to 215 mod 19 = 12 and then Bug sends 12 (public number) to Ant.

Step 4: arriving at the shared secret key

Ant in the previous step received 12 from Bug. In this last step, the received 12 becomes the base: (BaseAnt's private number mod modulus), it equates to: 128 mod 19 = 11.

Similarly, Bug uses 9 as the base that he received from Ant in the previous step. His calculation comes out to be: 915 mod 19 = 11.

They both have finally arrived at the same number that is their shared secret key! 🙌

How does this work?

The intuition is exact same as we saw in our flawed implementation. So, this time I will go a bit fast with the explanation. I will expect from you to scroll up to look at the step 3 image and step 4 image as you read the explanation.

On the Ant's side, we had 128 mod 19 = 11 as the final equation in the step 4:

Now let us expand 12 that we received from Bug in the step 3.

On the Bug's side, we had 915 mod 19 = 11 as the final equation in the step 4:

Now let us expand 9 that we received from Ant in the step 3.

Both the equations are essentially the same equation when modular arithmetic properties are applied.

According to modular arithmetic properties:

Now, let us apply the above property to both the equations.

See, both the equations are exact same! This is how they both arrive at the same secret key without the eavesdropper ever knowing about it.

As we already know, this shared secret key can be used as an encryption key to prevent eavesdropper from making sense of the messages.

That's the power of the Diffie–Hellman key exchange guys!

Credits

Below are some resources I used to tighten my understanding. You don't need to consume these. If you have read this article or watched Brian's video, you already understand this topic well enough.

• Art of the Problem's YT video.
• Computerphile video.
• Again, a computerphile video.
• The old gold, Wikipedia article.

I have worked hard to create this course. If you are getting some learnings from it, you should follow me on Twitter: twitter.com/vkwebdev. I try to be useful there :)