How Elliptic Curves and Diffie-Hellman Break in Real Life: The Discrete Log Never Fell

1. Seven Breaks, One Unbroken Problem#

On a well-chosen elliptic curve, the best attack anyone has ever fielded against the discrete logarithm is a square-root-time random walk that has barely moved since the 1970s ^[1][2]. No deployed P-256, Curve25519, or secp256k1 key, and no standard 2048-bit Diffie-Hellman group, has ever had its discrete log solved in public. By every measurement we can make, the mathematics is holding.

And yet. PlayStation 3 consoles were jailbroken ^[3]. Android Bitcoin wallets were emptied ^[4]. Tamper-resistant TPMs certified to government standards surrendered their signing keys ^[5]. Windows accepted forged certificates that chained to a counterfeit authority ^[6]. Live TLS sessions were downgraded and decrypted in transit ^[7]. Every one of those systems ran the discrete-log math exactly as specified. The math was never where they broke.

That is the paradox this article resolves, and the resolution fits in one sentence: none of these attacks solved a discrete logarithm. Each attacked a layer the math depends on but does not control. There are exactly three such layers, and they organize everything that follows:

• The per-signature nonce -- the throwaway secret ECDSA needs for every signature. PS3, Android, Minerva, TPM-Fail, and LadderLeak all landed here.
• The curve and certificate parameters -- which curve, and whose generator, you are actually talking to. CurveBall landed here.
• The negotiated strength -- how strong a key exchange two parties agree to use before they exchange anything. Logjam landed here.

The discrete-logarithm assumption protects the private key against being directly computed -- and nothing else. "Nobody solved the discrete log" and "somebody recovered the private key" are not contradictory statements, because the discrete-log problem (genuinely hard) and a discrete-log deployment (a nonce, some parameters, a negotiation) are different things. Every real break in this article lives in the gap between them.

A note on scope. This piece treats the hardness of the elliptic-curve discrete logarithm as a black box: assume it holds, and watch everything around it fail. The structural mathematics of curve choice -- why one curve is weak and another is strong, how the number field sieve and Shor's algorithm actually work -- belongs to a companion article, "How the Discrete Log Would Break: Elliptic Curves, Finite Fields, and Why Curve Choice Is the Weak Part." Here, we assume the strongbox is uncrackable and ask how the key kept getting out anyway.

To see why a hard problem protects so little, you first have to see exactly what it promises -- and what it quietly leaves to the deployment.

2. What the Math Actually Promises#

In 1976, Whitfield Diffie and Martin Hellman reduced the ancient problem of exchanging a secret over an open wire to a single piece of hard arithmetic: the discrete logarithm ^[8]. Two parties each pick a private exponent, exchange public powers of a shared generator, and combine them into a key that an eavesdropper cannot reconstruct without solving for one of those exponents.

Nine years later, Victor Miller and, independently, Neal Koblitz moved the same hard problem onto elliptic curves ^[9][10]. Koblitz argued the curve version was "likely to be harder than the classical discrete logarithm problem" ^[10] -- which is why a 256-bit curve buys security that a finite field needs thousands of bits to match. A clean, triumphant origin. So where did the promise leak?

Signatures are where the story starts, because signatures introduce a second secret. The Elliptic Curve Digital Signature Algorithm (ECDSA) signs a message hash z under a long-term private key d by generating a fresh random value k, computing a point kG, taking its x-coordinate as r, and producing:

$s = k^{-1}\,(z + r\,d) \bmod n$

where n is the order of the group. The verifier only ever sees (r, s). The private key d is buried inside, protected by the discrete-log assumption -- nobody can read d off the signature. But look at what else is in that equation.

The discrete-log assumption guards d against being computed from the public key. It says nothing whatsoever about three things the assumption quietly depends on but does not itself enforce:

1. The nonce k must be secret, uniform, and unique. The math assumes a perfect k and never checks that you supplied one.
2. The parameters must be the standard, named ones. The math assumes you are on the curve you think you are, with the generator you think you have.
3. The negotiated strength must not be crippled or shared. The math assumes the group you agreed to use is actually strong.

Each of those is the deployment's responsibility, not the primitive's. And each one became a pillar of failure.

flowchart TD
DLP["(EC)DLP is hard: d cannot be computed from the public key dG"]
DLP --> N["Depends on the per-signature nonce k"]
DLP --> P["Depends on the curve and certificate parameters"]
DLP --> G["Depends on the negotiated group strength"]
N --> P1["Pillar 1 nonce: PS3, Android, Minerva, TPM-Fail, LadderLeak"]
P --> P2["Pillar 2 validation: CurveBall"]
G --> P3["Pillar 3 downgrade: Logjam"]

