Why ECDSA nonce reuse leaks the private key

ECDSA needs a fresh random number for every signature. Use the same one twice and anyone watching can recover the private key with two lines of algebra — which is exactly how the PS3's master key fell out.

Why it exists

In December 2010, at the 27th Chaos Communication Congress in Berlin, a group calling itself fail0verflow walked on stage and demonstrated that they had recovered the PlayStation 3’s code-signing private keys. Not stolen from a Sony server — derived from signatures Sony had already published on every PS3 in the world. Once they had those keys, they could sign their own firmware as if they were Sony, and the console’s chain of trust collapsed: homebrew apps, alternate operating systems, and the rest of the jailbreak ecosystem fell out from there. The mechanism behind the break was almost embarrassingly small. Sony’s ECDSA implementation reused the same per-signature random value across different firmware blobs, and that’s all it takes.

The wild part isn’t the politics or the jailbreak. It’s that the math of ECDSA is fine. The curve is fine, the hash is fine, the private key is fine. The whole scheme is destroyed by one variable being not-random-enough. This is the cleanest example I know of a recurring lesson in real cryptography: security is usually a constraint on the implementation, not the math.

Why it matters now

ECDSA is everywhere you actually transact value or trust. Bitcoin signs transactions with it (over the curve secp256k1); plenty of other chains use ECDSA, Schnorr, Ed25519, or BLS depending on lineage. Apple devices use ECDSA for code signing. TLS certificates routinely use ECDSA over P-256 instead of RSA. SSH keys default to ECDSA or Ed25519 in modern OpenSSH. Every randomized ECDSA deployment that generates a fresh nonce per signature is one buggy RNG away from the PS3 outcome. (Deterministic ECDSA — see below — and Ed25519 sidestep that risk by construction.)

It has happened repeatedly. The PS3 in 2010 is the famous one. In 2013, Bitcoin Android wallets lost coins because Android’s SecureRandom had a weakness on certain devices that caused nonce collisions across signatures — attackers scraped the public blockchain for repeated r values and drained the wallets. Embedded firmware and IoT signing have produced a steady drip of similar incidents since. The pattern is always the same: the curve math holds, the RNG fails, the key falls out.

The short answer

ECDSA security = elliptic-curve discrete-log hardness + a secret, unique, unpredictable nonce per signature

ECDSA pretends to be one equation but is really two assumptions stacked. If the elliptic-curve discrete log is hard and the per-signature nonce k is fresh and secret, the scheme is secure. If k is ever repeated across two signatures with the same private key, the second assumption collapses, and two signatures plus a few lines of modular arithmetic give up the private key. The math doesn’t care that the curve is still strong.

How it works

An ECDSA signature on a message m under private key d (an integer) is a pair (r, s) computed like this:

• Pick a nonce k, a random integer in [1, n−1], where n is the curve order.
• Compute the curve point kG, where G is the generator.
• Set r = (kG).x mod n — the x-coordinate of that point, reduced mod n. (If r = 0, retry with a new k.)
• Set s = k⁻¹ · (e + r·d) mod n, where e = bits2int(Hash(m)) — the message hash converted to an integer and truncated to the bit length of n.

Verification uses only the public key Q = dG, the message, and (r, s). The private key d never appears in the verifier; the nonce k is thrown away after signing and is supposed to never appear anywhere again.

Now suppose the signer reuses the same k for two different messages m₁ and m₂ (with e₁ ≠ e₂). Because r is derived from k alone, both signatures will share the same r. So a passive observer who collects two signatures on the same public key and notices a repeated r immediately knows: same nonce was used. From here it’s algebra.

s₁ = k⁻¹ · (e₁ + r·d) mod n
s₂ = k⁻¹ · (e₂ + r·d) mod n

s₁ − s₂ = k⁻¹ · (e₁ − e₂) mod n           ← the r·d term cancels

k = (e₁ − e₂) · (s₁ − s₂)⁻¹ mod n

Subtracting the two signing equations cancels the private-key term, leaving k as the only unknown. Once k is known, the signing equation rearranges to give up d directly:

d = (s · k − e) · r⁻¹ mod n

That’s it. No quantum computer, no curve break, no factoring — just a public observation that two signatures share an r, and a calculator that can do modular inverses. The whole strength of the elliptic-curve discrete log was wrapped around the assumption that k was an unknown random number each time. Reusing k across two different messages is enough to give up the private key.

It’s actually worse than reuse. If k is merely predictable — drawn from a weak PRNG, biased toward small values, or correlated across signatures — there are lattice-based attacks that recover d from many signatures even when no two k’s are identical. Same family of failure: the security of ECDSA leans entirely on k being indistinguishable from uniform random in [1, n−1].

Why this is a property of ECDSA (and DSA), not all signatures

