DH Static-Key Reuse — turning a persistent secret exponent into a leaking oracle

When one party keeps the same secret exponent b across many exchanges and echoes anything derived from the shared secret, every exchange becomes another query in a live oracle on that single unknown — repeated small-subgroup confinement against a *static* key leaks b one residue at a time, and Chinese Remainder Theorem — recombining residues across coprime moduli recombines the residues into the whole secret. This is the historical Lim-Lee attack (1997): the one-shot version leaks a few bits; reusing the key turns it into a full key-recovery engine.

The signal that gives it away

- A persistent endpoint or service, not a fresh handshake per connection — the same public value B (or its effect) reappears across sessions, or the challenge literally states "the key never changes." - You can query the service repeatedly with a public value you control, and it returns anything computed from the shared secret: a MAC/tag, a ciphertext, a decrypt success/fail bit, even a timing difference. Without something to read back per query, confinement alone gives you nothing — see DH Small-Subgroup Attack — confining the secret to a tiny subgroup to leak it mod that order for that prerequisite. - p-1 factors into several distinct small primes (check with factorint(p-1)), not just one — a single small factor only ever gives one residue, not the key. If p is a safe prime (p = 2q+1, g full order), this line is closed before it starts: see "What does NOT work" below. - The ECDH/X25519 flavor of the same signal: a service that accepts a fresh low-order peer point on every call while reusing the same private scalar underneath — see X25519 Basics — recognizing Curve25519 ECDH and where it actually breaks.

How to exploit it

For each small prime factor q_i of p-1, manufacture an element of exact order q_i, send it in as your public value, and read the oracle's response to recover b mod q_i:

```python from sympy import factorint from sympy.ntheory.modular import crt

res, mods = [], [] for q in small_factors(factorint(p - 1)): # distinct small prime factors of p-1 h = pow(g, (p - 1) // q, p) # h has exact order q out = oracle(h) # peer computes h^b mod p, leaks a function of it for x in range(q): # q is small: linear scan is fine if pow(h, x, p) == out: res.append(x); mods.append(q) break

b, _ = crt(mods, res) # valid once prod(mods) exceeds b's real range ```

Operational points from field use: - Distinct factors only. Querying the same q_i twice returns the same residue — it doesn't narrow anything down. Budget queries across *different* q_i, not repeats of one. - The stopping condition is concrete, not vibes. CRT gives a unique answer only once prod(q_i) exceeds the actual bit-range of b (or of p, if you have no tighter bound). Stop collecting factors and CRT-combine as soon as that product crosses the threshold — collecting more than needed just wastes oracle calls, collecting less gives an ambiguous b mod prod(q_i) with multiple candidates. - This is Pohlig-Hellman driven live, one prime at a time. Pohlig-Hellman — solving the discrete log when the group order is smooth normally works offline against a single known (g,h) pair; here each factor requires a fresh round-trip through a real oracle, so query budget/rate limits matter in a way the offline algorithm doesn't — plan the factor list before you start burning queries. - Brute-forcing `x` in `range(q)` only scales while `q` is genuinely small. For q in the low thousands it's instant; push into the millions and swap the linear scan for Baby-Step Giant-Step — the generic meet-in-the-middle solver for a mid-sized discrete log on that sub-DLP instead of blindly looping. - X25519 static-scalar reuse is the same idea with a much thinner yield. Curve25519 has exactly 8 points of low order (the cofactor-8 subgroup), not a rich set of diverse smooth factors like a poorly-chosen DH p-1. Reusing a static scalar against repeated low-order peer points caps the leak at b mod 8 — three bits, nowhere near enough to CRT a ~252-bit clamped scalar on its own. Treat it as a partial-leak signal to feed into a broader attack (e.g. a Hidden Number Problem — recovering a secret from many small-bounded-error samples lattice setup combining it with other bias), not a self-contained Lim-Lee recovery. See X25519 Basics — recognizing Curve25519 ECDH and where it actually breaks. - Field measurement backs the threat model: a 2016 survey found roughly 3% of HTTPS servers doing DH reused static exponents against groups with exploitable small-order subgroups — enough to fully recover the private exponent via exactly this technique once probed.

What does NOT work

- Expecting a single query to hand you the key. One confinement round only ever yields b mod q_i for that one factor. Treating that residue as the answer (instead of one CRT input among several) is the most common early mistake — check the factor's size against the key's real bit-length before declaring victory. - Running this against a genuinely ephemeral exchange. If the peer draws a fresh b per session (textbook DHE/ECDHE), each query targets a *different* secret — the residues you collect don't belong to the same unknown and CRT-combining them produces garbage. The attack strictly requires a static, reused exponent; ephemeral rotation is the standard, effective defense against it. - Ignoring public-key validation. A peer that checks an incoming public value actually has the intended large order (per RFC 2785: confirm y^q mod p == 1 for the expected subgroup order q) rejects every attacker-chosen small-order element before it ever reaches the oracle computation — the attack is closed at the first query, not after enough residues accumulate. - Trying it on a safe prime with no oracle-side leak diversity. If p = 2q+1 with q prime and g a genuine primitive root, p-1 = 2q has proper subgroups of order 1, 2, and q — but q is roughly half the bit-length of p, far too large to manufacture or brute-force as a confinement target, so the only *small* proper subgroup usable here has order 2 — repeated queries leak at most one bit total, no matter how many times you ask. If the modulus is safe, this line is closed; look elsewhere in the checklist (timing, biased ephemeral nonces via Hidden Number Problem — recovering a secret from many small-bounded-error samples) rather than forcing small-subgroup confinement here. - Re-querying the same small factor to "confirm" it. It doesn't add information and just burns query budget — spend queries on *new* distinct factors of p-1, not repeats. - Assuming X25519 reuse behaves like classic DH reuse. As above: the cofactor-8 ceiling means pure repeated-query CRT recovery that works beautifully against a badly chosen DH prime simply doesn't reach far enough on Curve25519 by itself.

Related

DH Small-Subgroup Attack — confining the secret to a tiny subgroup to leak it mod that order Pohlig-Hellman — solving the discrete log when the group order is smooth Chinese Remainder Theorem — recombining residues across coprime moduli Hidden Number Problem — recovering a secret from many small-bounded-error samples 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 X25519 Basics — recognizing Curve25519 ECDH and where it actually breaks 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