Key-Exchange Methodology — triage any DH/ECDH challenge before reaching for heavy DLP machinery

A checklist-driven decision tree for any shared-secret handshake challenge — classic DH, ElGamal, ECDH/X25519, or a custom "key exchange" service — that routes you to the right specific attack before you waste time on a raw discrete-log solve.

The signal that betrays it

Any challenge exposing a shared-secret handshake: public values A/B (or Q_A/Q_B on a curve), a generator g (or base point), and usually a live oracle you can query. The tell that this page — not a raw DLP solver — is the right entry point is that the challenge gives you *more than just the numbers*: it gives you a protocol with moving parts (parameters you can influence, a value you can send, a key reused across queries). The math is rarely broken head-on; you win by auditing parameters, identity, and reuse before computing anything.

How it's exploited

Run the checklist top to bottom — in our field notes this ordering matters, because each step is cheaper to test than the next and a hit short-circuits the rest:

```text 1. Parameters: is p prime? is p-1 smooth? -> Pohlig-Hellman — solving the discrete log when the group order is smooth 2. Generator/peer value: small order? degenerate (0, 1, p-1)? -> DH Small-Subgroup Attack — confining the secret to a tiny subgroup to leak it mod that order 3. Composite modulus? factorable n? -> DH Composite Modulus — splitting the discrete log by CRT when the modulus isn't prime 4. Can you tamper p, g, or the public keys? -> 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 5. Static secret + a repeatable oracle? -> DH Static-Key Reuse — turning a persistent secret exponent into a leaking oracle 6. Reused/biased ephemeral k? -> Hidden Number Problem — recovering a secret from many small-bounded-error samples 7. ECDH/X25519? low-order / twist / clamp -> X25519 Basics — recognizing Curve25519 ECDH and where it actually breaks ```

The first check is a two-line script and it's the highest-value one to run first — it decides whether you're even looking at a hard problem:

``python from sympy import isprime, factorint assert isprime(p) print(factorint(p - 1)) # smoothness drives the whole choice ``

If p - 1 factors into small primes, Pohlig-Hellman — solving the discrete log when the group order is smooth solves the discrete log directly by splitting it into one small sub-problem per prime-power factor of the order and CRT-recombining — this is documented to work even for p well over 1024 bits, because cost scales with the *largest prime factor of the order*, not with p itself, which public sources on smooth-order groups confirm as the reason "big prime" alone is not a security guarantee.

Step 2 is cheap and often skipped by challenge authors: check whether the generator or the peer's public value sits in a small subgroup, or is one of the degenerate values 0, 1, or p-1. A peer value of 1 forces the shared secret to 1 outright; a value of p-1 (i.e. -1 mod p) forces it to ±1 depending on the parity of the exponent. Neither requires any discrete-log machinery — just recognizing the value. This is the "free" case of what public sources call small subgroup confinement: an attacker (or an already-degenerate legitimate value) forces the computed secret into a subgroup small enough to brute-force, and the private exponent leaks modulo the subgroup's order; repeat with several small-order values and CRT-recombine, exactly as DH Static-Key Reuse — turning a persistent secret exponent into a leaking oracle describes for a queryable oracle.

Step 4 matters specifically when the *transport* — not just the math — is attacker-influenced: if you can rewrite p, g, or either public key in transit (not just observe them), you don't need any weakness in the numbers the server picked — you inject your own smooth p, order-1 g, or degenerate public value yourself (DH Parameter Injection — tamper with (p, g) themselves to make the exchange breakable), or run a full relay attack (DH Man-in-the-Middle — unauthenticated exchange lets an active attacker relay two separate keys). This class exists because bare Diffie-Hellman carries no authentication of p, g, or the public values by design — public sources on DH's man-in-the-middle weakness confirm this is a structural property of the unauthenticated protocol, not an implementation bug, so the *first* question for any DH challenge is really "is anything here signed or pinned?" before auditing the numbers at all.

