diffiehellman

Diffie-Hellman man-in-the-middle attack

In Diffie-Hellman key exchange method there are 4 public parameters. Two of them form the initial agreement which are the modulus (p) and base (g). And base (g) should be a primitive root modulo modulus (p). Two remaining parameters are public keys computed and shared publicly by parties, who are going to generate the symmetric secret key individually.

• modulus (p)
• base (g)
• Alice's public key (A)
• Bob's public key (B)

While two parties share neither their private keys (a: Alice's secret, b: Bob's secret) nor the shared secret key which they compute it individually after exchanging their public keys, the DiscoverSharedSecret method illustrates how is it possible to regenerate the shared secret key by only using the publicly exchanged parameters without any knowledge of the private parameters and equal assertions are made in tests for different private key pairs in the test file.

Attack described

Suppose key exchange parties agreed on:

• modulus p = 11
• base: g = 6
• Alice chooses a secret integer a = 9 and sends Bob her public key A = 2 calculated from:

   A = g^a mod p = 6^9 mod 11 = 10077696 mod 11 = 2
  

• Bob chooses a secret integer b = 3 and sends Alice his calculated public key B = 7 calculated from:

   B = g^b mod p = 6^3 mod 11 = 216 mod 11 = 7
  

Now that public parameters have been exchanged it's time for Alice and Bob to calculate the shared secret key:

• Alice:

   sa = B^a mod p = 7^9 mod 11 = 40353607 mod 11 = 8
  

• Bob:

   sb = A^b mod p = 2^3 mod 11 = 8 mod 11 = 8
  

As it was expected they both calculated the same shared secret key using counterpart's public key and their own private keys: sa = sb = 8. Let's check if it's possible to calculate the same shared secret key without any knowledge of private keys (a and b):

1. Find one cycle of remainders of sequential powers (k) of the base (g) modulo the modulus (p) which results in one permutation of reduced residue system modulo (p):

   • rrs = {r | r = g^k mod p and 0 < k <= φ(p) and k ∈ ℕ}

     rrs = {6^1 mod 11, 6^2 mod 11, ..., 6^10 mod 11} --> rrs = {6, 3, 7, 9, 10, 5, 8, 4, 2, 1}

     Calculating all rrs elements and searching it for the public-keys is actually a brute-force attack which is a costly action esp. when dealing with big numbers and this is a factor which protects diffie-hellman against brute-force attack.

2. As g is a primitive root of p and B and A are remainders of a power of g modulo p both A and B exist in the rrs. Find index of one of A or B in selected rrs:

   indexB = rrs.indexOf(B=7) = 2
   indexA = rrs.indexOf(A=2) = 8
   

3. Shared secret key sh can be computed using each index individually:

   sh = 1
   for i := 0; i <= indexB; i++ {
       sh = (sh * A) mod p
   }
   ---
   sh = 1
   sh = (1 * 2) mod 11 = 2 // i = 0
   sh = (2 * 2) mod 11 = 4 // i = 1
   sh = (4 * 2) mod 11 = 8 // i = 2
   

   or

   sh = 1
   for i := 0; i <= indexA; i++ {
      sh = (sh * B) mod p
   }
   ---
   sh = 1
   sh = (1 * 7) mod 11 = 7 // i = 0
   sh = (7 * 7) mod 11 = 5 // i = 1
   sh = (5 * 7) mod 11 = 2 // i = 2
   sh = (2 * 7) mod 11 = 3 // i = 3
   sh = (3 * 7) mod 11 = 10 // i = 4
   sh = (10 * 7) mod 11 = 4 // i = 5
   sh = (4 * 7) mod 11 = 6 // i = 6
   sh = (6 * 7) mod 11 = 9 // i = 7
   sh = (9 * 7) mod 11 = 8 // i = 8
   

   and surprisingly sh = sa = sb = 8