ecdsa-nonce-reuse.ipynb

Kernel: SageMath 10.0

Break: ECDSA Nonce Reuse (The PlayStation 3 Hack)

Module 06 | Breaking Weak Parameters

When the same nonce $k$ is used for two ECDSA signatures, the private key falls out with simple algebra.

Why This Matters

In 2010, the hacker group fail0verflow revealed that Sony used the same nonce $k$ for every ECDSA signature on PlayStation 3 firmware updates. This single mistake allowed them to recover Sony's master private signing key, enabling anyone to sign and run arbitrary code on the PS3.

The mathematics behind the attack is shockingly simple: two equations, two unknowns, basic algebra. If you understood ECDSA signing from Notebook 06f, you already have everything you need to break it.

This attack also hit Android Bitcoin wallets in 2013 (a faulty random number generator repeated nonces) and continues to appear in poorly implemented systems.

The Scenario

Alice signs two different messages $m_1$ and $m_2$ using ECDSA with the same nonce $k$. The attacker (Eve) intercepts both signatures.

Recall ECDSA signing (from Notebook 06f):

1. Pick nonce $k$, compute $R = kG$, set $r = x_R \bmod n$.

2. Compute $s = k^{-1}(e + d \cdot r) \bmod n$, where $e = H(m)$ and $d$ is the private key.

3. Output signature $(r, s)$.

If the same $k$ is used for both signatures, both share the same $r$ (since $R = kG$ is identical). This is the telltale sign an attacker looks for.

Let's set up the scene.

# === Setup: a small curve for our demonstration ===
p = 10007  # a prime
E = EllipticCurve(GF(p), [3, 7])  # y^2 = x^3 + 3x + 7
G = E.gens()[0]
n = G.order()
print(f"Curve: y^2 = x^3 + 3x + 7 over F_{p}")
print(f"Generator G = {G}")
print(f"Order n = {n}, is prime: {n.is_prime()}")

# Alice's key pair
d = 4231  # Alice's SECRET private key
Q = d * G  # Alice's public key
print(f"\nAlice's private key: d = {d}  (secret!)")
print(f"Alice's public key:  Q = {Q}")

Step 1: Alice Signs Two Messages with the Same Nonce

Alice commits the fatal error: she uses the same nonce $k$ for two different messages.

Signature 1: $s_1 = k^{-1}(e_1 + d \cdot r) \bmod n$

Signature 2: $s_2 = k^{-1}(e_2 + d \cdot r) \bmod n$

Both signatures share the same $r$ because $R = kG$ is identical.

Zn = Integers(n)

# The SAME nonce for both signatures (the fatal mistake)
k = 7777
R = k * G
r = Integer(R[0]) % n
print(f"Nonce k = {k}")
print(f"Nonce point R = kG = {R}")
print(f"r = x_R mod n = {r}")

# Message 1
m1 = "PS3 firmware update v3.55"
e1 = Integer(Zn(hash(m1)))
s1 = Integer(Zn(k)^(-1) * Zn(e1 + d * r))

# Message 2
m2 = "PS3 firmware update v3.56"
e2 = Integer(Zn(hash(m2)))
s2 = Integer(Zn(k)^(-1) * Zn(e2 + d * r))

print(f"\nSignature 1: (r={r}, s1={s1})  on '{m1}'")
print(f"Signature 2: (r={r}, s2={s2})  on '{m2}'")
print(f"\nNotice: SAME r in both signatures! This is the smoking gun.")

Step 2: The Algebra of the Attack

Eve sees two signatures with the same $r$. She writes down the two signing equations:

$$s_1 = k^{-1}(e_1 + d \cdot r) \pmod{n}$$$$s_2 = k^{-1}(e_2 + d \cdot r) \pmod{n}$$

Subtract the second from the first:

$$s_1 - s_2 = k^{-1}(e_1 - e_2) \pmod{n}$$

The private key $d$ cancels out! Solve for $k$:

$$\boxed{k = \frac{e_1 - e_2}{s_1 - s_2} \bmod n}$$

Once Eve has $k$, she recovers the private key from either signing equation:

$$\boxed{d = \frac{s_1 \cdot k - e_1}{r} \bmod n}$$

# === Eve's Attack ===
# Eve knows: r, s1, s2, e1, e2, G, n (all public or intercepted)
# Eve does NOT know: k, d

print("=== Eve's information ===")
print(f"  r  = {r}")
print(f"  s1 = {s1},  e1 = H(m1) = {e1}")
print(f"  s2 = {s2},  e2 = H(m2) = {e2}")

# Step 1: Recover the nonce k
k_recovered = Integer(Zn(e1 - e2) * Zn(s1 - s2)^(-1))

print(f"\n--- Step 1: Recover nonce k ---")
print(f"  k = (e1 - e2) / (s1 - s2) mod n")
print(f"  k = ({e1} - {e2}) / ({s1} - {s2}) mod {n}")
print(f"  k_recovered = {k_recovered}")
print(f"  k_actual    = {k}")
print(f"  Match? {k_recovered == k}")

# Step 2: Recover the private key d
d_recovered = Integer((Zn(s1) * Zn(k_recovered) - Zn(e1)) * Zn(r)^(-1))

