Diffie-Hellman (Man-in-the-middle)

Diffie-Hellman (Man-in-the-middle)

The Diffie-Hellman method is used in key exchange, and where two parties can generate a shared secret encryption key.

Bob and Alice first need to agree on two values (g and p), where p is a prime number. Next they generate two random numbers (a and b), and exchange values. Unfortunately thus is prone to a man-in-the-middle attack, and where Eve generates two keys, with one to communicate with Bob, and the other to communicate with Alice.

Method

In this case, no matter what value Eve gets, she will return a value to both Bob and Alice, based on her random number.

For example if g=15 and p=1011, and Alice uses a random value of 5. For her key, Alice will calculate:

A=15⁵ (mod 1011)=114

If Bob takes a random value of 9. Bob will calculate:

B=15⁹ (mod 1011)=462

Eve changes Alice’s value in the tunnel to give:

114⁷ (mod 1011)=402

So, Alice receives a value of 402. She calculates a key of:

KeyAlice=402⁵ (mod 1011)=636

Bob receive a value of 426 and calculate his key of:

KeyBob= 462⁹ (mod 1011)=483

This is, of course, wrong, as the Diffie-Hellman method should give the same value. But Eve is the man-in-the-middle, so she has two keys, and basically deciphers the message, and re-encrypts.

Sample code

The following gives some sample code for the DH calculation [link]:

import random
import base64
import hashlib
import sys

g=15
p=1011

a= 5
b = 9
eve = 7

message=21

A=(g**a) % p

B=(g**b) % p

Eve1 = (A**eve) % p
Eve2 = (B**eve) % p

Key1= (Eve1**a) % p
Key2= (Eve2**b) % p

print 'g: ',g,' (a shared value), n: ',p, ' (a prime number)'

print '\n== Random value generation ==='

print '\nAlice calculates:'
print 'a (Alice random): ',a
print 'Alice value (A): ',A,' (g^a) mod p'

print '\nBob calculates:'
print 'b (Bob random): ',b
print 'Bob value (B): ',B,' (g^b) mod p'

print '\n==Alice sends value to Eve ==='

print 'Eve takes Alice\'s value and calculates: ',Eve1
print 'Alice gets Eve\'s value and calculates key of: ',Key1

print '\n==Bob sends value to Eve ==='

print 'Eve takes Bob\'s value and calculates: ',Eve2
print 'Bob gets Eve\'s value and calculates key of: ',Key2

A sample run is here [link]:

g: 15 (a shared value), n: 1011 (a prime number)
Eve’s value: 7

== Random value generation ===

Alice calculates:
a (Alice random): 5
Alice value (A): 114 (g^a) mod p

Bob calculates:
b (Bob random): 9
Bob value (B): 462 (g^b) mod p

==Alice sends value to Eve ===
Eve takes Alice’s value and calculates: 402
Alice gets Eve’s value and calculates key of: 636

==Bob sends value to Eve ===
Eve takes Bob’s value and calculates: 528
Bob gets Eve’s value and calculates key of: 483

Conclusion

The key problems of the DH method is that Bob and Alice cannot validate each other, and thus we can get a MITM attack. It also suffered from pre-computed values (Logjam) and where values for the random numbers could be pre-computed for default prime numbers. These problems have now been overcome with the help of elliptic curve methods (ECDH — Elliptic Curve Diffie Hellman), and in supporting ephemeral keys and forward secrecy. For enterprise networks, Tor, Wi-fi and many other things, ECDH is the king of the hill just now.