Diffie-Hellman Key Exchange Attacks

Diffie-Hellman Protocol Basics

Diffie-Hellman allows two parties (Alice and Bob) to establish a shared secret over an insecure channel:

1. Agree on public parameters: a large prime modulus $p$ and a generator $g$.
2. Alice picks private key $a$, computes public key $A = g^a \pmod p$.
3. Bob picks private key $b$, computes public key $B = g^b \pmod p$.
4. Shared secret: $S = B^a \pmod p = A^b \pmod p = g^{ab} \pmod p$.

The security relies on the hardness of the Discrete Logarithm Problem (DLP): finding $a$ given $g, A, p$.

---

1. Small Subgroup Attack

If $p - 1$ has many small prime factors ($p - 1 = q_1^{e_1} q_2^{e_2} \dots q_k^{e_k}$), an attacker can pick malicious public keys $A’$ of small order $q_i$.

When Bob computes $S’ = (A’)^b \pmod p$, $S’$ will lie inside a small subgroup of order $q_i$. The attacker can brute-force $b \pmod{q_i}$ easily!

Using the Chinese Remainder Theorem (CRT), combining equations for multiple small primes $q_i$ recovers Bob’s full secret key $b$:

from sage.all import *

# Solving discrete log in SageMath when p - 1 is smooth (Pohlig-Hellman algorithm)
p = ...
g = ...
A = ...

# Pohlig-Hellman is executed automatically in Sage when order is smooth
a = discrete_log(mod(A, p), mod(g, p))
print(f"Recovered private key: {a}")

---

2. Invalid Parameter / Static Generator Attacks

$g = 0, 1$ or $p - 1$

If generator $g = 1$, then $A = 1^a = 1 \pmod p$. The shared secret $S$ is always $1$. If generator $g = p - 1 \equiv -1 \pmod p$, then $A \in {1, p - 1}$. The shared secret is trivially guessed.

Composite Modulus $N$ instead of Prime $p$

If the modulus is not prime ($N = p \cdot q$), the discrete log problem modulo $N$ reduces to finding discrete logs modulo $p$ and $q$ separately, then combining them via CRT.

---

3. Man-in-the-Middle (MitM) Key Replacement

If the protocol lacks authentication (signatures or MACs), an attacker in the middle intercepts public key exchanges:

Alice                        Attacker                        Bob
  | --- Send A = g^a --->       |                              |
  |                             | --- Send A' = p - 1 ------>  |
  | <--- Send B' = p - 1 ------ |                              |
  |                             | <--- Send B = g^b ---------  |

If $A’ = p - 1 \equiv -1 \pmod p$: Bob computes shared secret $S = (p - 1)^b \pmod p \equiv (-1)^b \pmod p \in {1, p - 1}$. Attacker tests both values ($1$ and $p - 1$) to decrypt all intercepted communications!

---

SageMath Cheat Sheet for DH

# Discrete Logarithm using SageMath
F = GF(p)
g = F(g_val)
A = F(A_val)

# Solves DLP using Pohlig-Hellman, BSGS, or Index Calculus depending on prime size
secret = A.log(g)
print("Secret key:", secret)