DH Small-Subgroup Attack — confining the secret to a tiny subgroup to leak it mod that order

When the generator g (or a peer's public value) has small multiplicative order, the shared secret is forced to live inside that small subgroup, so it can only take a handful of values — an attacker, or a careless protocol, ends up leaking the secret exponent modulo that small order.

The signal that gives it away

- The generator g is small, or explicitly stated/verifiable as *not* a primitive root of p. - p-1 factors with at least one small prime q such that g^q ≡ 1 mod p — i.e. g sits in a proper subgroup of order q, not the full group of order p-1. - The server accepts an attacker-supplied public value A (or B) without checking it lies in the intended large-order subgroup, and returns *something* computed from the shared secret — a MAC, a ciphertext, a success/failure bit. That "returns something derived from A^b" is the oracle you need; without it, confinement alone gives you nothing to read back. - Flavor of the challenge: "partial key recovery", a service that lets you query repeatedly, or a DH/ElGamal handshake where parameter validation is visibly absent. - The ECDH analogue of this same signal is a peer point of low order, or a server that never checks the received point actually lies on the intended curve — see Invalid Curve Attack — leaking an ECDH secret through a point nobody checked was on the curve.

How to exploit it

Step 1 — find or manufacture a small-order element. If g itself already has small order q (check pow(g, q, p) == 1 for each small factor q of p-1), you're handed the subgroup for free. If g is a full-order generator but *you* control the public value sent to the peer, manufacture one: h = g0^((p-1)//q_i) has exact order q_i for any factor q_i of p-1.

```python from sympy import factorint

order = None for q in factorint(p - 1): if pow(g, q, p) == 1: # g lies in a subgroup of order q order = q break ```

Step 2 — brute the exponent mod that order. Because order (q) is small, a linear scan (or Baby-Step Giant-Step — the generic meet-in-the-middle solver for a mid-sized discrete log if q is a few thousand rather than a few dozen) recovers secret mod q directly:

``python for x in range(order): if pow(g, x, p) == A: secret_mod_q = x break ``

Step 3 — if you need the full secret, not just one residue: chain small subgroups and CRT. Send several different attacker-chosen elements h_i = g0^((p-1)//q_i), one per small factor q_i of p-1, to a peer that reuses a *static* secret exponent across queries. Each round-trip through the oracle leaks secret mod q_i. Once the product of the collected q_i exceeds the secret's range, Chinese Remainder Theorem — recombining residues across coprime moduli reconstructs it exactly. This live, oracle-driven, repeated-query version is exactly Pohlig-Hellman — solving the discrete log when the group order is smooth executed one prime factor at a time against a real service — see DH Static-Key Reuse — turning a persistent secret exponent into a leaking oracle for the full oracle-loop pattern. Historically this is the Lim-Lee attack (1997) against static/reused DH exponents, and it is the exact scenario RFC 2785 was written to close off for S/MIME. - Degenerate public values (A = 1, A = p-1) are the extreme case of order 1 or 2 — free wins, but treat them as their own signal; see DH Parameter Injection — tamper with (p, g) themselves to make the exchange breakable and DH Man-in-the-Middle — unauthenticated exchange lets an active attacker relay two separate keys for the broader family of tampered-parameter attacks they belong to. - Real-world measurement backs the threat model: the Logjam study (2015) found 8.4% of the most popular HTTPS sites' DH-capable servers reused a static exponent against groups with small-order subgroups, enough to fully recover the private exponent via Lim-Lee once probed.

What does NOT work

- Brute-forcing the full exponent directly, ignoring the subgroup structure. If p-1 is large with only a *small* smooth factor, don't try to brute the whole secret — you only ever recover it modulo the small factor(s) you can confine to. Reaching the full secret requires either enough small factors to CRT past the secret's bit-length, or combining the small residues with another leak (e.g. Hidden Number Problem — recovering a secret from many small-bounded-error samples if the remainder is bounded some other way). If p-1 has no usable small factors at all, this attack line is simply closed. - Expecting one query to reveal the whole secret. A single confinement to order q_i reveals only secret mod q_i. Treating that residue as the secret itself (instead of one CRT input among several) is a common early mistake — always check whether q_i alone is anywhere near the secret's real bit-length before declaring victory. - Trying this against a safe prime with a full-order generator and no oracle. If p = 2q+1 with q prime and g is a genuine primitive root of order p-1, the divisors of p-1 = 2q give exactly two *proper* subgroups: order 2 and order q. The order-2 one is genuinely small — confinement there leaks at most one parity bit, nowhere near enough on its own. The order-q subgroup is not small at all (q is roughly half the bit-length of p), so it gives this attack no foothold: brute-forcing or baby-step-giant-stepping a residue mod q costs as much as attacking the full group. Safe primes are the standard defense precisely because, past that one parity bit, they remove all the small factors this attack needs; if the challenge insists on a safe prime, look elsewhere in the checklist (oracle timing, reused ephemeral keys) rather than forcing small-subgroup here. - Re-querying the same small subgroup repeatedly. Sending h_i for the same factor q_i twice gives the same residue, not new information — the CRT step needs *distinct* prime factors of p-1, not repeated samples of one. - Applying this without an oracle at all. Confinement by itself constrains the *math*, but without something in the response that depends on the shared secret (a MAC, a decryption success/fail, a re-derived key check), there's nothing to read the residue back from — the attack needs the peer to compute-and-leak, not just to accept a low-order value silently.

Related

Diffie-Hellman Fundamentals — what to audit first in any DH challenge Key-Exchange Methodology — triage any DH/ECDH challenge before reaching for heavy DLP machinery Pohlig-Hellman — solving the discrete log when the group order is smooth DH Static-Key Reuse — turning a persistent secret exponent into a leaking oracle DH Parameter Injection — tamper with (p, g) themselves to make the exchange breakable DH Man-in-the-Middle — unauthenticated exchange lets an active attacker relay two separate keys Chinese Remainder Theorem — recombining residues across coprime moduli Baby-Step Giant-Step — the generic meet-in-the-middle solver for a mid-sized discrete log Discrete Logarithm — the factorization of the group order picks your algorithm Invalid Curve Attack — leaking an ECDH secret through a point nobody checked was on the curve Hidden Number Problem — recovering a secret from many small-bounded-error samples