schnorr-nonce-reuse.ipynb

Kernel: SageMath 10.0

Break: Schnorr Protocol Nonce Reuse

Module 09 | Breaking Weak Parameters

When the prover reuses a nonce $k$ across two Schnorr protocol runs, the secret key falls out with simple algebra.

Why This Matters

The Schnorr protocol (from 09d) requires the prover to choose a fresh random nonce $k$ for every protocol execution. The commitment $R = g^k$ is sent to the verifier, and the response $s = k + c \cdot x \bmod q$ encodes both $k$ and the secret $x$.

The nonce $k$ acts as a one-time pad for $c \cdot x$: without knowing $k$, nobody can extract $x$ from $s$. But if the same $k$ is used twice with different challenges, we get two equations in two unknowns ($k$ and $x$), and the system solves trivially.

This is not a theoretical concern:

• Sony PS3 (2010): Sony used a fixed nonce for ECDSA signatures on firmware updates. The hacker group fail0verflow extracted the master signing key.

• Android Bitcoin wallets (2013): A faulty RNG produced repeated nonces, leaking users' private keys.

• ROCA (2017): Weak nonce generation in Infineon smartcards allowed key recovery.

The same algebra applies to Schnorr identification, Schnorr signatures, and ECDSA.

The Scenario

Alice proves knowledge of $x$ (where $y = g^x \bmod p$) using the Schnorr protocol. She runs the protocol twice, using the same nonce $k$ both times but receiving different challenges $c_1$ and $c_2$.

Recall the Schnorr protocol:

Step	Action	Computation
Commit	Prover sends $R$	$R = g^k \bmod p$
Challenge	Verifier sends $c$	Random $c \in \{0, \ldots, q-1\}$
Response	Prover sends $s$	$s = k + c \cdot x \bmod q$

If $k$ is reused, an eavesdropper who sees both transcripts $(R, c_1, s_1)$ and $(R, c_2, s_2)$ can recover $x$.

Let's set up concrete parameters and demonstrate the full attack.

# === Schnorr Group Setup ===
# Safe prime p = 2q + 1 so we get a prime-order subgroup of order q.

def schnorr_group_setup(bits=20):
    """Generate Schnorr group parameters (p, q, g)."""
    while True:
        q = random_prime(2^bits, lbound=2^(bits-1))
        p = 2 * q + 1
        if is_prime(p):
            break
    while True:
        h = randint(2, p - 2)
        g = power_mod(h, 2, p)
        if g != 1:
            break
    return p, q, g

p, q, g = schnorr_group_setup(bits=20)
print(f"Prime p = {p}")
print(f"Subgroup order q = {q}")
print(f"Generator g = {g}")
print(f"Verify: g^q mod p = {power_mod(g, q, p)}  (should be 1)")

# Alice's key pair
x = randint(1, q - 1)          # SECRET key
y = power_mod(g, x, p)         # PUBLIC key
print(f"\nAlice's secret key: x = {x}")
print(f"Alice's public key: y = g^x mod p = {y}")

Step 1: Alice Runs the Protocol Twice with the Same Nonce

Alice uses the same nonce $k$ in two protocol executions. The verifier (or two different verifiers) sends different challenges $c_1$ and $c_2$.

Run 1: $R = g^k$, challenge $c_1$, response $s_1 = k + c_1 \cdot x \bmod q$

Run 2: $R = g^k$ (same!), challenge $c_2$, response $s_2 = k + c_2 \cdot x \bmod q$

The telltale sign: both transcripts have the same commitment $R$.

# === Alice reuses the nonce k (the fatal mistake) ===

k = randint(1, q - 1)           # Alice's nonce
R = power_mod(g, k, p)          # Commitment (same in both runs)

# Run 1: verifier sends challenge c1
c1 = randint(1, q - 1)
s1 = (k + c1 * x) % q

# Run 2: different challenge c2
c2 = c1
while c2 == c1:
    c2 = randint(1, q - 1)
s2 = (k + c2 * x) % q

