Exploiting ECDSA Nonce Reuse to Recover Private Keys via Shared k Values

Why This Matters

In 2010, console security researchers discovered that Sony's PlayStation 3 firmware signing used a static, hard-coded value for the ECDSA nonce k instead of generating a fresh random k for every signature. Because every firmware update was signed with the same k, the private signing key could be recovered algebraically from any two firmware images and their signatures — completely compromising the platform's chain of trust and enabling arbitrary code execution. This remains the most publicly visible demonstration of ECDSA nonce reuse. The same vulnerability class appeared in Bitcoin transaction signing implementations (where nonce reuse allowed private key recovery from the blockchain's public signature data) and in TLS client libraries. RFC 6979, published in 2013, provides a deterministic algorithm for generating k from the private key and message hash, eliminating the problem entirely without requiring any entropy source at signing time.

Core Concept

ECDSA (Elliptic Curve Digital Signature Algorithm) signatures over a curve with generator G and group order n are computed as follows. The signer holds private key d and public key Q = d·G. To sign message hash H(m):

1. Generate a random nonce k uniformly from [1, n-1].
2. Compute the curve point R = k·G; set r = R.x mod n (the x-coordinate of R).
3. Compute s = k^(-1) · (H(m) + r·d) mod n.
4. Output signature (r, s).

The nonce reuse attack exploits the case where the same k is used for two signatures on different messages m_1 and m_2. Both signatures share the same r (since R = k·G is identical). Given (r, s_1, H(m_1)) and (r, s_2, H(m_2)):

s_1 - s_2 = k^(-1) · (H(m_1) + r·d) - k^(-1) · (H(m_2) + r·d) = k^(-1) · (H(m_1) - H(m_2)) mod n

Therefore:

k = (H(m_1) - H(m_2)) · (s_1 - s_2)^(-1) mod n

Once k is recovered, the private key d follows directly:

d = (s_1 · k - H(m_1)) · r^(-1) mod n

The attack precondition is: same curve and generator G, two (message, signature) pairs where the r values are identical (indicating k reuse), and the signed messages (or their hashes) are known. No knowledge of the private key, no curve-breaking computation — just modular arithmetic over the group order n.

Partial nonce exposure (a generalisation via lattice methods): if k is not fully repeated but has a known number of zero bits (e.g., k < 2^(n/2)), the hidden number problem can be solved using LLL lattice reduction to recover d from many signatures. This is relevant when nonces are generated from a biased RNG.

Technical Deep-Dive

# ECDSA nonce-reuse private key recovery
# Prerequisites: pip install pycryptodome ecdsa

from ecdsa import NIST256p, ellipticcurve
from ecdsa.numbertheory import inverse_mod
import hashlib

def recover_private_key_nonce_reuse(curve_order, r, s1, s2, h1, h2):
    """
    curve_order: n (group order of the elliptic curve)
    r:           shared r value (x-coordinate of k*G mod n)
    s1, s2:      the two s values from signatures sharing k
    h1, h2:      integer message hashes H(m1), H(m2)
    Returns:     private key d as integer, and recovered nonce k
    """
    n = curve_order

    # Recover nonce k from the two s values
    # k = (h1 - h2) * inverse(s1 - s2, n) mod n
    s_diff = (s1 - s2) % n
    h_diff = (h1 - h2) % n
    k = (h_diff * inverse_mod(s_diff, n)) % n

    # Recover private key d
    # d = (s1*k - h1) * inverse(r, n) mod n
    d = ((s1 * k - h1) * inverse_mod(r, n)) % n

    # Verify: also try the other signature as a sanity check
    d_check = ((s2 * k - h2) * inverse_mod(r, n)) % n
    assert d == d_check, "Private key mismatch — check inputs"

    return d, k

# Example with NIST P-256 (secp256r1)
curve = NIST256p
n     = curve.order

# Parse signatures from challenge (DER or raw r,s pairs)
# Fill in from challenge data:
# r, s1, s2 = ...
# h1 = int.from_bytes(hashlib.sha256(msg1).digest(), 'big')
# h2 = int.from_bytes(hashlib.sha256(msg2).digest(), 'big')

# d, k = recover_private_key_nonce_reuse(n, r, s1, s2, h1, h2)
# print(f"[+] Private key d = {hex(d)}")
# print(f"[+] Nonce k       = {hex(k)}")

# To verify d: check Q = d*G equals the known public key
# from ecdsa import SigningKey
# sk = SigningKey.from_secret_exponent(d, curve=NIST256p)
# vk = sk.get_verifying_key()
# print("[+] Public key matches:", vk.to_string().hex() == known_pubkey_hex)

# SageMath version for secp256k1 (Bitcoin curve)
# Run in SageMath shell
p  = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
n  = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

def ecdsa_recover(r, s1, s2, h1, h2):
    F = GF(n)
    k = F(h1 - h2) / F(s1 - s2)
    d = (F(s1) * k - F(h1)) / F(r)
    return Integer(k), Integer(d)

# Automated approach with RsaCtfTool / ecdsa tooling:
# Search for repeated r values in a set of ECDSA signatures:
python3 -c "
sigs = [...]  # list of (r, s, hash) tuples
from collections import Counter
r_counts = Counter(r for r,s,h in sigs)
repeated = [r for r,c in r_counts.items() if c > 1]
print(repeated)
"

Cryptanalysis Methodology

1. Collect signatures and messages — Extract all (r, s) pairs and corresponding message hashes from the challenge. Signatures may be DER-encoded; parse with ecdsa or pyOpenSSL.
2. Identify repeated r values — Two signatures sharing the same r value use the same nonce k. Sort or hash-bucket signatures by r; any collision is immediately exploitable.
3. Compute k from the two s values — Apply k = (h1 - h2) * inverse(s1 - s2, n) mod n. Use Python's built-in pow(s1 - s2, -1, n) (Python 3.8+) for the modular inverse.
4. Recover d from k — Apply d = (s1*k - h1) * inverse(r, n) mod n. Verify by checking that d·G equals the known public key.
5. Sign or decrypt with the recovered key — Use the private key to produce forged signatures on arbitrary messages or to decrypt ECDH-derived session keys as required by the challenge.
6. Handle partial nonce bias — If no full repeats exist but nonces are biased (e.g., top 4 bits always zero), apply lattice-based hidden-number-problem attack in SageMath with LLL.

Secure Implementation Note — Generate ECDSA nonces using RFC 6979 deterministic nonce derivation. RFC 6979 computes k = HMAC-DRBG(private_key || H(message)), producing a unique, unpredictable, non-repeating k for every (key, message) pair without requiring any randomness at signing time. In Python, the ecdsa library uses RFC 6979 by default when hashfunc is specified. OpenSSL has supported RFC 6979 since version 1.0.2.

Common Cryptanalysis Errors

• Using message bytes instead of message hash as integer — h1 and h2 must be the integer representation of the hash output (e.g., int.from_bytes(sha256(msg), 'big')), not the raw message. Using the wrong value gives an incorrect k.
• Not reducing s_diff and h_diff mod n — Subtraction of large integers can go negative. Always reduce (s1 - s2) % n before computing the modular inverse.
• Confusing secp256k1 with secp256r1 — Bitcoin uses secp256k1; TLS/FIDO2 typically use secp256r1 (NIST P-256). The group orders n differ. Mixing them produces wrong results silently.
• Stopping after recovering k — k is not the private key. d = (s*k - H(m)) * r^(-1) mod n is the target. Always proceed to recover d.
• Assuming r uniqueness implies k uniqueness — In theory r = (k·G).x mod n; two different k values could theoretically produce the same r if k and k+n give the same point x-coordinate. This is negligible in practice but worth noting for rigour.
• Overlooking multi-nonce lattice attacks — When the challenge provides many signatures with biased (not repeated) nonces, the nonce reuse formula does not directly apply. The lattice/HNP method is required.

NICE Framework Alignment

Further Reading

• Garcia, F. and de Koning Gans, G. (2010). Wirelessly Pickpocketing a Mifare Classic Card — IEEE Symposium on Security and Privacy
• Brengel, M. and Rossow, C. (2018). Identifying Key Leakage of Bitcoin Users — RAID 2018
• RFC 6979: Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA) — IETF