The curve migration itself is not our subject. Miller (1985) and Koblitz (1987) are mentioned here only to fix the primitive's birth. Whether a particular curve is structurally weak -- anomalous curves, small embedding degrees, the number field sieve, Shor's algorithm -- is the structural mathematics deferred to the companion article. This article assumes the curve is strong and attacks everything around it. The math guards the key against being computed. It says nothing about the key being handed over. Three contracts govern that handover, and each one broke.

3. Three Contracts the Deployment Signs and Never Reads#

Every cryptographic deployment signs a contract it never reads. There are three clauses, one for each layer the math leans on, and the fine print on all three is where real products sank.

The nonce contract: k must be fresh#

Take the ECDSA signing equation and ask the cruelest possible question: what if k is not unique? Suppose two different messages, with hashes z1 and z2, are signed under the same nonce k. Because r is the x-coordinate of kG, the same k produces the same r in both signatures. Now write them down side by side:

$s_1 = k^{-1}(z_1 + r\,d), \qquad s_2 = k^{-1}(z_2 + r\,d) \pmod n$

Subtract. The rd term is identical in both, so it cancels, and k falls straight out:

$s_1 - s_2 = k^{-1}(z_1 - z_2), \qquad k = \frac{z_1 - z_2}{s_1 - s_2} \bmod n$

Once you know k, the first equation has exactly one unknown left, and you solve for the private key by hand:

$d = \frac{s_1\,k - z_1}{r} \bmod n$

No lattice. No side channel. No discrete log. Two signatures that share a nonce are two linear equations in two unknowns, and a middle-schooler with modular arithmetic can finish the job.

The contract, then, is strict: k must be secret, statistically uniform, and never reused or partially leaked. Break any word of that clause and the algebra above (or its statistical cousin, later) takes your key.

The parameter contract: talk to the curve you think you are#

The second clause is about identity. A named curve -- "P-256," "secp256k1" -- is an agreement to use one specific set of domain parameters, and in particular one specific generator, the base point G that every public key is measured against.

The contract: never trust attacker-supplied explicit parameters. A validator that checks a public point but not the generator it was measured against has, in effect, let the attacker choose the ruler and then declared the measurement correct. That is precisely the door CurveBall walked through ^[6].

The negotiation contract: agree to strength, not to a museum piece#

The third clause governs what two parties agree to before they exchange anything. In ephemeral Diffie-Hellman, each side picks a fresh secret per connection, which is supposed to guarantee that compromising one session cannot retroactively expose others.

The contract: the negotiated group must be strong, fresh, and unshared. The fine print that sank it: many servers ship the same standardized 512-bit prime, so breaking one group breaks all of them at once ^[7]. A fresh ephemeral exponent does not save you when the prime itself is weak and shared.

Three contracts, three clauses of fine print. Over fifteen years, every clause was breached in the field -- and the breaches fall into exactly three piles.

4. The Failure Catalog: Seven Breaks, Three Layers, One Shape#

None of the seven incidents below solved a discrete logarithm. Every one of them recovered a private key or forged a trusted one. Watch where each attack actually landed -- because the landing spot, not the marquee name, is the whole lesson.

timeline
title EC and DH in the field, the assumption versus the breaks
1976 : Diffie-Hellman, the assumption is born
1985-1987 : Miller and Koblitz, the curve migration
2010 : PS3 constant nonce, reuse
2013 : Android SecureRandom, reuse
2015 : Logjam, downgrade plus shared-prime NFS
2019-2020 : Minerva and TPM-Fail, lattice bias
2020 : LadderLeak, Bleichenbacher-Fourier sub-bit : CurveBall, unvalidated generator

Here is the entire corpus on one page. The rightmost column is the thesis in a single word, repeated seven times.

Six "No"s and one heavily qualified "Yes." Let us walk the three pillars in turn.

Pillar 1a: the nonce, reused (certain, from two signatures)#

In December 2010, at the 27th Chaos Communication Congress, the group fail0verflow presented "Console Hacking 2010" and revealed that Sony had signed PlayStation 3 firmware using ECDSA with a constant nonce ^[3]. Not a weak random k. The same k, every time. Every signature Sony ever produced shared a nonce with every other, which means any two of them collapse to the algebra from Section 3. Keep two PS3 events distinct. fail0verflow's 27C3 talk exposed the constant-nonce mechanism. George Hotz released a separate PS3 root key weeks later, in January 2011 ^[11]. The teaching case -- a hardcoded constant nonce -- is fail0verflow's. The console's chain of trust, the thing Sony spent years engineering, came apart because a random number generator was told to always return the same number.