print("  TWO SCHNORR PROTOCOL RUNS (SAME NONCE)")
print(f"\nBoth share: R = {R}  <-- SAME commitment!")
print(f"\nRun 1: c1 = {c1}, s1 = {s1}")
print(f"Run 2: c2 = {c2}, s2 = {s2}")

# Verify both transcripts are valid
def schnorr_verify(p, q, g, y, R, c, s):
    """Verifier checks: g^s == R * y^c mod p."""
    lhs = power_mod(g, s, p)
    rhs = (R * power_mod(y, c, p)) % p
    return lhs == rhs

print(f"\nRun 1 valid? {schnorr_verify(p, q, g, y, R, c1, s1)}")
print(f"Run 2 valid? {schnorr_verify(p, q, g, y, R, c2, s2)}")
print(f"\nSame R in both runs, this is the smoking gun.")

Step 2: The Algebra of the Attack

An eavesdropper (Eve) observes both transcripts. She writes down the two response equations:

$$s_1 = k + c_1 \cdot x \pmod{q}$$$$s_2 = k + c_2 \cdot x \pmod{q}$$

Subtract the second from the first:

$$s_1 - s_2 = (c_1 - c_2) \cdot x \pmod{q}$$

The nonce $k$ cancels out! Since $q$ is prime and $c_1 \neq c_2$, the value $(c_1 - c_2)$ is invertible mod $q$. Solve for $x$:

$$\boxed{x = \frac{s_1 - s_2}{c_1 - c_2} \pmod{q}}$$

Two equations, two unknowns, high school algebra. The secret key is gone.

# === Eve's Attack: Extract the secret key x ===

# Eve knows: R, c1, s1, c2, s2 (from observing both protocol runs)
# Eve does NOT know: k, x

print("  EVE'S NONCE REUSE ATTACK")

print(f"\nEve's observations:")
print(f"  R  = {R}")
print(f"  c1 = {c1}, s1 = {s1}")
print(f"  c2 = {c2}, s2 = {s2}")

# Step 1: Recover the secret key x
x_recovered = ((s1 - s2) * inverse_mod(c1 - c2, q)) % q

print(f"\n--- Recovering x ---")
print(f"  x = (s1 - s2) / (c1 - c2) mod q")
print(f"  x = ({s1} - {s2}) / ({c1} - {c2}) mod {q}")
print(f"  x = {(s1 - s2) % q} * {inverse_mod(c1 - c2, q)} mod {q}")
print(f"  x_recovered = {x_recovered}")
print(f"  x_actual    = {x}")
print(f"  Secret key recovered? {x_recovered == x}")

# Bonus: Eve can also recover the nonce k
k_recovered = (s1 - c1 * x_recovered) % q
print(f"\n--- Recovering k (bonus) ---")
print(f"  k_recovered = {k_recovered}")
print(f"  k_actual    = {k}")
print(f"  Nonce recovered? {k_recovered == k}")

# === Verification: Eve can now impersonate Alice ===

# Eve proves knowledge of x to any verifier, using the recovered key
print("  EVE IMPERSONATES ALICE")

for i in range(5):
    # Eve runs a legitimate Schnorr proof using x_recovered
    k_eve = randint(1, q - 1)  # Eve uses a fresh nonce (she learned her lesson)
    R_eve = power_mod(g, k_eve, p)
    c_eve = randint(1, q - 1)  # verifier's challenge
    s_eve = (k_eve + c_eve * x_recovered) % q
    valid = schnorr_verify(p, q, g, y, R_eve, c_eve, s_eve)
    print(f"  Proof {i+1}: R={R_eve}, c={c_eve}, s={s_eve}  Valid? {valid}")

print(f"\nEve now owns Alice's identity. Every proof verifies against")
print(f"Alice's public key y = {y}.")
print(f"TOTAL BREAK: one nonce reuse = complete key compromise.")

The Fix: Deterministic Nonce Derivation

The root cause is that the Schnorr protocol demands a fresh, unpredictable, never-repeated nonce $k$ for every execution. This is a dangerous requirement: one failure is catastrophic.

