Brief History

In 1976 Whitfield Diffie and Martin E.Hellman imagined a future where people would regularly communicate through electronic networks and be vulnerable to having their communications stolen or altered.By seeing today’s world, after nearly 40 years, their forecasts were remarkably prescient.

Two of the main disadvantages of symmetric key cryptography are the need for a secure means of key transfer and managing different keys for different communicating parties. Diffie and Hellman proposed an algorithm which showed that Public-key cryptography was possible, and was ready to cover these disadvantages of symmetric key cryptography.

Diffie-Hellman key exchange is a way of generating a shared secret key between two people in such a way that the key can’t be seen by observing the communication and then with the key they can exchange information across an insecure channel. We’re not sharing information during the key exchange; we’re creating a key together to share the information securely. Even if the channel is monitored by adversary then also it is nearly impossible to detect the shared key.

How it Works

Firstly both parties let say Alice and Bob agree on two prime numbers.The first prime p is a large number on the order of 300 decimal digits (approximately 1024 bits) and g is a primitive root modulo p.Generally it’s a good idea to choose in such a way that p and (p -1)/2 is also prime. Also  p has to be large enough to withstand some basic attacks.These kind of primes where p and (p -1)/2 are both primes known as Sophie-Germain prime. These numbers are then shared publicly. Now the following happens in both sides

Alice	Bob
1.   Chooses a large random number  a privately 2.   Computes A =  g^(a) mod p 3.   Send A to Bob 4.   Receive B from Bob 5.   Compute K_a = B^a mod p = (g^b)^a mod p = g^(ab) mod p	1.   Chooses a large random number b privately 2.   Computes B = g^(b) mod p 3.   Send B to Alice 4.   Receive A from Alice 5.   Compute K_b = A^b mod p = (g^a)^b mod p = g^(ab) mod p

After the calculation they both obtain at a shared secret key K = K_a = K_b.Although Alice never know what was the initial number Bob used or vice versa.

Security of Diffie-Hellman key exchange

The Strength of Diffie-Hellman key exchange protocol lies in the hardness to solve Discreet logarithm problem and Diffie-Hellman problem.

Even if an adversary (let’s say Eve) gets the values of  A ,B, p and g because they are all public, he can’t compute the secret key.For this he needs either a or b, both are private and finding the values of either a or b from A or B respectively is computationally infeasible for large p.This problem is generally known as Discreet logarithmic problem (DLP).

Diffie–Hellman Problem (DHP) is the problem of computing the value of g^(ab) mod p from the known values of  g^(a) mod p and g^(b) mod p.Two type of DHP are Computational Diffie-Hellman (CDH) & Decisional Diffie-Hellman (DDH).

To totally break the protocol a passive eavesdropper, Eve, must compute the Diffie-Hellman function defined as dh(g^(a), g^(b)) =  g^(ab) which finds g^(ab) from g^(a) and g^(b).The Computational Diffie-Hellman assumption says no efficient algorithm can solve the above problem of finding .

But unfortunately CDH by itself isn’t sufficient to prove that Diffie-Hellman protocol is useful.

Even though Eve can’t find the secret key from A, B, p and g , he may predict some of the bits of the key very confidently.The Decisional Diffie-Hellman assumption bounds the amount of information eve can predict correctly given g^(a), g^(b), p and g.Mathematically it says that there is no efficient probabilistic algorithm that given any triplet g^(a), g^(b), g^(c) the algorithm outputs True if a = bc and False otherwise.

Some attack on diffie-hellman key exchange

Diffie-Hellman key exchange algorithm is not secure against active attackers. The simplest attack is probably to substitute g^(a) and g^(b) by 1 during transmission. After this tampering, Alice computes 1^(a)=1 as its common key and Bob computes 1^(b)=1 as its common key. Since both end up with the same key, the communication may proceed without problem. After that initial tampering, eve, the attacker knows the common secret (1).So, he just needs to eavesdrop on the remaining of the communication to do any damage he wants.

The solution to this attack is aborting the key exchange or freshly starting the algorithm if the incoming value is 1.

Another well-known active attack against Diffie-Hellman key exchange is the man-in-the-middle attack. Here, eve breaks the communication link between Alice and Bob. Afterwards, he communicates with Alice pretending to be Bob and with Bob pretending to be Alice. On each side, he participates in a copy of the Diffie-Hellman key exchange. After that, eve can decrypts any incoming message, and he may change it or without changing send to the other party after re-encrypting the information. As a consequence, eve can listen to the whole communication. Neither of the party can detect the man-in-the-middle attack, unless some external mean of authentication is used.

Due to the fact that Diffie-Hellman protocol is not resilient to man-in-the middle attacks, it is not used in its basic form in practice.

Remarks 

The Diffie-Hellman key exchange alone does not provide authentication of any kind. It only allows two parties to share a common secret. On a daily basis, individuals establish secure online communications with banks, e-commerce sites, email servers and the cloud. The Diffie-Hellman protocol protects daily internet communications and trillion of dollars in financial transactions. The idea of Public-Key cryptography was appeared in the paper “New Directions in Cryptography”, authored by diffie and hellman in 1976, which brought a revolution in the field of cryptography and that won them the prestigious “Turing award” in the year 2015.