flowchart LR
A["Sig 1: s1 = k^-1 (z1 + r d)"] --> C["Same k means same r"]
B["Sig 2: s2 = k^-1 (z2 + r d)"] --> C
C --> D["Subtract, k cancels: k = (z1 - z2) / (s1 - s2) mod n"]
D --> E["Solve for d = (s1 k - z1) / r mod n"]
E --> F["Private key recovered, no discrete log solved"]

This is not a metaphor. Here is the recovery, executable. Two signatures share a nonce, and a dozen lines of BigInt arithmetic reproduce the private key exactly:

// secp256k1 group order
const n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141n;
const mod = (a, m) => ((a % m) + m) % m;

// Modular inverse via the extended Euclidean algorithm
function inv(a, m) {
let [oldr, r] = [mod(a, m), m];
let [olds, s] = [1n, 0n];
while (r !== 0n) {
  const q = oldr / r;
  [oldr, r] = [r, oldr - q * r];
  [olds, s] = [s, olds - q * s];
}
return mod(olds, m);
}

// A victim signs two different messages with the SAME nonce k
const d  = 0x00c0ffee1234567890abcdef00c0ffee1234567890abcdef00c0ffee12345678n; // secret
const k  = 0x0000deadbeef0000feed0000deadbeef0000feed0000deadbeef0000feed0001n; // reused nonce
const r  = mod(0x1122334455667788112233445566778811223344556677881122334455667788n, n);
const z1 = 0x1111111111111111111111111111111111111111111111111111111111111111n;
const z2 = 0x2222222222222222222222222222222222222222222222222222222222222222n;
const s1 = mod(inv(k, n) * mod(z1 + mod(r * d, n), n), n);
const s2 = mod(inv(k, n) * mod(z2 + mod(r * d, n), n), n);

// The attacker sees only (r, s1, z1) and (r, s2, z2). Recover k, then d.
const kRec = mod((z1 - z2) * inv(mod(s1 - s2, n), n), n);
const dRec = mod((mod(s1 * kRec, n) - z1) * inv(r, n), n);
console.log('recovered nonce matches:  ' + (kRec === k));
console.log('recovered private key:    ' + (dRec === d));
console.log('d = 0x' + dRec.toString(16));

Three years later, the same algebra emptied wallets. In August 2013, an advisory on bitcoin.org warned that "a component of Android responsible for generating secure random numbers contains critical weaknesses" that rendered "all Android wallets" vulnerable to theft ^[4]. The root cause, per Google's own postmortem, was that the platform's SecureRandom "may not receive cryptographically strong values" because the underlying PRNG was improperly initialized ^[12].

The consequence was nonce repetition across transactions. And because every Bitcoin signature is broadcast to a public ledger, anyone could scan the chain for two signatures sharing an r and drain the wallet behind them. The bitcoin.org advisory names the flaw and the affected wallets but states no total loss figure ^[4]. Any "coins stolen" number you have seen is reported, not established -- treat it accordingly.

The detector that would have caught both PS3 and Android is embarrassingly short. Group public signatures by r; any collision is an exposed key:

const n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141n;
const mod = (a, m) => ((a % m) + m) % m;
function inv(a, m) {
let [oldr, r] = [mod(a, m), m];
let [olds, s] = [1n, 0n];
while (r !== 0n) { const q = oldr / r; [oldr, r] = [r, oldr - q * r]; [olds, s] = [s, olds - q * s]; }
return mod(olds, m);
}
// Build a public feed in which one signer reused a nonce, then forget the secret
const dSecret = 777n, kReused = 424242n, rReused = 987654321n;
const mk = (z) => ({ r: rReused, s: mod(inv(kReused, n) * mod(z + mod(rReused * dSecret, n), n), n), z });
const feed = [ { r: 111n, s: 22n, z: 5n }, mk(1001n), { r: 222n, s: 44n, z: 9n }, mk(2002n), { r: 333n, s: 66n, z: 12n } ];

const seen = new Map();
for (const g of feed) {
const key = g.r.toString();
if (seen.has(key)) {
  const a = seen.get(key), b = g;
  const k = mod((a.z - b.z) * inv(mod(a.s - b.s, n), n), n);
  const d = mod((mod(a.s * k, n) - a.z) * inv(a.r, n), n);
  console.log('NONCE REUSE at r = ' + key + '  ->  private key d = ' + d.toString());
} else {
  seen.set(key, g);
}
}

Two incidents, two different root causes -- a hardcoded constant and a starved RNG -- and one identical, certain outcome. This is the crudest form of the whole thesis: the deployment lost the key while the discrete log stood untouched.

Pillar 1b: the nonce, biased (statistical, over many signatures)#

Reuse is loud. The subtler failure is a nonce that never repeats but is not quite uniform -- one whose top bit is a little too often zero, say. It turns out that even this surrenders the key, and the theory predicting it predates the exploits by two decades.

