THE GARDEN

Small-Subgroup - Smooth-Prime Static-Key Extraction Attack (Diffie-Hellman)

Updated 13 Sep 2026

• •

  What it is

  • •

    A more resilient version of the static-key generator-substitution attack, for parties that add some validation of caller-supplied Diffie-Hellman parameters (rejecting obviously-wrong public values or suspiciously tiny/composite moduli) but still accept an attacker-chosen prime modulus outright. Constructing a large but deliberately smooth prime $p'$ (one where $p'-1$ factors entirely into small primes, so it passes basic primality checks and doesn't look obviously "dodgy" by size alone) lets an attacker efficiently solve the discrete logarithm $g^b \equiv B' \pmod{p'}$ via Pohlig-Hellman once the target computes and reveals $B'$ under that weak modulus — recovering their real, reused static private key $b$ (or at least $b$ modulo the order of $g$ in that weak group, which is often already large enough to pin down $b$ exactly, since real-world private exponents are typically much smaller than the weak group's own order). With $b$ known, the attacker can go back and compute the real shared secret from an earlier, legitimately-observed exchange under the party's real, strong parameters.

• •

  When to apply

  • •

    A static-key party validates caller-supplied DH parameters just enough to block the crudest tricks (composite moduli, degenerate public values) but doesn't verify anything about how the modulus's own group structure is built — checking a candidate modulus's primality alone doesn't rule out it being deliberately smooth.

• •

  Math

  • •

    Same Pohlig-Hellman mechanism as any smooth-order discrete log — factor $p'-1$ (or more precisely the order of $g$ within $\mathbb{F}_{p'}^\times$, which may be a proper divisor of $p'-1$ if $g$ isn't a full primitive root) into prime powers, solve the discrete log independently modulo each prime-power factor (via baby-step giant-step within each small subgroup), and CRT-combine the results into $b \bmod \text{ord}(g)$.

• •

  Worked example

  • •

    Building a genuinely smooth ~146-bit prime $p'$ from scratch (product of small primes plus one, checked for primality) and computing $g^b \bmod p'$ for a random 20-bit "static secret" $b$: a from-scratch Pohlig-Hellman implementation correctly recovered $b$ modulo the actual order of $g$ in that field — notably, $g=2$ turned out not to be a full primitive root of $p'$ in this trial (its order was only about a quarter of $p'-1$), yet the recovered value still matched $b \bmod \text{ord}(g)$ exactly, and since $b$ itself was smaller than that order, this recovered $b$ exactly, not just a partial residue.

• •

  Python

  • •

    1. build/search for a smooth prime p' (p'-1 = product of many small primes)
    # 2. send it to the target as the modulus; they respond with B' = g^b mod p'
    # 3. factor ord(g) [often just p'-1, verify] into prime powers
    # 4. Pohlig-Hellman: solve g^b = B' independently mod each prime-power factor via BSGS, then CRT-combine
    b_recovered = pohlig_hellman(g, B_prime, p_prime, ord_g)
    # 5. go back to the REAL, strong (p, A) pair observed earlier and compute the true shared secret:
    real_shared_secret = pow(A_real, b_recovered, p_real)
    

• •

  SageMath

  • •

    This is the practical, standard route — discrete_log() in Sage runs Pohlig-Hellman automatically once it can factor the group order, rather than needing a hand-rolled BSGS+CRT implementation:

  • •

    F = GF(p_prime)
    b_recovered = discrete_log(F(B_prime), F(g))
    

• •

  Related

  • •

    Diffie-Hellman Downgrade Attack (Export-Grade - Weak Group Negotiation)

  • •

    Static-Key Generator Substitution Attack (Diffie-Hellman)

• •

  Cards

  • •

    Why does checking that a caller-supplied modulus is prime fail to prevent this attack?

    • •

      Primality alone says nothing about how smooth p-1 is — a prime can be entirely legitimate-looking while still having a group order that factors completely into small primes, making its discrete log problem tractable.

  • •

    Why does recovering the target's static private key from one weak-group exchange compromise other, legitimate exchanges too?

    • •

      Because the private key is static (reused across sessions) rather than fresh per exchange — once known, it can be applied directly to any previously-observed real public value to compute that session's true shared secret.

◌ Explore connections in Graph view