Signature Nonces: The Single Secret That Breaks ECDSA

ECDSA is the most widely deployed public-key signature scheme, and its failure mode is unlike anything in RSA. The private key is never used directly in the output. Instead each signature consumes a fresh random value, and that value is as sensitive as the key itself — worse, in one respect: it must be used exactly once, and a single reuse across two signatures reveals the key by elementary algebra.

The signature equation and what it exposes

For a curve of prime order $n$ with base point $G$, the private key is $d$ and the public key is $Q = dG$. To sign a message hash $z$:

1. Draw a nonce $k$ uniformly from $[1, n-1]$.
2. Compute $R = kG$ and take $r = R_x \bmod n$.
3. Compute $s = k^{-1}(z + rd) \bmod n$.
4. Output $(r, s)$.

Verification recomputes $R’ = s^{-1}zG + s^{-1}rQ$ and checks that its x-coordinate reduces to $r$. The check works because $s^{-1}zG + s^{-1}r(dG) = s^{-1}(z + rd)G = kG$.

Read step 3 as a linear equation in two unknowns, $k$ and $d$. One signature gives one equation. Two signatures with the same $k$ give two equations:

$$s_1 = k^{-1}(z_1 + r_1 d), \qquad s_2 = k^{-1}(z_2 + r_2 d)$$

Subtracting eliminates $d$‘s coefficient only if $r_1 = r_2$, which holds when the same $k$ was used, since $r$ depends only on $k$. Then $k = (z_1 - z_2)/(s_1 - s_2) \bmod n$ and $d = (s_1 k - z_1)/r \bmod n$. Two signatures, one modular inversion, and the key is out. No search, no computation of any difficulty.

def recover_key(z1, r, s1, z2, s2, n):
    k = (z1 - z2) * pow(s1 - s2, -1, n) % n
    return (s1 * k - z1) * pow(r, -1, n) % n

The attack does not require the nonces to be equal by accident. It applies to any device that generates them from a predictable source, and it applies across signatures from the same key even if they are made years apart — the algebra does not care about time.

Why reuse happens without anyone reusing a value

The failure is almost never a deliberate reuse of a stored nonce. It comes from the generator behind the nonce.

Weak randomness. A nonce drawn from a source with insufficient entropy repeats within a modest number of signatures by the birthday bound: with a $b$-bit nonce space, a collision is likely after about $2^{b/2}$ signatures. If the source produces only a few thousand distinct values because of a poorly seeded generator, collisions occur quickly. The historical failures in this class were devices whose random source was identical across boots or across devices, so two different machines produced the same nonce for the same key.

Truncation and bias. A nonce that is uniform over 256 bits but truncated to 200, or one generated by a process with a slight modular bias, does not repeat but is not uniform. These are attacked by lattice methods rather than by subtraction. Given many signatures where $k$ is known to lie in a smaller range, the equations $s_i k_i - r_i d \equiv z_i \pmod n$ form a system that a lattice reduction finds the small solution to. The number of signatures needed grows as the bias shrinks; a leak of a few bits per nonce is enough over a few hundred signatures. Nguyen and Shparlinski showed the technique against DSA, and it applies to ECDSA unchanged.

Faults. A signing operation interrupted or perturbed so that it produces a signature with a faulty $k$ but a correct $r$, or the reverse, produces a pair of equations that differ only in the faulty component. The difference is again solvable.

The common thread is that the security of the scheme depends on the nonce being uniform, independent, and used once. Any deviation is not a reduction in security margin; it is a structural break, because the signature equation is linear and linear systems with a leaked variable are solved, not searched.

Deterministic nonces and the removal of the requirement

The standard answer is RFC 6979: derive $k$ deterministically from the private key and the message hash using a hash-based construction, so that no randomness is consumed at signing time.

The construction is an HMAC-based generator. It initialises two state values from the private key and the message hash, then iterates HMAC to produce candidate nonces until one lies in the valid range. The message hash is an input, so different messages produce different nonces; the private key is an input, so an attacker who knows the message cannot predict the nonce without the key.

