liberlume-content-v3
lang: en
title: The number used only once
summary: Every digital signature consumes, besides the key, a second secret number generated for the occasion and good only once: the nonce. If it repeats, two signatures give back the private key with a subtraction: it happened to the PlayStation 3 and to Bitcoin wallets on Android in 2013. How the recovery works in ECDSA and in Schnorr, shown on the bytes of real signatures; why a nonce that is merely predictable betrays as well; and the point that concerns Bitcoin: a node validates a signature born from a disastrous nonce like any other, consensus cannot notice.
btc-anchor: 960990,0000000000000000000007c6cbdc6958d83fbfe12368e96f373a23a84ed45276
prev: genesis
--- body ---
Signing does not use the key alone. Every time a wallet produces a signature
it also consumes a second secret number, generated for that occasion and good
for that one only: the **nonce**. The key is kept for years, the nonce lives
the time of one signature and is then useless. Yet it is the fragile piece.
If two signatures from the same key are born from the same nonce, anyone
reading those two signatures derives the private key. Not weakens it: derives
it.
What follows concerns signatures as such, not one system in particular.
Bitcoin is where the thing shows best, because signatures end up on a public
ledger anyone can reread years later, but the most famous case of nonce reuse
is not Bitcoin's.
## The secret used a single time
The first ambiguity to clear up is about the word itself. In Bitcoin jargon
"nonce" also names the number miners vary in search of a valid block: that
one is public, sits in the block header, and finding it by trial is exactly
the job. The signature nonce has nothing to do with it. It is secret, no one
is supposed to search for it, and it is to be used once only.
Nor is it a second key. A private key is a permanent secret that says who can
spend; the nonce holds for a single signature and is then thrown away. And it
is not a complication one would gladly do without: without it, every
signature would hand the key to whoever reads it.
The reason is a count. A published signature is, in essence, an equation, and
it ties three things: the message, the private key and the nonce. The message
is public, and so is the signature itself; the unknowns are two, the key and
the nonce. If the nonce were missing, or were a value the observer knows,
only one unknown would remain and the equation would be solved: the advantage
the nonce takes away from an attacker is exactly this, deriving the private
key from any signature read off the ledger. And every new signature brings
its own nonce, that is, a new unknown along with the new equation: a thousand
signatures are a thousand equations with a thousand and one unknowns, always
one too many for the system to close.
Repeating the nonce removes that margin. Two signatures made with the same
key and the same nonce are two equations with only two unknowns: the count
evens out and the system solves. No need to attack the cryptography,
subtracting one from the other is enough.
## Where it sits, inside a signature
An ECDSA signature is a pair of numbers, `r` and `s`. The second mixes key,
message and nonce. The first comes from the nonce and nothing else: it is the
coordinate of a point obtained by multiplying the nonce by the curve's
generator point.
This is the central fact of the piece, and it should be said slowly. **Half
of what ends up written on the ledger comes from the nonce alone.** Not the
nonce, which stays secret, but a value that depends only on it. Two
signatures with the same nonce therefore have the same `r`, and the
coincidence is visible to anyone, with no calculation, by reading the bytes.
That passage is one-way, and it is the same one that turns a private key into
a public key: a secret number multiplied by the generator point. From `r`
there is no way back to the nonce, as from a public key there is no way back
to the private one. The repetition of `r` is therefore not a way in: it is a
signal, and it only says where to look.
A real ECDSA signature, byte by byte: the one that spent the first payment in history, block 170. Inside the DER envelope sit two numbers: r, which depends only on that signature's nonce, and s, which mixes key, message and nonce. The last byte, outside the envelope, says which part of the transaction the signature covers. Boxes: blue = the bytes announcing what comes next, plus the tail byte saying what the signature covers; grey = how many bytes the next piece takes; yellow = the two numbers. The announcing bytes are fixed codes of the format, the same in every signature; the numbers above the boxes are their byte counts. Verifiable with getrawtransaction f4184fc596403b9d638783cf57adfe4c75c605f6356fbc91338530e9831e9e16.
In the format Bitcoin uses those two numbers sit inside a DER envelope, which
writes every piece always the same way: one byte says what is coming, the
next byte says how many bytes it takes, and then come the actual bytes. So
the first byte announces a sequence and the second says how long it is;
inside, each of the two numbers presents itself the same way, first what it
is, then how long, then the number. At the tail, outside the envelope, one
byte says which part of the transaction the signature covers.
The announcing bytes are fixed codes of the format, not content: `30` means
"here comes a sequence" and `02` "here comes an integer", and they are the
exact same in every signature ever written. From one signature to the next
only the lengths and the two numbers change: worth knowing to read the
figures that follow, where the identical boxes say nothing and the different
ones say everything.
DER stands for *Distinguished Encoding Rules*, and it is a writing convention
born outside Bitcoin, the same one used by the certificates a browser checks
at every site. It is the strict version of a more permissive standard, which
would let the same value be written in several ways: here instead, for a
given value, only one writing is allowed. The rule has earned its keep,
because a signature does not cover itself: as long as nodes accepted loosely
written envelopes, someone could rewrite another's signature in a different,
equally valid form, changing the transaction's identifier without
invalidating it; since 2015 the strict form is a consensus rule (BIP 66).
Inside the envelope, finally, integers are written signed, so a number
starting with a high byte carries a leading zero: this is why the signatures
in these figures take 71, 72 or 73 bytes.
## When it repeats
Before the sums, one thing to clear up: a signature is not a hash. There is a
hash, and it is the message reduced to a number, but it is public and anyone
recomputes it; the signature proper is two numbers obtained with additions,
multiplications and inverses, operations that can be done and undone. And it
must be so, otherwise the signature would not be verifiable: the checker
knows neither the key nor the nonce, so the only thing they can do is verify
that a relation holds among the public values, and a relation can only be
checked if it is arithmetic. The same arithmetic that makes a signature
verifiable allows two of them to be combined.
The signing rules fit in two lines. `d` is the private key, `z` the message
reduced to a number (its hash), `G` the generator point, `n` the order of the
group, and all sums are done modulo `n`:
```
r = x(k · G) the coordinate of the point obtained from the nonce
s = k⁻¹ · (z + r · d) where k is the nonce
```
Now sign twice with the same key and the same nonce, on two different
messages `z₁` and `z₂`. The `r` is the same, because it depends only on the
nonce:
```
s₁ = k⁻¹ · (z₁ + r · d)
s₂ = k⁻¹ · (z₂ + r · d)
```
Subtracting, the term with the key disappears, because it is identical in the
two lines:
```
s₁ - s₂ = k⁻¹ · (z₁ - z₂)
k = (z₁ - z₂) / (s₁ - s₂)
```
`r` is never inverted: the nonce comes out of the difference of the two `s`,
and `r` serves only at the end, as a known number, to derive the key.
With the nonce recovered, the key comes from the first equation, rewritten:
```
d = (s₁ · k - z₁) / r
```
Two subtractions and two divisions, modulo a prime. It is arithmetic a phone
carries out in an instant. No brute force, no elliptic curve broken, no
defect in the mathematics: the mathematics did exactly what it promised, and
it was used twice with the same secret ingredient.
Two signatures from the same key produced with the same nonce. The highlighted r is identical in the two strips, because it depends only on the nonce, and the coincidence can be seen by reading the bytes, with no calculation. The s changes instead, because the message changes: it is precisely that difference which, subtracted, returns first the nonce and then the private key. The two signatures are built with a key created for this figure, which has never owned anything; the script that generates them derives the key from the two signatures and stops if it does not find the starting one.
One clarification that makes the picture exact. It takes the **same key**
signing twice with the same nonce. If two different keys happen to use the
same nonce, the equations remain two and the unknowns become three, and
nothing comes out. The danger therefore does not come from collisions between
strangers: it comes from a wallet repeating itself.
## It was never theoretical
In 2010 it was discovered that the signatures with which the PlayStation 3
authenticated its own code used a **constant** nonce. Not repeated by bad
luck: always the same, written once and for all. The console's signing key
came out by subtraction, with the calculation seen above.
In August 2013 it was discovered that the Android component in charge of
producing secure random numbers was flawed. The advisory published at the
time declared **all** wallets generated on that system up to that point
vulnerable and required moving funds to new keys. The flaw struck in two
distinct places: at the moment keys were born, which came out less
unpredictable than believed, and at the moment of signing, where the nonce
could repeat. Of the second case the traces remain on the ledger, because
signatures with the same `r` can be counted by reading. Those who found them
broke nothing: they read two signatures and did a division.
Worth noting that a single flawed component sufficed to threaten two things
that seem far apart, the key at the moment it is created and the signature at
the moment it is produced. It is the same piece of software, and it is where
nearly all the disasters in this family originated.
## The cure is not more randomness, it is less
The instinctive reaction would be to demand better random generators. The
solution adopted goes the opposite way: **taking chance out of the picture**.
The nonce is not drawn, it is derived from the private key and the message,
with a function that mixes them irreversibly. It is the recipe of RFC 6979
for ECDSA, and the same idea BIP-340 writes into its own specification for
Schnorr signatures, with the added option of auxiliary randomness for those
who have good randomness to add. The choice is not Bitcoin's alone: EdDSA,
another family of signatures in common use, derives the nonce by construction
and provides for no drawing at all.
The advantage is structural, not statistical: two different messages cannot
produce the same nonce by accident, because the nonce is a function of the
message. And signing the very same message twice produces two identical
signatures, which reveals nothing that was not public already.
Here lies the point that usually trips people up: deriving the nonce seems to
make it predictable. It does not, because the private key enters the
derivation. Whoever has the key can recompute the nonce, but whoever has the
key already has everything. Whoever does not is left facing a value they have
no way of guessing. Determined does not mean predictable.
The same signature in two forms. Above, ECDSA, with the DER envelope announcing a sequence and the length of each number; below, BIP-340 Schnorr, sixty-four flat bytes with no envelope. The packaging changes, not the substance: here too the first half depends on the nonce alone and the second mixes key, message and nonce, and here too two signatures with the same nonce hand over the key, with an even shorter calculation.
Worth seeing that the change of form does not change the problem. A Schnorr
signature is simpler, sixty-four flat bytes with no envelope, and its rule is
linear:
```
s = k + e · d where e depends on R, the public key and the message
```
With the same nonce on two different messages the calculation is even
shorter:
```
s₁ - s₂ = (e₁ - e₂) · d
d = (s₁ - s₂) / (e₁ - e₂)
```
One subtraction and one division, without going through the nonce. The form
changed, the failure did not. This is why BIP-340 does not merely recommend a
nonce derivation: it writes it into the specification.
## What consensus cannot see
A node receiving a transaction runs the [lock](/en/bitcoin-locks/) of the
coins being spent and checks that the signature verifies. It does not check
how the nonce was born, and it is not an oversight: it cannot. The nonce is
not in the signature, and nothing in the signature says where it came from. A
signature produced with a disastrous nonce is a valid signature,
indistinguishable from a well-made one, and it is accepted, relayed and
confirmed like any other.
It is not a missing rule someone could add. It is information that never
reaches the verifier. No protocol change can make a node check a piece of
data it does not possess.
One partial consolation remains, and it is best called by its name: the
repetition becomes visible after the fact, because anyone can scan the ledger
looking for two signatures with the same `r`. But by the time it is seen, the
key is already out. It is an autopsy observation, not a defense.
What follows is the thing this piece wanted to say. Verification establishes
that a signature is valid, not that it was produced safely. They are two
different questions, and the ledger answers only the first. The second sits
entirely on the signer's side, inside a program no one else runs and no one
else can check.
## Pairs that get confused
Six distinctions that, held firm, dissolve almost everything:
- **signature nonce ≠ block nonce**: the same word in two places that have
nothing to do with each other; the mining one is public and searched for by
trial, this one is secret and not to be searched for at all;
- **nonce ≠ private key**: the key lasts for years, the nonce holds for a
single signature;
- **repeated nonce ≠ weak key**: the key can be perfect, it is the signature
that handed it over;
- **random ≠ unpredictable**: a generator can produce numbers that look
random and that someone else manages to reproduce;
- **deterministic ≠ predictable**: the derived nonce can be recomputed only
by who already has the key, hence determined and not guessable;
- **valid signature ≠ safe signature**: consensus checks the first and has no
way of checking the second.
## In short
Every signature consumes, besides the key, a secret number good for that one
signature. Half of what remains written on the ledger comes from that number
alone, so its repetition is visible to anyone; and two signatures from the
same key with the same nonce subtract from each other until they give back
the private key, with a few divisions. It has really happened, always from
flawed generators, never from a failure of the cryptography. The defense is
not more randomness but less: the nonce is derived from the key and the
message, so that two different messages cannot collide. And no node can
enforce it, because that piece of data never reaches it: a valid signature
stays valid even when it was born terribly.
## References
- RFC 6979, *Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA)*: [datatracker.ietf.org/doc/html/rfc6979](https://datatracker.ietf.org/doc/html/rfc6979)
- BIP 340, *Schnorr Signatures for secp256k1*: [github.com/bitcoin/bips/blob/master/bip-0340.mediawiki](https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki)
- RFC 8032, *Edwards-Curve Digital Signature Algorithm (EdDSA)*: [datatracker.ietf.org/doc/html/rfc8032](https://datatracker.ietf.org/doc/html/rfc8032)
- BIP 66, *Strict DER signatures* (the strict envelope form as a consensus rule, 2015): [github.com/bitcoin/bips/blob/master/bip-0066.mediawiki](https://github.com/bitcoin/bips/blob/master/bip-0066.mediawiki)
- Bitcoin.org, security advisory on Android wallets (August 2013): [bitcoin.org/en/alert/2013-08-11-android](https://bitcoin.org/en/alert/2013-08-11-android)
- fail0verflow, *Console Hacking 2010 (PS3 Epic Fail)*, 27C3 (the PlayStation 3 signing key): [media.ccc.de/v/27c3-4087-en-console_hacking_2010](https://media.ccc.de/v/27c3-4087-en-console_hacking_2010)
- The library Bitcoin Core uses for signatures, [`libsecp256k1`](https://github.com/bitcoin-core/secp256k1)