Invalid Curve Attack — leaking an ECDH secret through a point nobody checked was on the curve

An oracle performs scalar multiplication secret * P on an attacker-supplied point P without checking that P actually satisfies the curve equation, so an attacker can hand it points from other, deliberately weak curves and read the secret back through small-subgroup confinement.

The signal that gives it away

- The challenge exposes curve parameters p, a, b (explicitly, or via a named curve like secp256k1/P-256) and an ECDH-style oracle: send a point, get back something derived from secret * P — a decrypted flag, a MAC, a re-derived-key check, or even just a success/failure bit. - In whitebox/reversing challenges, the receiving code builds a curve point directly from attacker-supplied (x, y) and never asserts (y^2 - x^3 - a*x - b) % p == 0. Sometimes it checks x, y ∈ [0, p-1] and stops there — that's "partial validation," and it is exactly the gap this attack lives in. - The deeper tell: the addition/doubling code itself never references b. Short-Weierstrass point addition and doubling use only a (in the doubling slope λ = (3x² + a) / (2y)) and the point coordinates — b never appears in the arithmetic, only in the membership check. If that check is missing, the implementation is *structurally incapable* of noticing it's computing in the wrong group, because b never entered the computation to begin with. - A secret that is static/reused across queries (same session key, same server-side long-term ECDH key answering repeatedly) — a single query only ever leaks one residue; combining residues needs the oracle to be poked more than once with the same secret behind it.

How to exploit it

Step 1 — build a family of sibling curves that share `a` and `p` with the target. The receiving code almost always hardcodes a and p (they're curve-wide constants baked into the arithmetic); only b is implicit in the point you send. So don't search for random weak curves — construct them on demand: pick any x, y you like, then solve `` b' = (y**2 - x**3 - a*x) % p ` This *guarantees* (x, y) lies on E' : y^2 = x^3 + a*x + b', a valid short-Weierstrass curve with the same a and p as the target, for whichever b'` falls out. Build several candidate curves this way and check their group order.

Step 2 — find a sibling curve whose order has a useful small prime factor `q`. ``python for bp in candidate_bs: Ep = EllipticCurve(GF(p), [a, bp]) for q in small_prime_factors(Ep.order()): Pq = (Ep.order() // q) * Ep.gen(0) # a point of exact order q on E' # send Pq to the oracle as if it were a point on the real curve ``

Step 3 — read the residue back. The oracle computes R = secret * Pq using its own (unchecked) arithmetic, which — because b never entered the computation — happily returns a point that really does live in the order-q subgroup of E'. Recover secret mod q with a linear scan for tiny q, or Baby-Step Giant-Step — the generic meet-in-the-middle solver for a mid-sized discrete log once q runs into the thousands: ``python res.append((discrete_log(R, Pq, ord=q, operation='+'), q)) ``

Step 4 — repeat with pairwise-coprime small primes, then combine. Query enough distinct sibling curves/prime factors that the product of the q_i exceeds the secret's bit-length, then Chinese Remainder Theorem — recombining residues across coprime moduli: ``python secret = crt([r for r, _ in res], [q for _, q in res]) ` For a ~256-bit curve (secp256k1, P-256, and most CTF-sized curves) this typically means chaining many small primes across several different b'` choices — the same accumulate-until-product-exceeds-the-secret pattern as DH Small-Subgroup Attack — confining the secret to a tiny subgroup to leak it mod that order, because this *is* Pohlig-Hellman — solving the discrete log when the group order is smooth executed one prime factor at a time through a live oracle, just over an elliptic-curve group instead of a multiplicative one.

What does NOT work

- Varying `a` instead of (or in addition to) `b`. The vulnerable arithmetic hardcodes a; a point from a curve with a different a isn't processed the way the exploit needs, because the receiver's doubling/addition formulas were written for a fixed a. Only vary b — derived on the fly from your chosen (x, y) as above — never touch a. - Expecting one weak curve to leak the whole secret. A single order-q subgroup only ever reveals secret mod q. On a full-size curve q is always tiny relative to the secret, so treating one residue as the answer is the same beginner mistake as in small-subgroup DH: it's one CRT input among many, not the secret itself. - Conflating this with a twist attack. A twist attack targets the OTHER curve implicit in the same short-Weierstrass equation (its quadratic twist) via a genuinely on-curve-equation-satisfying y-coordinate substitute — it doesn't touch b at all and doesn't require the receiver to skip validation the same way. They share the "small-subgroup confinement" endgame but the setup is different; don't reach for the twist-attack construction when the tell is a missing (y^2 - x^3 - a*x - b) % p == 0 check, and vice versa. - Attacking a server that performs full public-key validation. If the target checks the curve equation (and, per NIST SP 800-56A guidance, non-identity and — for non-cofactor ECDH — subgroup membership), this line is closed; mainstream libraries with up-to-date point validation (modern OpenSSL/BoringSSL, patched BouncyCastle after the disclosures this attack triggered) are not vulnerable. Confirm the "partial validation only" gap actually exists before investing time — don't assume it. - Linear brute force once `q` stops being tiny. Fine for q in the tens or low hundreds; switch to Baby-Step Giant-Step — the generic meet-in-the-middle solver for a mid-sized discrete log once a sibling curve's smooth factor climbs into the thousands, or the per-query cost dominates the whole exploit. - Trying this against session-ephemeral secrets. If the peer generates a fresh secret per handshake, each query is a dead end in isolation — there is no way to CRT-combine residues from different secrets. The attack needs a *reused* secret across queries, exactly as in DH Static-Key Reuse — turning a persistent secret exponent into a leaking oracle; confirm the oracle is answering with the same long-term/static key before building out the whole small-prime chase. - Re-sending the same sibling curve/prime twice. Like the DH analogue, repeat queries against the same q_i give the same residue, not new information — each CRT input needs a genuinely distinct prime factor from a genuinely distinct (or at least distinct-order) sibling curve.

Related

Elliptic Curve Discrete Logarithm Problem — the curve order's factorization picks your attack Elliptic Curve Fundamentals — the audit that routes to the right ECC attack 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 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 Static-Key Reuse — turning a persistent secret exponent into a leaking oracle Singular Curve Attack — the zero-discriminant signal that collapses ECDLP to a field problem Smart Attack — the anomalous-curve signal that turns ECDLP into polynomial time