Diffie-Hellman Man-in-the-middle attack

Introduction

The Diffie-Hellman protocol is a method for two users to generate a shared private secret with which they can then exchange information across a public channel. This protocol is mostly used to secure a variety of network services.

A Diffie-Hellman key exchange by itself does not provide authentication of the communicating parties and is thus vulnerable to a man-in-the-middle attack.
An attacker may establish two distinct key exchanges between the two parties, allowing it to decrypt, then re-encrypt the messages transmitted between them.

The Diffie-Hellman key exchange

Alice and Bob want to exchange information across an insecure channel.
The Python code below is a simple implementation of the Diffie-Hellman protocol.

[ Alice ]---------------------[ Bob ]

#!/usr/bin/env python
from random import getrandbits

g = 2
p = 0xF36E2495C4A214F8A498AC594894C19B
bits = 128

# Generate Alice's secret and public keys (a, A)
a = getrandbits(bits)
A = pow(g, a, p)

# Generate Bob's secret and public keys (b, B)
b = getrandbits(bits)
B = pow(g, b, p)

# Generate the shared secrets
sa = pow(B, a, p)
sb = pow(A, b, p)

if sa == sb:
    print("Alice and Bob share the same secret : {:x}".format(sa))

g is the generator
p is a prime
a is Alice's secret
b is Bob's secret
A is Alice's public key
B is Bob's public key
sa and sb are Alice's and Bob's shared key

Man-in-the-middle attack against Diffie-Hellman

This time a malicious thrid party, Mallory, is able to modify messages between Alice and Bob.
Mallory knows p the prime, and g the primitive root modulo p.

[ Alice ]-----[ Mallory ]-----[ Bob ]

#!/usr/bin/env python
from random import getrandbits

g = 2
p = 0xF36E2495C4A214F8A498AC594894C19B
bits = 128

# Generate Alice's secret and public keys (a, A)
a = getrandbits(bits)
A = pow(g, a, p)

# Generate Bob's secret and public keys (b, B)
b = getrandbits(bits)
B = pow(g, b, p)

# Generate Mallory's secret and public keys (m, M)
m = getrandbits(bits)
M = pow(g, m, p)

# Generate the shared secrets
sam = pow(M, a, p)
sma = pow(A, m, p)

sbm = pow(M, b, p)
smb = pow(B, m, p)

if sam == sma:
    print("Alice and Mallory share the same secret : {:x}".format(sam))

if sbm == smb:
    print("Bob and Mallory share the same secret : {:x}".format(sbm))

m is Mallory's secret
M is Alice's public key
sam and sma are Alice's and Mallory's shared key
sbm and smb are Bob's and Mallory's shared key