Diffie-Hellman Key Exchange, in depth: a small-subgroup attack run end to end, public-key validation, key lifetime and wire encoding

The group structure an attacker exploits

Work modulo a prime p. The non-zero residues form a cyclic group of order p - 1 under multiplication. Lagrange's theorem says the order of every element divides the order of the group, and in a cyclic group there is exactly one subgroup for each divisor of p - 1. If r divides p - 1, you can manufacture an element of order r by raising any random element to the power (p - 1) / r: the result h satisfies h^r = 1, and as long as it is not 1 itself, its order is exactly r when r is prime.

Now suppose a server with private exponent x receives h as the peer's public value and computes h^x mod p. Because h has order r, the result depends only on x mod r. There are just r possible shared secrets. If the server then proves knowledge of the derived key, for example with a MAC over a Finished message or an encrypted reply, the attacker can try all r candidates offline and learn x mod r. That is the leak. It is not a weakness of the discrete logarithm; it is a weakness of accepting an element from the wrong subgroup.

Two conditions make it fatal. First, p - 1 must have many small prime factors, which is what happens with randomly chosen primes or with DSA-style primes where p - 1 = k * q and the cofactor k is never checked. Second, the server must reuse x across connections, so each query extracts another residue of the same secret. Combine the residues with the Chinese Remainder Theorem and you have x modulo the product of the small factors. This attack is usually credited to Lim and Lee (1997), and the Pohlig-Hellman decomposition explained in Primitive Roots and Discrete Logarithms is the same idea seen from the attacker's side.

The attack at a glance

The attack in code

The script below builds a 70-bit group whose p - 1 is 2 times a 32-bit prime q times every odd prime from 3 to 31. The honest generator g has order q, and the server picks x < q. The sizes are toy sizes so it runs in under a second; the structure is exactly what a real misconfigured deployment has. It uses only the standard library and Python 3.8+ (for pow(m, -1, n)).

import hashlib, hmac, random

def is_probable_prime(n, rounds=40):            # Miller-Rabin
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2
    d, s = n - 1, 0
    while d % 2 == 0:
        d, s = d // 2, s + 1
    for _ in range(rounds):
        x = pow(random.randrange(2, n - 1), d, n)
        if x in (1, n - 1):
            continue
        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

SMALL = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31]

