Diffie-Hellman key exchange algorithm reference

Diffie-Hellman key exchange algorithm

Diffie-Hellman key exchange algorithm

Diffie and Hellman deviced an amazing solution to the problem of key agreement or key exchange in 1976. The solution is called Difie-Hellman key Exchange/Agreement algorithm.

The beauty of this scheme is that the two parties, who want to communicate securely, can agree on a symmetric key using this technique. This key can be used for encryption/decryption.

However, we must note that Diffie-Hellman key exchange algorithm can be used only for key agreement, but not for encryption or decryption of the message. Once both the parties agree on the key to be used, they need to use other symmetric key encryption algorithm.

---

The Algorithm

This is a 7 step algorithm. Let us understand it with the help of a simple example.

Suppose Puli and Snehal want to agree upon a key to be used for encrypting/decrypting message that would be exchanged between them.

Diffie-Hellman Key Exchange Algorithm

1.Firstly, Puli and Snehal agree upon two large prime numbers, n and g. These two numbers need not be kept secret.
2.Puli chooses another large number x, and calculate A such that:
     A=g^x mod n
3.Puli sends the number A to Snehal.
4.Snehal independently chooses another large random integer y and calculates B such that:
     B=g^y mod n
5.Snehal sends the number B to Puli.
6.Puli now computes the secret key K1 as follows :
     K1=B^x mod n
7.Snehal now computes the secret key K2 as follows :
     K2=A^y mod n

Result:
K1=K2=K =The symmetric key

K now becomes the shared symmetric key between Puli and Snehal.

---

Example of Diffie-Hellman Algorithm

Let us take an example:

1. let n=11, g=7
2. let x=3, then we have, A=g^x mod n
                           =7³ mod 11                            =343 mod 11
                           =2
3. Puli sends 2 to Snehal.
4. let y=6, then we have, B=g^y mod n
                           =7⁶ mod 11                            =117649 mod 11
                           =4
5. Snehal sends 4 to Puli.
6. Now, we have K1=B^x mod n
                  =4³ mod 11
                  =64 mod 11
                  =9
7. Now, we have K2=A^y mod n
                  =2⁶ mod 11
                  =64 mod 11
                  =9

As we have seen this algorithm under a very small prime numbers, but in real life these values are very large.

---

Problems with the algorithm

Man-in-the-middle attack

A man, say Golani, is an attacker. Lets see how he come to know the key to be shared between Puli and Snehal.

step I:
         Puli                Golani               Snehal
         n=11, g=7         n=11, g=7         n=11, g=7
step II:
         Puli                Golani               Snehal
          x=3              x=8, y=6            y=9
step III:
          Puli                Golani               Snehal
        A=g^x mod n          A=g^x mod n        B=g^y mod n
         =7³ mod 11          =7⁸ mod 11        =7⁹ mod 11
         =343 mod 11         =5764801 mod 11   =40353607 mod 11
         =2                  =9                =8
                            B=g^y mod n
                             =7⁶ mod 11
                             =117649 mod 11
                             =4
step IV:
          Puli                 Golani               Snehal
         A=2, B=4^*           A=2, B=8          A=9^*, B=8
step V:
          Puli                Golani               Snehal
       K1=B^x mod n         K1=B^x mod n       K2=A^y mod n
         =4³ mod 11          =8⁸ mod 11        =9⁹ mod 11
         =64 mod 11          =16777216 mod 11  =387420489 mod 11
         =9                  =5                =5
                            k2=A^y mod n
                             =2⁶ mod 11
                             =64 mod 11
                             =9

At step IV, the real attack happens, 
Golani intercepts the value of A sent by the Puli to Snehal his own A instead.
Moreover, Golani intercepts the value of B sent by Snehal to Puli and sends Puli his own B, instead.

From this we can conclude that man-in-the-middle attack can work against the Diffie-Hellman key exchange algorithm, causing it to fail.

This is plainly because the man-in-the-middle makes the actual communicators believe that they are talking to each other, whereas they are actually talking to man-in-the-middle, who is talking to each of them!