K = 0x00...00 ; V = 0x01...01
K = HMAC_K(V || 0x00 || int2octets(d) || bits2octets(z))
V = HMAC_K(V)
K = HMAC_K(V || 0x01 || int2octets(d) || bits2octets(z))
V = HMAC_K(V)
loop:
    V = HMAC_K(V)
    k = bits2int(V)          # retry with K = HMAC_K(V || 0x00) if out of range

Three properties follow. There is no nonce reuse, because the same $(d, z)$ always yields the same $k$ and a repeated message with the same key yields a repeated signature — which is harmless, since it is the same signature. There is no dependence on a random source at signing time, so a device with a broken entropy source still signs safely. And the nonce is unpredictable to anyone without $d$, because it is the output of an HMAC keyed with a value derived from $d$.

The last point is the security argument, and it has a subtlety: deterministic nonces make the nonce a deterministic function of the key, so any side channel that leaks the nonce leaks information about the key. The scheme removes the randomness failure mode but not the implementation failure mode. A signing routine that is not constant-time still leaks through the scalar multiplication, whatever produced the scalar.

Deterministic derivation also changes the failure mode for repeated messages. Under randomised nonces, signing the same message twice produces two different signatures, and an observer cannot tell. Under deterministic nonces, it produces byte-identical signatures, which reveals that the same message was signed. For most protocols that is not sensitive — the message is usually already visible — but it is a difference worth knowing.

Hedged and randomised variants

A middle ground derives the nonce from both the key and fresh randomness, hashing them together. The result is unpredictable even if the random source is weak, because the key contributes entropy, and different across repeated signatures, because the randomness does. This hedged construction is what several modern libraries use by default, and it recovers the property that two signatures over the same message differ.

The trade-off is that it reintroduces a dependency on a random source, though a benign one: a weak source degrades to the deterministic case rather than to a break, because the key’s contribution still prevents an attacker from predicting or controlling the nonce. That property — graceful degradation rather than catastrophic failure — is the reason the hedged design is attractive.

Verification-side issues that are not about nonces

Signature verification has its own edge cases, and they matter because a verifier that accepts a non-canonical signature enables malleability.

Range checks on $r$ and $s$. Both must lie in $[1, n-1]$. A verifier that accepts $s = 0$ or $r = 0$ accepts signatures that the signer could not have produced, and one that accepts values above $n$ accepts alternative encodings of the same signature. The second is the malleability problem: given a valid $(r, s)$, the pair $(r, n - s)$ is also valid for some schemes under some conventions, so a signature is not a unique object unless the verifier enforces the range.

Point decoding. The public key and the ephemeral point must be validated as described in Elliptic Curve Point Arithmetic and Validation. A verifier that accepts an invalid public key can be made to verify signatures under a key that is not the claimed one.

Hash truncation. For curves whose order is shorter than the hash output, the hash is truncated to the bit length of $n$ before use. The truncation must be by bits, not by bytes, and the resulting value must be reduced mod $n$. Getting this wrong produces signatures that verify under one implementation and not another, and in the worst case produces a value that is not reduced at all.

The general lesson about linear schemes

RSA signatures are deterministic and have no per-signature secret; their failure modes are about the encoding, covered in RSA Padding and Why Textbook RSA Fails. ECDSA’s failure mode is about the per-signature secret, and it is worse in kind: a single leaked nonce is a total break, not a weakening. The reason is that the signature is a linear equation in the key and the nonce, so partial information about either is directly solvable.

Schnorr-style signatures, including EdDSA, have a similar structure with a different equation, and they inherit the same requirement that the nonce be unique and unpredictable. Ed25519 derives its nonce deterministically from the key and the message by construction, which is why the scheme does not expose a random-nonce parameter at all. The requirement is not removed; it is moved out of the caller’s reach.