Diffie-Hellman Key Exchange — Logjam and DH Group Pitfalls

Whitfield Diffie and Martin Hellman published 'New Directions in Cryptography' in 1976 — the paper that invented public key cryptography. The Diffie-Hellman key exchange protocol solves the fundamental key distribution problem: how do two parties who have never met establish a shared secret over a public channel?

The protocol is used in every TLS handshake (HTTPS), every SSH connection, every Signal message. Its security rests on the discrete logarithm problem: given g^x mod p, computing x is computationally infeasible for large p. Ephemeral Diffie-Hellman (DHE/ECDHE) in TLS provides forward secrecy — past sessions remain secure even if the server's long-term key is later compromised.

The Protocol

Public parameters: large prime p, generator g. Alice chooses private a, sends A = g^a mod p. Bob chooses private b, sends B = g^b mod p. Shared secret = A^b = B^a = g^(ab) mod p. An eavesdropper sees p, g, A, B but cannot compute g^(ab) without solving the discrete log problem.

import random

# Using small numbers for demonstration — real DH uses 2048+ bit primes
P = 23   # prime modulus (real: 2048+ bits)
G = 5    # generator

# Alice
alice_private = random.randint(2, P-2)
alice_public  = pow(G, alice_private, P)

# Bob
bob_private = random.randint(2, P-2)
bob_public  = pow(G, bob_private, P)

# Exchange public keys over insecure channel
# Alice computes shared secret
alice_secret = pow(bob_public, alice_private, P)
# Bob computes shared secret
bob_secret   = pow(alice_public, bob_private, P)

print(f'Alice public: {alice_public}')
print(f'Bob public:   {bob_public}')
print(f'Alice secret: {alice_secret}')
print(f'Bob secret:   {bob_secret}')
print(f'Match: {alice_secret == bob_secret}')

The Discrete Logarithm Problem

DH security rests on: given g, p, and g^x mod p, find x. This is the discrete logarithm problem. The best classical algorithms (Index Calculus, Number Field Sieve) run in sub-exponential time — which is why 2048-bit DH parameters are needed even though AES-128 is considered equivalent security.

Note: Shor's quantum algorithm solves discrete log in polynomial time. Elliptic curve Diffie-Hellman (ECDH) suffers the same quantum vulnerability. Post-quantum key encapsulation (CRYSTALS-Kyber) is the replacement being deployed in TLS 1.3 and Signal.

Forward Secrecy

DH enables forward secrecy — a property that makes past sessions immune to future key compromise. In classic RSA key exchange, the server's RSA private key encrypts the session key. If an attacker records encrypted traffic and later obtains the RSA key, they can decrypt all past sessions.

DHE (ephemeral DH): each TLS session generates a fresh DH key pair. Even if the server's certificate key is compromised, past session keys cannot be derived — they were never stored and the ephemeral DH keys are discarded after use. TLS 1.3 mandates ephemeral key exchange (ECDHE) and removed all non-forward-secret cipher suites.

Vulnerabilities and Attacks

Basic DH is vulnerable to man-in-the-middle attacks — an attacker can intercept both parties' public keys, replace them with their own, and establish separate shared secrets with each party. This is why TLS authenticates the DH public key using a certificate signed by a trusted CA.

Implementation Best Practices

When implementing or deploying DH:

1. Parameter generation: Use well-known groups (RFC 3526) instead of generating your own prime — DH parameter generation is slow and error-prone. For ECDH, use X25519 (RFC 7748) which has built-in guard against twist attacks.
2. Key validation: Always verify received public keys are not in the trivial subgroup. For classic DH, check that 1 < pub_key < p-1 and that pub_key^q mod p != 1 (where q is the subgroup order).
3. Ephemeral keys: Generate fresh DH key pairs for each session. Never reuse a static DH key pair across sessions.
4. TLS configuration: Prefer ECDHE cipher suites with X25519. If classic DHE is required for legacy clients, use at least 2048-bit groups (RFC 7919).
5. Fallback safety: If DHE key exchange fails (e.g., no compatible parameters), fail closed — do not fall back to RSA key exchange which breaks forward secrecy.

import math

def validate_dh_public_key(pub_key, p, q):
    """Validate received DH public key against small subgroup attack."""
    if pub_key <= 1 or pub_key >= p - 1:
        return False
    # Check that pub_key is in the prime-order subgroup
    if pow(pub_key, q, p) != 1:
        return False
    return True

# Example using a safe prime (p = 2*q + 1)
P = 0x00ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff  # RFC 3526 2048-bit MODP group
G = 2
# q = (p-1)//2  (since p is a safe prime)
Q = (P - 1) // 2

# Assume bob_public is received from peer
bob_public = pow(G, 123456, P)
if validate_dh_public_key(bob_public, P, Q):
    print("Valid public key")
else:
    print("INVALID — possible small subgroup attack! Do not proceed.")