Step 5 and 6 both come from the same underlying pattern (a secret reused across observations leaks structure), but the mechanism differs: step 5 is "the server keeps reusing its own static exponent and answers repeated queries" (leaks residues mod small subgroup orders you feed it — see DH Static-Key Reuse — turning a persistent secret exponent into a leaking oracle); step 6 is "the *ephemeral* per-session k is reused or partially known/biased across sessions" which turns the samples into a Hidden Number Problem — recovering a secret from many small-bounded-error samples solved by lattice reduction, not brute force. Don't conflate them: step 5's fix (query more small-order values, CRT) does nothing for step 6's problem, and vice versa.

Step 7 exists because on X25519/Curve25519 the classical pitfalls above (smooth-order subgroups, degenerate values in the algebraic sense of steps 1–3) don't map onto a fixed, already-vetted curve — but that's not the same as the math being immune to cofactor/twist issues. RFC 7748 is explicit that a low-order input point eliminates the other party's private-key contribution from the computed shared secret: feed one in and you learn (or force) the result without ever touching the peer's real scalar. Nothing about the curve's design makes this hard to hit "by accident" — what actually neutralizes it is implementation discipline: correct scalar clamping and rejecting (or explicitly handling) low-order/twist input points. So field-tested experience says: don't waste time hunting for smooth-order primes on a Montgomery-curve challenge — the attack surface moves entirely to protocol misuse: does the implementation reject low-order input points, does it clamp the scalar correctly, does it reuse a static scalar across untrusted peers. See X25519 Basics — recognizing Curve25519 ECDH and where it actually breaks for the specific checks.

If none of the seven checks fire, the intended vulnerability is *not* in the DH math at all — pivot to the broader triage in Cryptanalysis Methodology — classify the family before you reach for an attack (RNG weakness, a side channel, or a logic bug in how the shared secret is used downstream, e.g. as an AES key with no KDF).

What does NOT work

- Jumping straight to a generic DLP solver (baby-step giant-step, index calculus) without running step 1 first. If p-1 is smooth, Pohlig-Hellman — solving the discrete log when the group order is smooth is orders of magnitude faster and is what tools like SageMath's discrete_log() will pick automatically once it detects a composite group order — running the generic algorithm anyway just burns wall-clock time solving a problem that decomposes trivially. - Assuming "the prime is huge" means the exchange is safe. Security depends on the order of g (equivalently, the smoothness of p-1), not the bit-length of p. A large p with smooth p-1 can be far weaker in practice than a much smaller safe prime, because Pohlig-Hellman — solving the discrete log when the group order is smooth's cost tracks the *largest prime factor of the order*, not the bit-length of p — bit-length alone is not a security guarantee. - Treating small-subgroup and hidden-number-problem leaks as the same fix. They both stem from "reuse leaks structure," but one is solved by CRT over brute-forced small residues, the other needs a lattice/HNP solver — trying to CRT your way through biased-nonce samples does not work; trying to build a lattice out of a handful of small-subgroup residues is overkill and usually won't even set up correctly (too few samples, wrong bound shape). - Auditing only `p` and `g` and ignoring the transport. If the challenge lets you tamper with values in flight, the numbers the *server* chose can be perfectly fine — you supply the weak ones yourself via DH Parameter Injection — tamper with (p, g) themselves to make the exchange breakable or a relay via DH Man-in-the-Middle — unauthenticated exchange lets an active attacker relay two separate keys. A parameter audit that only inspects what the server printed misses this whole class. - Applying this checklist un-adapted to X25519/ECDH. The subgroup/smoothness questions (steps 1–3) don't map onto a fixed, already-vetted curve the same way; port straight to step 7 and X25519 Basics — recognizing Curve25519 ECDH and where it actually breaks instead of hunting for a "smooth order" on a curve chosen specifically to not have one.

Related

Cryptanalysis Methodology — classify the family before you reach for an attack Diffie-Hellman Fundamentals — what to audit first in any DH challenge Pohlig-Hellman — solving the discrete log when the group order is smooth DH Small-Subgroup Attack — confining the secret to a tiny subgroup to leak it mod that order DH Composite Modulus — splitting the discrete log by CRT when the modulus isn't prime 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 DH Static-Key Reuse — turning a persistent secret exponent into a leaking oracle Hidden Number Problem — recovering a secret from many small-bounded-error samples X25519 Basics — recognizing Curve25519 ECDH and where it actually breaks