Nguyen and Shparlinski turned the abstract HNP into a concrete lattice attack on (EC)DSA with partially known nonces ^[15], and Brumley and Tuveri showed in 2011 that the necessary bit-leak could be harvested remotely, over a network, from an OpenSSL implementation whose scalar multiplication was not constant-time ^[16]. Then the field split into two solver regimes, and telling them apart is essential.

When the timing channel leaks a few bits of the nonce -- typically its exact bit-length -- the HNP is solved by lattice reduction. Minerva (CHES 2020) demonstrated this against smartcards and libraries whose scalar multiplication ran in time correlated with the nonce's length, reporting roughly "2100 signatures to recover the private key on the standard secp256r1 curve" ^[17].

TPM-Fail (USENIX Security 2020) carried the same idea into hardware roots of trust. A timing leak in Intel firmware TPMs (CVE-2019-11090 ^[18]) and STMicroelectronics ST33 chips (CVE-2019-16863 ^[19]) recovered a 256-bit ECDSA key from an Intel fTPM in 4 to 20 minutes, and a VPN authentication key remotely in about five hours ^[5]. Two honesty notes. Minerva's project page retracted its original EdDSA claim; the confirmed result is ECDSA-only ^[17]. And the TPM-Fail targets were not toys -- they held Common Criteria EAL4+ and FIPS 140-2 certification, and the leak survived that scrutiny ^[5].

flowchart TD
L["A timing channel leaks partial information about the nonce k"] --> Q{"How much leaks per signature?"}
Q -->|"at least 2 bits"| LAT["Lattice reduction of the HNP: Minerva, TPM-Fail"]
Q -->|"under 1 bit"| FFT["Bleichenbacher and Fourier HNP: LadderLeak"]
LAT --> R["Private key d recovered over MANY signatures"]
FFT --> R

The second regime is where people get it wrong. When the leak drops below a single bit -- LadderLeak revealed the most-significant bit of the nonce "but with probability less than one" -- lattices become intractable, and the attack instead revives a Fourier-analysis method the paper credits to Daniel Bleichenbacher ^[20].

The LadderLeak authors note that "most of the attacks so far have relied on at least two bits of nonce bias," precisely the lattice regime. Their contribution was to break below it, over curves sect163r1 and NIST P-192, using the Fourier solver rather than a lattice ^[20]. Calling LadderLeak a lattice attack is the field's classic mistake.

"Breaking ECDSA With Less Than One Bit Of Nonce Leakage" -- the title of the LadderLeak paper, and the most compact statement of how little a nonce must betray before the key is gone.

Notice what happened across this subsection. Every one of these attacks beat a signer that had already removed the reuse bug. The leak had moved from how the nonce was generated to how it was used -- a variable-time scalar multiplication -- and the cure had to move with it. Hold that thought; it is the pivot of the entire article. But reuse or bias, lattice or Fourier, two signatures or two thousand, the outcome is the same and the discrete logarithm is never touched: the deployment hands over d, and the strongbox stays locked.

Pillar 2: the parameters, unvalidated (CurveBall)#

The nonce pillar is about a secret the deployment mishandles. The second pillar is about an identity the deployment fails to check. On 14 January 2020, Microsoft patched CVE-2020-0601, reported by the NSA: "a spoofing vulnerability exists in the way Windows CryptoAPI (Crypt32.dll) validates Elliptic Curve Cryptography (ECC) certificates" ^[6]. It became known as CurveBall, and it is the cleanest example in the whole corpus of a break that has nothing to do with the mathematics of ECC.

Recall the parameter contract. A public key is the point dG -- meaningful only if everyone agrees on G. CryptoAPI, when handed a certificate that specified its curve with explicit parameters, checked that the certificate's public point matched a trusted root's public key. What it did not check was the generator.

So an attacker could craft a curve with a custom generator G', pick any private key d' they liked, and compute G' such that d' * G' equals the exact public point of a trusted root certificate authority. The forged certificate then presents the right public point on the wrong curve. Windows, comparing only the point, accepts it -- while a library that pins named curves rejects it instantly, because G' is not the standard base point.

flowchart TD
A["Attacker picks explicit curve parameters with a custom generator G-prime"] --> B["Chooses private key d-prime so that d-prime times G-prime equals a trusted root public point Q"]
B --> C["Forged certificate presents point Q on the attacker curve"]
C --> D{"Windows CryptoAPI validation"}
D -->|"Public point matches a trusted root? YES"| E["Accepted, but the generator was never checked"]
D -.->|"A named-curve-pinning library also checks G"| F["Rejected, G-prime is not the standard base point"]
E --> G["Forged code-signing or TLS certificate chains to a trusted root"]