The same defect lives in classical DSA — ECDSA is just DSA over an elliptic curve. RSA signatures are not vulnerable to this particular failure mode (they don’t have a per-signature nonce in the same role; RSA-PSS uses random salt for different reasons). This specific key-recovery algebra also doesn’t apply to symmetric ciphers — though don’t read that as “AES is fine to misuse.” Nonce reuse in AES-GCM or AES-CTR is its own catastrophe (it leaks the keystream and breaks authentication), just via different math. The lesson generalizes: nonces are load-bearing in many primitives, and each scheme has its own way of collapsing when you reuse one.

The fix: stop relying on the RNG

The standard fix has been around since 2013 in the form of RFC 6979, which specifies deterministic ECDSA: derive k from the private key and the message hash via HMAC-DRBG (seeded from d and Hash(m)) instead of asking the RNG. Same private key plus same message always yields the same k, but two different messages yield independent-looking ks, and the secret d is mixed in so an attacker can’t precompute. This makes nonce reuse structurally impossible as long as you sign different messages. It is the default in libsecp256k1 (used by Bitcoin Core) and is widely adopted across modern ECDSA libraries.

The cleaner answer is to skip ECDSA entirely. EdDSA (Ed25519 is the popular instance) bakes deterministic nonces into the specification itself rather than retrofitting them — there is no RNG-shaped hole to fall into. New deployments increasingly default to Ed25519 for exactly this reason.

Show the seams

• Determinism has its own subtle failure mode. If a deterministic-ECDSA signer is induced to sign the same message twice but a fault hits one computation (a glitched bit during signing), an attacker can again get two signatures with the same k and different effective H(m), recovering d. Fault-injection attacks against deterministic ECDSA have been demonstrated in academic settings. Honest gap: I don’t have a confident count of real-world incidents from this attack vector.
• The PS3 specifics: I’m confident about the broad story — fail0verflow presented at 27C3 (December 2010), the bug was nonce reuse in Sony’s ECDSA implementation, and the master signing key was recovered. I am not confident in the exact reason the nonce was constant (it’s been described as a hardcoded value rather than a weak RNG, but I’d rather not commit to the specific characterization without re-checking the original talk).
• “Just use a good RNG” is the wrong takeaway. The lesson of RFC 6979 isn’t that RNGs got better; it’s that a signature scheme whose security depends on every signer having a flawless RNG forever is a bad scheme. The fix moved the requirement from “trust the RNG every time” to “trust the hash function” — a much sturdier assumption.
• Detection is asymmetric. A signer can’t easily tell in real time whether their RNG is betraying them — short of post-hoc scanning their own signatures for repeated rs. A passive attacker watching a public ledger (a blockchain, a CT log, a package archive) can scan millions of signatures for repeated r values trivially. The attacker has the easier job.

The mental model: in ECDSA, the nonce k is not a knob, it is a second private key. Treating it as anything less — letting it leak, letting it repeat, letting it correlate — gives away the first private key for free.

Famous related terms

• RFC 6979 — RFC 6979 = ECDSA + k derived as HMAC(d, H(m)) — the standard fix; eliminates the RNG dependency at the source.
• EdDSA / Ed25519 — EdDSA = Edwards curve + deterministic nonce by design — modern signature scheme without ECDSA’s nonce-shaped trapdoor. Used in SSH, Signal, and many TLS deployments.
• Schnorr signatures — Schnorr ≈ ECDSA's cleaner cousin — same elliptic-curve setting, simpler math, supports key aggregation. Bitcoin added Schnorr (BIP-340) alongside ECDSA in the Taproot upgrade.
• Lattice attacks on biased nonces — lattice attack ≈ many signatures with slightly-biased k → reconstruct d — generalizes nonce reuse: the attacker doesn’t need a collision, just a statistical pattern in k.
• Public-key cryptography — the broader setting ECDSA lives inside.
• Signatures vs encryption — why ECDSA is a signature primitive, not encryption-in-reverse.

Going deeper

• RFC 6979, Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA) — Thomas Pornin, 2013. Short and readable; the construction is simpler than you’d expect.
• fail0verflow, Console Hacking 2010 — PS3 Epic Fail, 27C3 talk (December 2010). Recordings are still online; the ECDSA section is the cryptographic punchline.
• Nguyen & Shparlinski, The Insecurity of the Digital Signature Algorithm with Partially Known Nonces (J. Cryptology, 2002) — foundational lattice-attack paper for biased-nonce DSA. Their follow-up, The Insecurity of the Elliptic Curve Digital Signature Algorithm with Partially Known Nonces (DCC, 2003), is the ECDSA-specific version.
• Bernstein et al., High-speed high-security signatures (2011) — the Ed25519 paper; the design choices read as a direct response to ECDSA’s RNG dependence.