print(f"\n--- Step 2: Recover private key d ---")
print(f"  d = (s1 * k - e1) / r mod n")
print(f"  d_recovered = {d_recovered}")
print(f"  d_actual    = {d}")
print(f"  Private key recovered? {d_recovered == d}")

# === Eve can now forge signatures on ANY message ===
def ecdsa_sign_with_key(message, priv_key, G, n):
    """Sign a message using ECDSA with a given private key."""
    Zn = Integers(n)
    e = Zn(hash(message) % n)
    while True:
        k_sign = randint(1, n - 1)
        R_sign = k_sign * G
        r_sign = Zn(R_sign[0])
        if r_sign == 0:
            continue
        s_sign = Zn(k_sign)^(-1) * (e + Zn(priv_key) * r_sign)
        if s_sign == 0:
            continue
        return (Integer(r_sign), Integer(s_sign))

def ecdsa_verify(message, sig, pub_key, G, n):
    """Verify an ECDSA signature."""
    r_v, s_v = sig
    Zn = Integers(n)
    if not (1 <= r_v < n and 1 <= s_v < n):
        return False
    e = Zn(hash(message) % n)
    w = Zn(s_v)^(-1)
    u1 = Integer(e * w)
    u2 = Integer(Zn(r_v) * w)
    R_prime = u1 * G + u2 * pub_key
    if R_prime == E(0):
        return False
    return Integer(R_prime[0]) % n == r_v

# Eve forges a signature using the recovered private key
forged_msg = "Transfer all BTC to Eve's wallet"
forged_sig = ecdsa_sign_with_key(forged_msg, d_recovered, G, n)

print(f"Eve forges a signature on: '{forged_msg}'")
print(f"Forged signature: (r={forged_sig[0]}, s={forged_sig[1]})")
print(f"Verifies with Alice's public key? {ecdsa_verify(forged_msg, forged_sig, Q, G, n)}")
print(f"\nTOTAL BREAK: Eve has Alice's private key and can sign anything as Alice.")

The Fix: RFC 6979 Deterministic Nonces

The root cause is that ECDSA requires a fresh, unpredictable, never-repeated nonce $k$ for every signature. This is a dangerous requirement: one failure is catastrophic.

RFC 6979 (2013) eliminates this risk by deriving $k$ deterministically:

$$k = \text{HMAC-DRBG}(d, H(m))$$

This means:

• The same $(d, m)$ pair always produces the same $k$ (and thus the same signature).

• Different messages produce different $k$ values (since $H(m)$ differs).

• No randomness is needed at signing time, so there is no RNG to fail.

EdDSA (Ed25519) takes this further: the nonce is derived as $k = H(\text{prefix} \| m)$ where the prefix is derived from the private key. Deterministic nonces are baked into the design, not bolted on as an afterthought.

# Simulating deterministic nonce generation (simplified RFC 6979 idea)
import hashlib

def deterministic_nonce(private_key, message, n):
    """Derive a deterministic nonce from the private key and message.
    This is a simplified illustration; real RFC 6979 uses HMAC-DRBG."""
    data = f"{private_key}:{message}".encode()
    h = int(hashlib.sha256(data).hexdigest(), 16)
    return (h % (n - 1)) + 1  # ensure k in [1, n-1]

# Same message always produces the same nonce (deterministic)
k1 = deterministic_nonce(d, "message A", n)
k2 = deterministic_nonce(d, "message A", n)
k3 = deterministic_nonce(d, "message B", n)

print(f"k for 'message A' (call 1): {k1}")
print(f"k for 'message A' (call 2): {k2}")
print(f"Same message -> same k? {k1 == k2}")
print(f"\nk for 'message B':          {k3}")
print(f"Different message -> different k? {k1 != k3}")
print(f"\nKey insight: nonce reuse can only happen if the SAME message")
print(f"is signed twice, which produces the SAME signature (harmless).")

Exercises

1. Known offset: Suppose instead of reusing $k$ exactly, the attacker knows that $k_2 = k_1 + \delta$ for a known offset $\delta$. Modify the attack to recover $d$. Hint: subtract the two signing equations and solve the resulting system.

2. Detection: Given a list of 100 ECDSA signatures, write code to check whether any two share the same $r$ value (indicating nonce reuse). How many comparisons are needed?

3. Partial nonce leakage: If an attacker learns just the top 8 bits of $k$ (not the full value), can they still recover $d$? Research the lattice-based nonce recovery attack (Howgrave-Graham and Smart, 2001).

Summary

Aspect	Detail
Vulnerability	Reusing nonce $k$ in two ECDSA signatures
Telltale sign	Two signatures with the same $r$ value
Attack	$k = (e_1 - e_2)(s_1 - s_2)^{-1}$, then $d = (s_1 k - e_1) r^{-1}$
Consequence	Full private key recovery; attacker can forge any signature
Real-world victims	PlayStation 3 (2010), Android Bitcoin wallets (2013)
Fix	RFC 6979 deterministic nonces, or use EdDSA

The nonce-reuse attack is a reminder that cryptographic protocols can be mathematically sound but operationally fragile. A single implementation mistake (reusing a random value) collapses all security. This is why modern designs like EdDSA eliminate randomness from the signing process entirely.

---

Back to Module 06: Elliptic Curves