Singular Curve Attack — the zero-discriminant signal that collapses ECDLP to a field problem

A curve with zero discriminant (4a^3 + 27b^2 ≡ 0 mod p) is not a valid elliptic curve — its smooth points form a group isomorphic to the additive or multiplicative group of F_p (or F_{p^2}), which turns Elliptic Curve Discrete Logarithm Problem — the curve order's factorization picks your attack into an easy field computation instead of a hard curve problem.

The signal that gives it away

- Discriminant check comes back zero. Compute 4*a**3 + 27*b**2 % p yourself before trusting the challenge's parameters — don't assume the given (p, a, b) describe a real curve just because the challenge hands you P and Q = k*P on it. - The construction itself refuses. In Sage, EllipticCurve(GF(p), [a, b]) raises an error on a singular cubic. That error is not a bug to route around — it *is* the signal. Treat "the curve constructor throws" as diagnostic, not as an obstacle to debug past. - The challenge still operationally hands you P and Q = k*P defined on the singular cubic even though it fails Sage's own validity check — the arithmetic on the smooth part of the curve still works, it's just isomorphic to something much weaker than a genuine EC group.

How it's exploited

1. Find the singular point (the double or triple root of the cubic) and translate it to the origin so the curve becomes y^2 = x^2*(x + c). 2. Cusp case (triple root, c = 0): the smooth points map to the *additive* group of F_p via (x, y) -> x/y. Recovery is pure division, no discrete log needed at all: k = (x_Q/y_Q) / (x_P/y_P) (mod p) 3. Node case (distinct roots, c != 0): let t = sqrt(c). Map each point to u = (y + t*x)/(y - t*x); the group law becomes multiplication, so recovering k is a discrete log in a multiplicative group: k = log_{u_P}(u_Q), solved with Discrete Logarithm — the factorization of the group order picks your algorithm / Pohlig-Hellman — solving the discrete log when the group order is smooth. - If `c` is a quadratic residue mod `p`, t exists in F_p and the target group is F_p^*. - If `c` is a non-residue, t only exists in F_{p^2} — you must lift the computation into F_{p^2} and solve the discrete log there instead. This is the operational trap: naively staying in F_p when c is a non-residue gives inconsistent or nonsensical results, not a clean failure, so it's easy to burn time before realizing the extension is required. - Field-tested note: the multiplicative group order in the extension case, p^2 - 1, is usually smooth enough for Pohlig-Hellman — solving the discrete log when the group order is smooth to finish quickly — check its factorization before reaching for anything heavier.

``python # node case, after shifting the singular point to the origin t = GF(p)(c).sqrt() # or a root in GF(p^2) if c is a non-residue def m(P): x, y = P return (y + t*x) / (y - t*x) k = discrete_log(m(Q), m(P)) # in GF(p)* or GF(p^2)* ``

Related methodology: the discriminant check is one of a small set of curve-validity checks (order, discriminant, point-on-curve) that route a challenge to the correct ECC sub-attack — see Elliptic Curve Fundamentals — the audit that routes to the right ECC attack for the full triage.

What does NOT work

- Debugging the "singular curve" construction error as if it were a bug in your own code or in the challenge. It's the intended signal. If EllipticCurve(GF(p), [a, b]) fails, stop and check the discriminant — don't try to "fix" the parameters or assume a typo. - Running standard ECDLP tooling (`E.discrete_log`, generic baby-step-giant-step over the curve group) directly on a singular curve. There is no well-defined curve group of the usual order to compute a discrete log in — the curve fails Sage's own group-law setup, so any attack that assumes a legitimate EllipticCurve object and its .order() is a dead end. The whole point is to leave the curve group entirely and work in the field instead. - **Confusing this with Smart Attack — the anomalous-curve signal that turns ECDLP into polynomial time. Both are "special structure makes ECDLP easy," but the trigger condition is different and mutually exclusive in practice: singular-curve applies when the discriminant is zero (the object isn't a valid curve at all), while Smart's attack applies to a genuine, smooth curve whose order happens to equal the field characteristic (`#E == p`, anomalous). Check discriminant first, since a singular check is cheaper and forecloses the anomalous case. - Confusing this with Invalid Curve Attack — leaking an ECDH secret through a point nobody checked was on the curve.** Invalid-curve abuses an oracle that fails to validate that a *supplied point* lies on the *intended, valid* curve, letting the attacker swap in a different (still smooth) weak curve. Singular-curve is about the curve parameters themselves being degenerate from the start — there's no point-substitution trick involved, and no oracle is required. - **Assuming the node case always lands in F_p^* without checking the residuosity of c first.** Skipping that check is the single most time-costly mistake in this attack: the arithmetic looks like it's running fine, but the recovered k will be wrong because the correspondence only holds in the field extension the residue actually lives in.

Related

Elliptic Curve Discrete Logarithm Problem — the curve order's factorization picks your attack Discrete Logarithm — the factorization of the group order picks your algorithm Pohlig-Hellman — solving the discrete log when the group order is smooth Elliptic Curve Fundamentals — the audit that routes to the right ECC attack Smart Attack — the anomalous-curve signal that turns ECDLP into polynomial time Invalid Curve Attack — leaking an ECDH secret through a point nobody checked was on the curve