RFC 6979 (2013) eliminates nonce reuse by deriving $k$ deterministically:

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

Properties:

• Same $(x, m)$ pair always produces the same $k$ (and the same proof/signature), deterministic.

• Different messages produce different $k$ values, no collisions.

• No randomness needed at proving time, no RNG to fail.

EdDSA (Ed25519) takes this further: the nonce is $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.

# === Deterministic Nonce Derivation (simplified RFC 6979 idea) ===
import hashlib

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

# Same message always produces the same nonce
k1 = deterministic_nonce(x, "prove identity session A", q)
k2 = deterministic_nonce(x, "prove identity session A", q)
k3 = deterministic_nonce(x, "prove identity session B", q)

print(f"k for 'session A' (call 1): {k1}")
print(f"k for 'session A' (call 2): {k2}")
print(f"Same message -> same k?     {k1 == k2}")
print(f"\nk for 'session B':          {k3}")
print(f"Different message -> different k? {k1 != k3}")
print()
print("With deterministic nonces, the only way to get the same k")
print("is to prove the same statement twice, which produces the")
print("same transcript (harmless, no new information for Eve).")

Exercises

Exercise 1: Known Nonce Offset

Suppose Alice does not reuse $k$ exactly, but the attacker knows that $k_2 = k_1 + \delta$ for a known constant $\delta$. The two transcripts are:

$$s_1 = k_1 + c_1 x \pmod{q}, \quad s_2 = (k_1 + \delta) + c_2 x \pmod{q}$$

Subtract: $s_1 - s_2 = -\delta + (c_1 - c_2)x$, so $x = (s_1 - s_2 + \delta) / (c_1 - c_2) \bmod q$.

Verify this with the concrete parameters below.

# === Exercise 1: Known nonce offset attack ===

delta = 42  # known offset between the two nonces
k1_ex = randint(1, q - 1)
k2_ex = (k1_ex + delta) % q  # k2 = k1 + delta

R1_ex = power_mod(g, k1_ex, p)
R2_ex = power_mod(g, k2_ex, p)

c1_ex = randint(1, q - 1)
c2_ex = c1_ex
while c2_ex == c1_ex:
    c2_ex = randint(1, q - 1)

s1_ex = (k1_ex + c1_ex * x) % q
s2_ex = (k2_ex + c2_ex * x) % q

# Attack: x = (s1 - s2 + delta) / (c1 - c2) mod q
x_offset_attack = ((s1_ex - s2_ex + delta) * inverse_mod(c1_ex - c2_ex, q)) % q

print(f"Nonce offset: delta = {delta}")
print(f"k1 = {k1_ex}, k2 = k1 + delta = {k2_ex}")
print(f"Note: R1 = {R1_ex} != R2 = {R2_ex}  (commitments differ!)")
print(f"\nRecovered x = {x_offset_attack}")
print(f"Actual x    = {x}")
print(f"Match? {x_offset_attack == x}")
print(f"\nEven without identical R values, a known relationship")
print(f"between nonces is enough to extract the secret key.")

Summary

Aspect	Detail
Vulnerability	Reusing nonce $k$ in two Schnorr protocol runs
Telltale sign	Two transcripts with the same commitment $R$
Attack	$x = (s_1 - s_2)(c_1 - c_2)^{-1} \bmod q$
Consequence	Full secret key recovery; attacker impersonates prover
Real-world victims	PS3 (2010), Android Bitcoin wallets (2013)
Fix	RFC 6979 deterministic nonces, or use EdDSA
Generalization	Any known relationship between nonces (e.g., $k_2 = k_1 + \delta$) is equally fatal

The nonce reuse attack is a direct application of special soundness from 09d: the extraction formula that proves the protocol is sound is exactly the formula an attacker uses when nonces collide. Special soundness is a security feature (it proves the protocol cannot be cheated), but it becomes a weapon when the prover violates the protocol's requirements.

---

Back to Module 09: Commitment Schemes and Sigma Protocols