Cryptanalysis: Nonce Reuse, Bias, & RFC 6979

The security of the Elliptic Curve Digital Signature Algorithm (ECDSA) is incredibly fragile. While the mathematics of the signature are airtight, a single flaw in how the ephemeral random key (the nonce, $k_{\text{ephemeral}}$) is generated will leak the user's private key instantly.

Let's explore the algebraic mechanics of how attackers exploit nonce flaws and how modern wallets prevent them.

---

💥 The Nonce-Reuse Disaster

In ECDSA, the ephemeral key $k_{\text{ephemeral}}$ is called a "nonce" because it must be used only once.

Suppose a buggy wallet signs two different transactions (with message hashes $z_1$ and $z_2$) using the exact same private key $k$ and the exact same nonce $k_{\text{ephemeral}}$.

Because they use the same nonce, both signatures will share the exact same $r$ component ($r = x_R \pmod n$). An attacker monitoring the blockchain scans for transactions sharing the same public key and $r$ value. Once found, they extract the private key instantly using simple algebra:

⚙️ Step-by-Step Key Extraction Proof

1. Recall the two signature equation components:

$$s_1 \equiv k_{\text{ephemeral}}^{-1} \cdot (z_1 + r \cdot k) \pmod n$$

$$s_2 \equiv k_{\text{ephemeral}}^{-1} \cdot (z_2 + r \cdot k) \pmod n$$

1. Subtract $s_2$ from $s_1$:

$$s_1 - s_2 \equiv k_{\text{ephemeral}}^{-1} \cdot (z_1 - z_2) \pmod n$$

1. Multiply both sides by $k_{\text{ephemeral}} \cdot (s_1 - s_2)^{-1}$ to isolate the secret nonce:

$$k_{\text{ephemeral}} \equiv \frac{z_1 - z_2}{s_1 - s_2} \pmod n$$

1. With the secret nonce $k_{\text{ephemeral}}$ exposed, substitute it back into the first signing equation to solve for the private key $k$:

$$k \equiv \frac{s_1 \cdot k_{\text{ephemeral}} - z_1}{r} \pmod n$$

In just four algebraic steps, the secret private key $k$ is fully extracted, and the attacker sweeps all associated funds. This exploit is not theoretical; early Android Bitcoin wallets in 2013 suffered from a bug in Java's SecureRandom class that led to repeated nonces and massive coin thefts.

---

🕸️ The Hidden Number Problem (HNP) & Nonce Bias

What if the nonce is not completely repeated, but is slightly biased or predictable?

Suppose an implementation flaw causes the first 4 bits of the 256-bit nonce $k_{\text{ephemeral}}$ to always be zero, or leaks those bits via a timing analysis attack. * In cryptography, this is formulated as the Hidden Number Problem (HNP). * By observing several dozen signatures and knowing only a tiny prefix (e.g., 4 or 5 bits) of each nonce, an attacker can construct a high-dimensional mathematical matrix known as a lattice. * Using lattice reduction algorithms like LLL (Lenstra–Lenstra–Lovász) or BKZ, the attacker can find the "shortest vector" or "closest vector" within this lattice. * Solving this lattice optimization problem reveals the exact private key $k$ in seconds.

This proves that in ECDSA, even $99\%$ randomness is fatal. The nonce must be completely, uniformly random down to every single bit.

---

🔒 The Solution: Deterministic Nonces (RFC 6979)

To completely eliminate nonce-reuse and nonce-bias vulnerabilities, modern Bitcoin wallets do not use random number generators during signing. Instead, they implement the RFC 6979 standard.

RFC 6979 generates the nonce deterministically by hashing the private key $k$ and the transaction message hash $z$ together using an HMAC-SHA256 loop:

$$k_{\text{ephemeral}} = \text{HMAC-SHA256}(k \parallel z)$$

┌─────────────────────────┐     ┌─────────────────────────┐
│     Private Key (k)     │     │   Message Hash (z)      │
└────────────┬────────────┘     └────────────┬────────────┘
             │                               │
             └───────────────┬───────────────┘
                             ▼
               ┌───────────────────────────┐
               │     HMAC-SHA256 LOOP      │ (RFC 6979 Deterministic Mixing)
               └─────────────┬─────────────┘
                             ▼
               ┌───────────────────────────┐
               │    Deterministic Nonce    │ (Different for every transaction;
               └───────────────────────────┘  completely uniform randomness)

Why RFC 6979 is Bulletproof:

1. No Nonce Reuse: If the transaction data changes, the message hash $z$ changes, ensuring the derived nonce is completely different.
2. No Nonce Bias: The output of HMAC-SHA256 is cryptographically uniform, meaning the nonce has zero mathematical bias.
3. Entropy Independent: Because the nonce is computed deterministically from the key and the message, the wallet does not need to query hardware random sensors during signing, rendering random generator bugs completely obsolete.