The ECDLP was never in play. The attacker chose their own private key; they never had to recover anyone's. The failure is a single missing comparison -- generator against named curve -- buried in a certificate validation stack that a billion machines trusted. CurveBall is a validation bug, not a curve break, and the fix is exactly what the missing check would have been: reject explicit parameters, or fully re-validate them against the claimed named curve.

Pillar 3: the negotiation, downgraded (Logjam)#

The third pillar is the one honest exception, and handled carelessly it looks like a refutation of the whole thesis. In 2015, the Logjam team (CVE-2015-4000) showed that a man-in-the-middle could rewrite a TLS handshake -- "rewriting a ClientHello with DHE replaced by DHE_EXPORT" -- to force the connection onto a 512-bit export-grade Diffie-Hellman group ^[21]. And here, unlike everywhere else, the attacker really does compute a discrete logarithm.

The trick is that the expensive part of the number field sieve has to be done only once per prime, and servers share primes.

The Logjam researchers found that "8.4% of the Top 1 Million domains were initially vulnerable," and that because so many servers reused a handful of standardized 512-bit primes, "the first step in the number field sieve ... is dependent only on this prime" ^[7]. One precomputation, amortized across every server that shipped that prime.

"The first step in the number field sieve ... is dependent only on this prime." One precomputation breaks every server that shares the group.

sequenceDiagram
participant C as Client
participant M as MITM
participant S as Server
Note over M: One-time NFS precomputation per shared 512-bit prime
C->>M: ClientHello offering DHE
M->>S: ClientHello rewritten to DHE_EXPORT
S->>M: 512-bit export DH parameters, a shared standardized prime
M->>C: forwards the weak parameters
Note over M: Precomputation done, so this connection solves fast
M-->>C: session decrypted in near real time

Read carefully, Logjam is not a counterexample; it is the thesis in its most literal form. A discrete log was computed, but only against a 512-bit prime that a downgrade forced the connection onto and that policy had left crippled and shared. The deployment set the weak, shared group on the table; the number field sieve merely finished the job. No strong, standard-sized group ever fell. The fix is the same shape as the break: remove export ciphers, negotiate vetted named groups (RFC 7919 ^[22]), and adopt TLS 1.3, which removes static Diffie-Hellman entirely ^[23].

Three pillars, seven breaks, one shape: every attack hit a layer the discrete-log math depends on but does not control. Name the shape, and you have the whole discipline.

5. The Realization: Fix the Contracts, Not the Curve#

There was no single eureka here. The insight accumulated across fifteen years of incidents and then snapped into one sentence: every field break attacked a layer the discrete-log math depends on but does not control -- the nonce, then the parameters, then the negotiated strength -- and every fix changed how the primitive is generated, used, validated, or negotiated, never the curve and never the log.

The sharpest crystallization hides inside the word "bias." For years it was treated as one problem with one fix: remove the random number generator, derive the nonce deterministically (RFC 6979 ^[24], later blessed by FIPS 186-5 ^[25]), and the biased-nonce class is solved. But Minerva, TPM-Fail, and LadderLeak all recovered keys from signers that had already done that. The reason is that "bias" was concealing two distinct root causes with two distinct cures.

flowchart TD
B["One word: nonce bias"] --> G["Generation defect: the RNG returns a constant, repeated, or predictable k"]
B --> U["Usage defect: variable-time scalar multiplication leaks the bit-length of k"]
G --> GC["Cure: deterministic and hedged nonces, RFC 6979 and FIPS 186-5"]
U --> UC["Cure: constant-time, exception-free scalar multiplication"]
GC --> BOTH["You need BOTH, they are orthogonal"]
UC --> BOTH

A generation defect is a bad nonce coming out of the sampler -- a constant (PS3), a repeat (Android), a predictable value. Determinism and hedging cure it. A usage defect is a perfectly good nonce leaking through the timing of the scalar multiplication that consumes it -- the bit-length falling out through a side channel (Minerva, TPM-Fail) or a sub-bit correlation (LadderLeak). Only constant-time code cures that. The two cures are orthogonal, and you need both.

Generalize the two-cures fork and you get the entire discipline of this field: four contracts, not one curve. Generate the nonce so it cannot be predicted or repeated; use it in constant time so it cannot leak; validate your parameters so no attacker chooses your generator; negotiate only strong, unshared groups so no downgrade can strand you. Every documented break is a breach of one of those four. No break in the corpus is a break of the discrete logarithm.

This also dissolves the apparent contradiction the article opened with. "Nobody solved the discrete log" and "somebody recovered the key" only sound incompatible if you conflate the discrete-log problem with a discrete-log deployment. The problem is a statement about computational hardness; the deployment is a nonce, a set of parameters, and a negotiation, wrapped around that hardness. The problem stayed hard. The wrapping tore.

