ECDSA/DSA Nonce Reuse — identical r collapses the private key to closed-form algebra

If two ECDSA (or DSA) signatures from the same key were produced with the same nonce k, the private key falls out of two linear equations in closed form — no discrete-log solving, no lattice, just modular arithmetic.

The signal that betrays it

Two (or more) signatures from the same public key share the same `r`. That's the entire tell, and it's cheap to check: r = (kG).x mod n depends *only* on k, so identical r means the signer used the same per-signature secret twice (accidentally, or because the "random" nonce generator isn't random). In practice:

- You don't need to know *why* k repeated to exploit it — a static seed, a broken PRNG, a counter that wrapped, a VM/container that reset its entropy pool before signing, RFC 6979 done wrong (see Deterministic Nonce (RFC 6979) Failures — when 'no more RNG risk' still leaks the key). The exploit is identical regardless of root cause. - If you're handed a batch of signatures rather than a suspicious pair, group them by `r` — any group with more than one member is exploitable, and a dump of dozens or hundreds of signatures (firmware update history, a signing-oracle CTF service hit many times) is exactly the shape that hides this. Don't eyeball it; sort and diff. - Works identically for plain DSA — swap (n, G) for (q, g) and the elliptic-curve point op for modular exponentiation; see DSA Fundamentals — the linear signing equation every DSA attack exploits for the shared s*k = h + d*r identity this attack exploits. - Two real-world breaches with this exact shape, useful for calibrating how often "no shortcut, it's just bad randomness" actually happens outside CTFs: Sony's PS3 signing key was recoverable because Sony's ECDSA implementation used a static, non-random nonce for every firmware signature — with two signed firmware images in hand, the private key fell straight out (disclosed by fail0verflow, Dec. 2010). Separately, a 2013 bug in Android's SecureRandom (an uninitialized JCA PRNG) made Bitcoin wallet apps on Android reuse k across transactions with more than one input, and attackers scanned the blockchain for duplicate r values to drain wallets.

How it's exploited

The signing equation for both signatures on the same key with the same k is s*k ≡ h + d*r (mod n). Two signatures give two equations in two unknowns (k, d); subtracting eliminates d and leaves k in closed form:

``python def recover_from_reused_nonce(r, s1, h1, s2, h2, n): k = ((h1 - h2) * pow(s1 - s2, -1, n)) % n d = ((s1 * k - h1) * pow(r, -1, n)) % n return k, d # spot it first: group all (r, s, h) triples for one pubkey by r, # any group of size > 1 is exploitable — pull any two and feed them in here ``

This is algebraically identical to the single-shot form some tooling uses, d = (s2*h1 - s1*h2) / (r*(s1-s2)) mod n, which skips materializing k — use whichever is easier to plug into your CTF framework; both need s1 ≠ s2 mod n (which holds whenever the two signed messages/hashes actually differ).

Operational details that matter in practice, from having actually run this against real challenge dumps:

- Truncate/reduce `h` consistently. h is H(m) reduced to the bit-length of n (or q for DSA) per the spec — if dsa_verify/ecdsa_verify doesn't check out on a signature you believe is genuine, you have a truncation or endianness bug in h, not the wrong vulnerability. Fix that before concluding nonce reuse doesn't apply. - Watch the sign. If the first d you recover doesn't verify against the public key, retry with (s1 + s2) in place of (s1 - s2) in the k step before concluding the pair isn't actually a reuse. This isn't superstition: ECDSA signatures are only unique up to a sign flip on s — for any valid (r, s), (r, n - s) is also a valid signature on the same message (the well-documented "low-S / high-S" malleability that libraries like Bitcoin Core later forced canonical to kill transaction malleability). A signature stack that doesn't canonicalize s can hand you the high-S form on one of the two signatures, which flips the sign in the subtraction; trying both combinations costs nothing and resolves it deterministically. - Always verify the recovered `d` against the public key (d*G == Q for ECDSA, g^d mod p == y for DSA) before trusting it — don't stop at "the algebra ran without an exception." A parsing bug (wrong n, wrong hash, wrong endianness) produces *a* number that looks like a private key but isn't.

Related

ECDSA Fundamentals — the s*k = h + d*r identity that routes every nonce attack DSA Fundamentals — the linear signing equation every DSA attack exploits Repeated / Linearly-Related Nonce Recovery — when nonces aren't reused, but ARE related by a known formula Deterministic Nonce (RFC 6979) Failures — when 'no more RNG risk' still leaks the key DSA/ECDSA Biased-Nonce Lattice Attack — turning partial nonce leaks into a private-key recovery Signature Malleability — a valid (r,s) becomes another valid (r,s) without the key Cryptanalysis Methodology — classify the family before you reach for an attack

What doesn't work

- Assuming same `p`/curve parameters means exploitable reuse. Two signatures from the same key sharing domain parameters (or even the same curve/q) tell you nothing on their own — you need the actual r values to match. Same params is necessary infrastructure, not the signal. - Trying this across two DIFFERENT public keys with a matching `r`. Identical r under different keys does not mean identical k was used *by the same signer for both* in a way you can exploit directly with the two-equation trick above — each signature still has two unknowns (its own k-usage and its own d) and you don't get a shared-d system to eliminate. This shape is real (see Deterministic Nonce (RFC 6979) Failures — when 'no more RNG risk' still leaks the key for the key-independent-k variant) but it is a *different* attack requiring a second relation on one specific key, not this closed form. Don't force-fit it. - Reaching for lattice reduction / Hidden Number Problem machinery when `r` matches exactly. If two signatures share the *exact* same r, that's exact nonce reuse — the closed-form solve above is instant. Building an HNP lattice instance is the tool for *partial* nonce bias/known-bits, a fundamentally different and much slower path to reach for when the cheap check (r1 == r2) already answered the question. See DSA/ECDSA Biased-Nonce Lattice Attack — turning partial nonce leaks into a private-key recovery for when you actually need it. - Trusting `d` without checking it against the public key. As above: a botched hash truncation or an off-by-one on which signature is "1" vs "2" still produces output, not an error — always verify before reporting the key recovered. - Expecting this to work with only ONE signature. Nonce reuse needs two signatures sharing k; a single leaked or biased nonce is a different technique — see DSA/ECDSA Biased-Nonce Lattice Attack — turning partial nonce leaks into a private-key recovery (partial bit knowledge) or, if k is fully known from some other leak, the direct one-shot solve in Deterministic Nonce (RFC 6979) Failures — when 'no more RNG risk' still leaks the key.