Diffie-Hellman Key Agreement

Introduction

Hello Reader!! 

We already know the importance of a safe and robust key exchange technique in cryptography. We will learn about one such technique called Diffie-Hellman Key Agreement.

The Diffie-Hellman key exchange is one of the greatest developments in public-key cryptography and is still widely used in a variety of modern security protocols.

In this article, we'll understand what it's used for, how it works step by step, its multiple versions, and the security concerns that must be considered to implement it properly.

So, let’s get started!

Diffie-Hellman key exchange

The Diffie-Hellman key exchange is a mathematical method for reliably exchanging cryptographic keys over a public channel. It was one of the earliest public-key protocols.

Let us understand this protocol in depth.

What is it?

The Diffie-Hellman key exchange protocol was the first commonly used way of producing and exchanging keys through an insecure channel.

In the above terms, it may not appear fascinating or new, so let us share an example of why the Diffie-Hellman key exchange was such a crucial milestone in cryptography and why it is still widely used today.

Let’s say you are an undercover agent and need to send some crucial information to the head. In this case, how will you ensure that the message reaches only the head and no third-party tempers with it?

There could be many solutions, the most common being encrypting the message with a code. The simplest method could be to arrange the type of code and key beforehand, or it could be done through a secure channel of communication.

Assume that you are not a good agent, and you and your head have agreed upon using a weak cipher, let’s say the shift cipher, to encode your secret message.

In this method, every “a” becomes “c,” “b” becomes “d,” “c” becomes “e,” and so on, till “z” becomes “b.”

Using this shift cipher, the message “Can you hear me” becomes “ecp aqw igct og.” In this scenario, we assume that eve is as incompetent as the agent and will not be able to crack the simple code.

But what if you do not have the code arranged with your head beforehand?

Suppose you wish to communicate with another agent from a different nation you have never met. This means you do not have a secure channel to communicate with them. You must encrypt your message to keep it safe from the adversary.

So, how do you exchange information safely with someone if you haven't exchanged the key beforehand?

The Diffie-Hellman key exchange was the first publicly available solution to this problem. The approach enables random people to securely establish a shared key, even via an unsecured channel that adversaries may be observing.

Uses

The primary goal of the Diffie-Hellman key exchange is to securely establish shared secrets from which keys may be obtained. These keys can then be used with symmetric-key algorithms to communicate messages securely. Since symmetric algorithms are more efficient than public key algorithms, they are commonly used to encrypt most data.

• In theory, the Diffie-Hellman key exchange may be used to generate public and private keys. In practice, though, RSA is more often used. This is because the RSA technique can also sign public-key certificates, but the Diffie-Hellman key exchange cannot.
   
• Because the ElGamal algorithm, prominently used in the PGP, is based on the Diffie-Hellman key exchange, any protocol that employs it is functionally implementing Diffie-Hellman.
   
• The Diffie-Hellman key exchange is widely used in security protocols as one of the most prevalent ways for properly distributing keys. As a result, it is an essential component of our secure communications.
   
• The Diffie-Hellman key exchange is commonly used as part of various protocols to help protect our connection to a website, remotely access another computer, and to transmit encrypted emails.

Working

The Diffie-Hellman Key exchange is a complex protocol, and it may be difficult to understand its working. It requires the use of very large numbers and complex maths.

To understand easily, let us start with an analogy. After getting the big-picture, we will see the processes' technicalities.

Suppose Alice and Bob want to mix paint. 

1. They both decide on a random color, to begin with. Assume they exchange messages and agree on yellow as their common color, as shown in the picture below:

2. They decide on their color. They do not inform the other party of their decision. Let's assume Alice goes with red and Bob goes with cyan.

3. The next step is for Alice and Bob to combine their secret colors with the yellow they selected collectively. According to the above image, Alice gets an orangish mix, while Bob gets a darker blue.

4. They share the product with the opposite party after mixing. Alice gets the deeper blue paint, while Bob gets the orange paint.

5. After receiving the mixed result from each other, they add their secret color to it. Alice adds her secret red paint to the deeper blue, while Bob adds his secret cyan to the orange mix he got.

6. To our surprise, both get the same color, i.e., brown color. This is the shared color, referred to as the common secret.