If the discipline is "honor the four contracts, not the curve," what does a deployment that honors all four actually look like in 2026?

6. What Correct EC/DH Deployment Looks Like in 2026#

The state of the art in this field is not a better discrete-log solver -- no such thing exists. It is a deployment discipline at the three layers the math never controlled. Here it is, pillar by pillar.

Nonce: two orthogonal cures, and a primitive that folds in both#

RFC 6979 also quietly records the deeper lesson. It insists on comparing each candidate nonce against the group order rather than reducing it modulo the order, warning that a "simple modular reduction would induce biases that would be detrimental to signature security" ^[24]. That is a standards document, in 2013, acknowledging that bias, not just reuse, is fatal. You can watch the effect yourself:

// A raw sampler emits values in [0, 256). We need a nonce in [0, q).
const q = 200n, B = 256n, trials = 400000;
const raw = () => BigInt(Math.floor(Number(B) * Math.random()));
let biasedHigh = 0, fairHigh = 0;
const half = q / 2n;
for (let i = 0; i < trials; i++) {
const reduced = raw() % q;              // reduce mod q -> BIASED
if (reduced >= half) biasedHigh++;
let fair; do { fair = raw(); } while (fair >= q);  // compare to q, retry -> FAIR
if (fair >= half) fairHigh++;
}
console.log('reduce mod q -> P(nonce in top half): ' + (biasedHigh / trials).toFixed(4));
console.log('compare to q -> P(nonce in top half): ' + (fairHigh / trials).toFixed(4));
console.log('That gap from 0.5 is a free bit for a Hidden Number Problem attacker.');

Determinism, though, fixes only generation. On hardware it also adds a risk.

New designs can sidestep the whole fork by choosing a misuse-resistant primitive. Ed25519 (RFC 8032) derives its nonce as a hash of the secret and message -- deterministic by construction, no per-signature RNG -- and signs with a single complete, constant-time addition law that has no exceptional cases to mishandle ^[26]. It folds both cures into the primitive and removes the dangerous choices from the caller's hands. Misuse-resistant is not misuse-proof. PuTTY derived P-521 ECDSA nonces such that "the first 9 bits of each ECDSA nonce are zero," allowing "full secret key recovery in roughly 60 signatures" (CVE-2024-31497) ^[13]. Determinism implemented carelessly re-introduced exactly the bias it was meant to prevent.

Validation: reject what you cannot vouch for#

The CurveBall cure is direct: bind a certificate's curve to the standard parameters of its named curve, and reject explicit parameters or fully re-validate them. The January 2020 patch made crypt32.dll check the generator, not merely the point ^[6].

For key exchange with static keys, the discipline is fuller. Before using a received point, confirm it is not the identity, lies on the curve, and sits in the correct prime-order subgroup -- the full public-key validation of NIST SP 800-56A, which blocks invalid-curve and small-subgroup attacks that would otherwise bleed a static key out one query at a time ^[27].

The most durable answer is to make invalid inputs unrepresentable. X25519 works on a Montgomery curve chosen so that every 32-byte string is an acceptable public key; the RFC even instructs implementations to "accept non-canonical values," and to run the conditional swap "in constant time" ^[28]. There is no explicit-parameter path to abuse and no on-curve check to forget. ※ This is the "make invalid states unrepresentable" principle applied to cryptography: the safest validation code is the code you deleted because the type system already guarantees the property. But note the boundary carefully.

Negotiation: remove the weak option entirely#

The downgrade pillar's fix is structural. RFC 7919 replaced ad-hoc, shared Diffie-Hellman primes with a menu of vetted named groups negotiated like curves ^[22]. TLS 1.3 went further and deleted the weak options outright, so there is nothing to downgrade to.

"Static RSA and Diffie-Hellman cipher suites have been removed; all public-key based key exchange mechanisms now provide forward secrecy." -- RFC 8446, the TLS 1.3 specification ^[23].

Because TLS 1.3 permits only strong ephemeral groups and binds the negotiation into the handshake transcript, the Logjam rewrite is not merely discouraged -- it is structurally impossible ^[23]. The end state of the negotiation pillar is a protocol in which the crippled, shared 512-bit group Logjam relied on simply cannot be selected.

Each of these is a choice, and where there is a choice, engineers argue. Which discipline actually wins in which threat model?

7. Competing Approaches: Which Defense Answers Which Adversary#

These defenses are not rungs on one ladder. They are answers to different adversaries, and the honest way to compare them is one pillar at a time.

Nonce: which signing discipline stops which adversary#