def weak_group(rng):
    m = 2
    for r in SMALL:
        m *= r
    while True:
        q = rng.getrandbits(32) | (1 << 31) | 1
        if is_probable_prime(q) and is_probable_prime(m * q + 1):
            p = m * q + 1
            g = pow(rng.randrange(2, p - 1), (p - 1) // q, p)   # order q
            if g != 1:
                return p, q, g

def tag_for(k, nbytes):
    key = hashlib.sha256(k.to_bytes(nbytes, "big")).digest()
    return hmac.new(key, b"server finished", "sha256").digest()

class StaticServer:
    def __init__(self, p, q, g, rng):
        self.p, self.q, self.x = p, q, rng.randrange(1, q)
        self.nbytes = (p.bit_length() + 7) // 8
        self.pub = pow(g, self.x, p)
    def handshake(self, peer_pub):
        k = pow(peer_pub, self.x, self.p)       # BUG: peer_pub never validated
        return tag_for(k, self.nbytes)

def crt(residues, moduli):
    x, m = 0, 1
    for r, n in zip(residues, moduli):
        t = ((r - x) * pow(m, -1, n)) % n
        x, m = x + m * t, m * n
    return x, m

def attack(server, p):
    residues, moduli = [], []
    for r in SMALL:
        h = 1
        while h == 1:                           # element of order exactly r
            h = pow(random.randrange(2, p - 1), (p - 1) // r, p)
        tag = server.handshake(h)               # one online query
        for i in range(r):                      # offline: r MAC trials
            if hmac.compare_digest(tag_for(pow(h, i, p), server.nbytes), tag):
                residues.append(i)
                moduli.append(r)
                break
    return crt(residues, moduli)

rng = random.Random(7)
p, q, g = weak_group(rng)
srv = StaticServer(p, q, g, rng)
x, m = attack(srv, p)
print(f"p bits={p.bit_length()} q={q} covered={m} (> q: {m > q})")
print(f"recovered={x} actual={srv.x} match={x == srv.x}")

Worked example: reading the run

With seed 7 the run prints a 70-bit p, q = 4008365027, and a covered modulus of 100280245065, the product 3 x 5 x ... x 31. The server's secret was 2869965265 and the attack recovered 2869965265. Read the cost carefully:

If the small factors had covered only part of q, the attacker would know x modulo m and could finish with a kangaroo search over the remaining q / m possibilities in square-root time. The fix is not a bigger prime; a 4096-bit random prime with smooth p - 1 leaks just as readily.

Validation that stops it

Full public-key validation for finite-field DH, as NIST SP 800-56A describes it, has two checks: the value is in range, and it lies in the subgroup of prime order q.

class InvalidPublicKey(ValueError):
    pass

def validate_ffdh_public(y: int, p: int, q: int) -> int:
    # 1 and p - 1 generate subgroups of order 1 and 2: reject them outright.
    if not 1 < y < p - 1:
        raise InvalidPublicKey("out of range")
    # Lagrange: y is in the order-q subgroup iff y^q = 1 (mod p).
    if pow(y, q, p) != 1:
        raise InvalidPublicKey("not in the prime-order subgroup")
    return y

def handshake(self, peer_pub):
    validate_ffdh_public(peer_pub, self.p, self.q)
    k = pow(peer_pub, self.x, self.p)
    return tag_for(k, self.nbytes)

Run the attack again with the validated handshake and the first query raises: an element of order 3 satisfies h^q != 1 because 3 does not divide q. The cost is one extra modular exponentiation per handshake, which with square-and-multiply is roughly the cost of the key agreement itself when q is the size of p.

Safe primes reduce the stakes. If p = 2q + 1 with q prime, the only subgroup orders are 1, 2, q and 2q. The range check removes orders 1 and 2, and what remains can leak at most one bit, x mod 2. That is why the RFC 7919 ffdhe groups used by TLS are safe primes and why protocols built on them often settle for the range check. Do the full check anyway when the private key is long-lived.

On elliptic curves the same mistake is called an invalid-curve attack. Common point addition formulas never use the curve coefficient b, so a point that is not on your curve is silently treated as a point on another curve, one the attacker chose because it has small-order points. The defence is to check that a received point satisfies the curve equation, and to handle the cofactor where it is not 1. X25519 takes a different route: the private scalar is clamped so it is a multiple of 8, which kills the components from Curve25519's cofactor-8 subgroup, and the curve was chosen to be twist-secure. A handful of low-order inputs still yield an all-zero shared secret, and TLS 1.3 requires implementations to check for that value and abort.

Static, semi-static and ephemeral keys

Every small-subgroup attack needs one thing besides a bad group: the victim must reuse its private key. Key lifetime is therefore a security parameter, not just a performance knob.

The last row is where real systems got hurt. The 2020 Raccoon attack targeted TLS 1.2 finite-field DH: the premaster secret had its leading zero bytes stripped before hashing, so its length, and the hash timing, depended on the secret. Exploiting it required the server to reuse a DH secret across connections. TLS 1.3 is not affected because it encodes the shared secret at a fixed length, leading zeros included; fresh key shares on every handshake remove the other precondition, so keep them fresh.

On the wire: key shares and fixed-length secrets

In TLS 1.3 the client's ClientHello carries a key_share extension with one or more public values, one per group it guesses the server will accept; the server answers with exactly one. If the client guessed wrong, the server sends a HelloRetryRequest naming the group it wants, costing a round trip. Sizes, per RFC 8446 and the hybrid draft:

For finite-field groups, RFC 8446 also pads the shared secret itself to the length of p before it enters HKDF-Extract, which closes the Raccoon timing channel. The shared secret then becomes the input keying material for the handshake secret in the key schedule; nothing uses the raw DH output directly as a key. TLS 1.3 internals walks through that schedule. The engineering lesson is general: fix every length, validate every received value, and pass the shared secret through a KDF bound to the transcript.

Failure modes

• Accepting peer-chosen parameters. If the peer can send p and g, it can pick a smooth group. Use named groups only.
• Range check without subgroup check on a DSA-style prime. The range check stops orders 1 and 2 and nothing else; the cofactor subgroups remain open.
• Skipping the all-zero check for X25519. Some libraries return zeros silently; TLS 1.3 and many other protocols require you to abort.
• Variable-length secret encoding. Stripping leading zeros, or using a variable-time big-integer serializer, recreates a Raccoon-style timing channel.
• Error oracles. Returning different errors for bad range, bad subgroup and bad MAC tells the attacker which check fired. Fail every invalid handshake the same way.
• Validation only in the happy path. Resumption, renegotiation, or a secondary protocol endpoint reuses the key but skips the check. Validate at the one function that performs exponentiation with the private key.

Trade-offs

What to do next

1. Run the attack script, then add validate_ffdh_public and confirm the first query is rejected.
2. Inventory every place your code performs DH or ECDH with a private key; note the group, where parameters come from, and how long each key lives.
3. Replace custom or peer-supplied groups with X25519, P-256 or RFC 7919 ffdhe groups.
4. Put validation inside the one function that touches the private key: range and subgroup for finite fields, on-curve checks for Weierstrass curves, all-zero rejection for X25519.
5. Make secret encodings fixed-length and errors uniform, then test with deliberately invalid public values in your CI suite.
6. Plan the hybrid post-quantum key share, measuring ClientHello size against your load balancers and middleboxes.