The main factor of the Diffie-Hellman key exchange is that both sides achieve the same result without ever sending the complete shared secret over the communication channel.

Now, if an attacker is observing this exchange, all he can get is the common yellow color that Alice and Bob started with and the mixtures that they exchanged. 

The structure of the Diffie-Hellman key exchange is responsible for making it so valuable. It enables the two parties to interact via a potentially unsafe connection while establishing a shared secret that may be used to generate encryption keys for future communications.

Technical Details

It operates on the same premise as the above example. Still, instead of mixing and delivering colors, the Diffie-Hellman system performs computations based on extremely big prime numbers and sends them over.

The prime (p) should be at least 2048 bits long to ensure security. But, for easy understanding, we will be working with much smaller numbers here. We must remember that if such small numbers are used in practice, then the Diffie-Hellman key exchange would be insecure.

Suppose Alice and Bob start by mutually deciding on two numbers to work with. Let these numbers be modulus (p) and base (q).

In practice, the modulus (p) is a very big prime integer, and the base (g) is kept as small as possible to ease computations. The base (g) is formed from a cyclic group (G), generally formed before the other steps.

• To take our example, let us assume that the modulus (p) is 19 and the base (g) is 6.
• After agreeing on these numbers, Alice selects a secret number, m, for herself, while Bob selects his secret number n. Let us suppose they decide:
  m=2
  n=4
• Alice then does the following calculation to get the number she will send to Bob:
  A = g^m mod p
  Here, the mod is the modulo operation.
  A = 6² mod 19
  A = 36 mod 19
  A = 17
• Doing the same above steps for Bob:
  B = gⁿ mod p
  B = 6⁴ mod 19
  B = 1296 mod 19
  B = 4
• Alice and Bob send their results to each other.
• Alice then uses the following formula to determine the shared secret s:
  s = B^m mod p
  s = 4² mod 19
  s = 16 mod 19
  s = 16
• Bob as well does the same:
  s = Aⁿ mod p
  s = 17⁴ mod 19
  s = 83,521 mod 19
  s = 16

As you can see, both parties got the same answer for s, which was 16. This is the shared secret that only Alice and Bob are aware of. They may then use this to generate a key for symmetric encryption, allowing them to exchange information between themselves securely that only they can access.

Why is it secure?

Mathematically, the Diffie-Hellman key exchange is secure since it is based on one-way functions. These computations are simple to do in one direction but far more challenging to perform in the opposite direction.

It is based on the Diffie-Hellman problem, which assumes that under the correct parameters, calculating gmn from the independent values of g, gm, and gn is impossible. Despite the fact that attackers may intercept the values p, g, A, and B, the Diffie-Hellman key exchange is deemed safe since there is presently no publicly known mechanism to quickly obtain gmn from the other values.

Authentication & the Diffie-Hellman key exchange

In practice, the Diffie-Hellman key exchange is rarely used on its own. The primary reason for this is that it does not enable authentication, leaving users exposed to man-in-the-middle attacks.

These attacks are possible when the Diffie-Hellman key exchange is used alone because it cannot confirm if the other person in a connection is who they claim to be. Users may interact with attackers while they believe they are communicating with a trusted person if no authentication is used.

As a result, the Diffie-Hellman key exchange is typically used with some form of authentication. This often involves the use of digital certificates and a public-key algorithm, such as RSA, to validate each party's identity.

Variations

The Diffie-Hellman key exchange may be implemented in various ways, and it has also served as the foundation for various additional algorithms. Some implementations have authorization, while others include cryptographic features like perfect forward secrecy.

Some of these are listed below:

• ElGamal
• Elliptic-curve Diffie-Hellman
• TLS
• STS(Station-to-Station protocol) 

Security issues

The security of the Diffie-Hellman key exchange is determined by how it is implemented as well as the numbers used. As previously mentioned, it has no way of authenticating the other party on its own. Still, other mechanisms are applied to verify that the other party in a connection is not fake.

Number selection parameters

The numbers should not only be significant but also need to be sufficiently random.

To ensure security, the integer p should be 2048 bits long. The base, g, can be a small integer like 2, but it must come from a G order with a large prime factor.