The load-bearing insight is that no single column stops every row. Generation cures (deterministic ^[24], hedged ^[25]) and the usage cure (constant-time) are orthogonal, which is why hedged-plus-constant-time became the practitioner default and why Ed25519 ^[26] folds most of both into the primitive.

Read the rows, not the columns: reuse fails only the first row and is certain from two signatures; the timing leaks fail three of the five columns and are cured on a different axis entirely. That is the two-cures fork, rendered as a matrix.

Validation: three philosophies of not trusting your input#

Named-curve pinning is the precise CurveBall fix ^[6]; SP 800-56A validation is the belt-and-suspenders choice for static keys ^[27]; X25519 deletes the problem by construction ^[28]. They converge on stopping CurveBall and diverge on everything else.

Downgrade: hardening, deletion, or hedging against tomorrow#

RFC 7919 named groups ^[22] are the transitional hardening for TLS 1.2; TLS 1.3 is the structural end state ^[23]; hybrid X25519 with ML-KEM (RFC 9954 ^[29], ML-KEM standardized as FIPS 203 ^[30]) is the forward hedge against a quantum adversary. Only the last column defends against a break that would be genuine mathematics rather than a deployment slip.

Every column in every table changed the deployment, not the curve. So is the discrete log itself simply unbreakable? Almost -- and the "almost" is the most honest paragraph in this article.

8. Theoretical Limits: What Is Provably True on Both Sides#

This is the honest concession the thesis has been earning the right to make. There are two provable sides here, and the argument needs both.

The hardness side: no room for a strong curve to fall#

On a well-chosen group, the discrete logarithm is genuinely hard, and we can say so with unusual precision. The best classical attack is Pollard's rho, a square-root-time random walk that needs negligible memory ^[2]. In the strict generic model its expected cost is about $\sqrt{\pi n/2}$, roughly 1.25 times $\sqrt{n}$ group operations; on an elliptic curve, the negation map (where $P$ and $-P$ share an x-coordinate) trims that to about 0.886 times $\sqrt{n}$. Either way the exponent is the same, matching baby-step giant-step's $O(\sqrt{n})$ time ^[1].

Against that upper bound, Shoup proved a generic lower bound of $\Omega(\sqrt{p})$: no algorithm restricted to the group operation can do better ^[31]. The two meet at $\Theta(\sqrt{n})$. The generic gap is essentially closed -- which is exactly why a 256-bit curve delivers around 128-bit security, and why no strong deployed curve's discrete log has fallen.

The last two rows carry the concession. Finite-field Diffie-Hellman is not generic: the number field sieve solves it in sub-exponential time, which is why finite-field DH needs primes of about 3072 bits to match the security a 256-bit curve gives (2048 bits is the absolute minimum), and why Logjam's downgrade to 512 bits was finishable at all ^[7]. The number-field-sieve mathematics belongs to the companion article.

Logjam is the only break in this corpus that reached the mathematics, and the reason is structural, not accidental. A finite field carries extra arithmetic structure that a generic group lacks, which lets the number field sieve run in sub-exponential time, faster than the square-root barrier that protects a strong elliptic curve. That structural gap is the sole opening the discrete log ever offered, and even it was not enough alone: the computation became feasible only after the prime was cut to 512 export-grade bits. Raise the group back to a standard 2048-bit prime, or move to a curve where no such shortcut exists, and the opening closes.

The leakage side: no room to hide a little bias#

The other provable side indicts the deployment just as sharply. The Hidden Number Problem makes partial leakage fatal by construction: Boneh and Venkatesan proved that recovering a secret from many small most-significant-bit leaks is tractable ^[14], and Nguyen and Shparlinski turned that into a working lattice attack on (EC)DSA with partial nonces ^[15].

There is no "a little bias is tolerable" regime: any consistent partial leak of k, integrated over enough signatures, provably recovers d. Two or more leaked bits fall to a lattice; a sub-bit leak falls to Bleichenbacher's Fourier method ^[20]. "k is secret, uniform, and unique" is not a best practice -- it is a hard boundary.

So where, concretely, does EC and DH still break tomorrow?

9. Where EC and DH Still Break in the Field#

The incidents are settled. The classes are not. Every open problem below is a documented pattern waiting for its next instance, and each one maps to a pillar you have already met.

The next SecureRandom (nonce generation, Pillar 1). A signer needs a unique, secret nonce at the exact moment its entropy is weakest: first boot, a headless IoT device with no entropy events, or a freshly cloned virtual machine carrying a duplicated seed. This is the mechanism behind Android 2013 ^[12], and it recurs whenever hardware is provisioned faster than it can gather randomness. Cloned-VM state duplication is an especially nasty modern form: two hosts that never coordinated can emit the same "random" nonce because they booted from one snapshot. The signing path can be hedged ^[25], but key generation and ephemeral key exchange still need a live, well-seeded source.

