What is the Diffie-Hellman Key Exchange and How Does it Work?

What is the Diffie-Hellman Key Exchange and How Does it Work?

Diffie-Hellman is an asymmetric cryptographic method used for key exchange or key agreement. It ensures that two or more communication partners agree on a common session key that everyone can use for encryption and decryption.

By adopting the problem-solution approach, we will understand why the Diffie-Hellman key exchange is necessary and how it works!

What Is the Diffie-Hellman Exchange?

With the typical key exchange methods of modern cryptography, the secret session key must be exchanged between two communication partners during the negotiation of the encryption. Only then can both sides encrypt and decrypt the data. 

The problem with this is that the secret session key can be recorded in transit by an attacker. The session key is encrypted. But if the attacker ever gets the secret session key, then they can also decrypt the encrypted data.

The Diffie-Hellman method is unique because it is not the secret session key that is transmitted but only the result of an arithmetic operation. This arithmetic operation assumes that raising numbers to the power is easy, but calculating the discrete logarithm is difficult. As long as the necessary computing power is lacking and there is no simplification in solving the discrete logarithm problem, this method is safe.

The Diffie-Hellman key exchange was published by three scientists, Diffie, Hellman, and Merkle, in 1976. Decades later, after publication by Diffie, Hellman, and Merkle, it became known that three scientists from the British secret service GCHQ had invented the principle of this method a few years earlier. However, for reasons of secrecy, this procedure was not made public at the time. Therefore, discovering the principle used in the Diffie-Hellman-Merkle key exchange is not credited to the three scientists at GCHQ but to Diffie, Hellman, and Merkle.

The objective of Diffie-Hellman is to allow the establishment of a private key between two parties via the exchange of messages over an insecure channel.  

When establishing a key with the Diffie-Hellman method, the messages are indeed sent in the clear over the network, and anyone who intercepts the transmitted messages should not be able to deduce the generated key.

To understand the Diffie-Hellman key exchange, consider a simple problem. 

Consider two strangers, Alice and Bob, who want to exchange a message encrypted using a symmetric encryption scheme. A symmetric encryption scheme uses the same cryptographic key for both plaintext and ciphertext decryption. For this reason, Alice and Bob need to share the key for encrypting and decrypting the text.

How, then, can they agree on the key to use in a way that prevents Eve from eavesdropping on all their communications?

Characteristics of the Diffie-Hellman Key Exchange

The solution to the problem is to find two one-way functions based on a secret parameter whose composition is cumulative. This part is important because it contains the principles on which the Diffie-Hellman key exchange is based.

Let’s go through each of the terms together.

One-way functions: These are functions for which it is easy to calculate the output from the input, but it is very difficult to do the opposite process. An example of this is the use of a hash function that adds a word to a string, making the hash string unique.

To apply the function to an input, you need to know the secret parameter based on a secret parameter.

Composition: Composition of functions consists of combining two or more functions into a single function (eg: A (x) = x + 5, B (x) = x * 3, AB (x) = A (B (X)).

Cumulative: Cumulative means that the order does not change. So, A (B (x)) produces the same result as B (A (x)).

For completeness of information, the example of the functions proposed to you is not cumulative because adding 5 and multiplying by 3 produces a different result if performed in a different order.

Although unidirectional, hash functions do not generally satisfy the cumulative composition requirement.

How Does the Diffie-Hellman Key Exchange Work?

The initial proposal of Diffie and Hellman was to use modular exponentiation, an operation capable of calculating the remainder when an integer b (the base) raised to the e-th power (the exponent) is divided by a positive integer m (the form).

Therefore, the modular exponentiation c calculated on the basis b, the exponent e, and the modulo m take the form of:

c = b and mod m.

This function has the particularity of making the computation of b complex, and only the result of the modulus of m is given.

Then, taking two secret exponents a and b, we obtain as many unidirectional functions, from the cumulative composition:

  • f 1 (x) = x a mod p
  • f 2 (x) = x b mod p

To break the protocol, it would be necessary to solve the discrete logarithm problem, which requires such computational time that the Diffie-Hellman exchange protocol is currently safe.

Here, then, are the steps necessary for the application of Diffie-Hellman:

  1. Alice generates a private key a, and chooses a large prime number p and a primitive root number g modulo p (i.e., an integer g whose powers modulo n are congruent with the coprime numbers a n )
  2. Then, she calculates A = g in mod p
  3. Then, Alice sends p, g, and the value A to Bob.
  4. Bob, in turn, randomly generates a private key b.
  5. Then, he computes g ab mod p by computing A b mod p.
  6. Then, he calculates B = g b mod p.
  7. Finally, Bob sends the calculated value B back to Alice.
  8. Alice can now compute g ab mod p by computing B a mod p.

The two strangers now share a private key g ab mod p.

The image shows two columns named Alice and Bob. Each have 6 cylinders belonging to them. The first row is common paint. Adding to that is secret colors. This leads to public transport and an exchange of the colors. Then, secret colors are added again to lead to a common secret. This image is a metaphorical expression of the logic behind the Diffe-Hellman Key Exchange.
Working of the Diffe-Hellman Key Exchange

Eve, who intercepted the communications, only knows g, p, A, and B. You cannot derive the secret key a from the value A and the secret key b from the value B without solving the discrete logarithm problem mentioned earlier. Without these values, ​​it cannot calculate the shared private key.

How Effective is the Diffie-Hellman Key Exchange?

The entire key search is not the most effective attack method with the Diffie-Hellman and other discrete logarithm methods. There are algorithms for calculating the discrete logarithm. The effort is considerable but still faster than the full key search. However, that’s not a bad thing. The more significant g, x, and y are—the greater the gain in security, the more secure the method. A key length of 1,024 is considered the minimum. 2,048 bits or more is often recommended.

Another weak point is a possible man-in-the-middle attack, which can be prevented using a public key infrastructure. It is particularly fatal because the attacker can get hold of the key. The risk can be reduced if the communication partners work with different keys. If the attacker gets hold of one of the keys, he can only decrypt part of the communication.

Conclusion

Though using Diffie-Hellman alone makes you vulnerable to man-in-the-middle attacks, its efficient use along with other protocols can help you create private set intersection protocols, a technique for calculating the intersection between data while protecting the privacy of the same.