The next Minerva or LadderLeak (nonce usage, Pillar 1). Constant-time scalar multiplication must be re-established against every new microarchitecture -- caches, execution ports, prefetchers, simultaneous multithreading -- and on every fragile incomplete-addition curve. The bit-length leak of Minerva ^[17] and the sub-bit leak of LadderLeak ^[20] both post-date deterministic nonces precisely because the leak had moved to usage. Formally verified primitives close the known channels on the chosen curve; FIPS-mandated P-curves and secp256k1 keep hand-written code in production.

The long tail of shared primes (downgrade, Pillar 3). TLS 1.3 closes the web protocol layer, but export-grade and shared standardized primes outlived their policy elsewhere. IKEv1 VPNs and older SSH still ship shared 1024-bit Diffie-Hellman groups, and a single precomputation per shared prime amortizes across every server using it ^[7]. The consensus recommendation is blunt: retire 1024-bit DH now.

The next CurveBall (validation, Pillar 2). CurveBall was one unchecked generator in one library ^[6]; the class is "somewhere in a large validation stack, attacker-supplied parameters are trusted." Every new parser, certificate profile, or post-quantum key format reopens the class, and a single such bug in a widely embedded validator forges trust across everything that depends on it.

Post-quantum migration ahead of Shor (cross-pillar). Hybrid key exchange -- running X25519 alongside ML-KEM so the session stays secure if either component holds -- is standardized (RFC 9954 ^[29]; concrete groups such as X25519MLKEM768 in the ongoing ECDHE-MLKEM work ^[32]; ML-KEM standardized as FIPS 203 ^[30]) and is already deployed at scale: it protected a majority of the human web traffic Cloudflare measured by late 2025 ^[33]. But the migration carries a trap that has nothing to do with the discrete log.

None of these needs new mathematics to break you. Each needs exactly one deployment mistake. Here is how not to make it.

10. What to Do on Monday#

Every item below maps to a specific incident in this article. Do these, and you do not ship the next one.

• Never put a bare runtime RNG in the signing path. Use deterministic (RFC 6979 ^[24]) or, on hardware, hedged (FIPS 186-5 ^[25]) nonces. Prevents: PS3, Android.
• Demand constant-time, exception-free scalar multiplication. This is a separate control from the nonce discipline, not a duplicate of it. Prevents: Minerva, TPM-Fail, LadderLeak.
• Prefer misuse-resistant primitives. Ed25519 for new signing ^[26], X25519 for ephemeral key exchange ^[28]; for static-key ECDH, run full public-key validation per SP 800-56A ^[27]. Prevents: whole classes of implementer error.
• Reject explicit curve parameters; require named curves. Pin the curve, and the generator with it. Prevents: CurveBall ^[6].
• Disable export ciphers and use vetted groups. RFC 7919 named groups ^[22] for residual TLS 1.2 DHE, or move to TLS 1.3 ^[23]. Prevents: Logjam.
• Never assume a fresh ephemeral rescues a shared prime. The number-field-sieve precomputation is per-prime, not per-connection ^[7]. Prevents: the subtle half of Logjam.
• Plan the post-quantum migration as hybrid, not pure. Run a classical curve alongside ML-KEM (RFC 9954 ^[29]); remember a KEM is not a NIKE. Prevents: harvest-now-decrypt-later exposure.

Notice that not one item on this list is "use a bigger curve." For every break except Logjam's downgrade, key size is irrelevant -- a 384-bit curve reuses a nonce exactly as fatally as a 256-bit one. The controls are about generation, usage, validation, and negotiation, because those are the four contracts, and the contracts are where reality broke.

Two questions decide whether you got this right, and they happen to be the two most-repeated errors in the field.

11. FAQ: Misconceptions, Precisely Corrected#

Half a century after Diffie and Hellman reduced key exchange to one hard problem, the scoreboard is unambiguous: seven documented field breaks across three deployment layers, and a discrete-log ceiling that only ever reached a deliberately crippled, shared 512-bit export group -- never a strong deployed curve, never a standard-sized group. The mathematics kept its promise. The deployments did not.

The discrete log never fell. The nonce did, the parameters did, and the negotiation did -- and every one of those is the deployment's job, not the curve's.

For the other half of the story -- how a curve itself could be structurally weak, how the number field sieve and Shor's algorithm actually break the math -- see the structural companion, "How the Discrete Log Would Break." For the primitive that has no per-signature nonce to reuse and its own padding-oracle history, see the series sibling, "How RSA Breaks in Real Life." This article was about the gap between a hard problem and a shipped product. That gap is where the keys keep getting out.