Biased Nonce Attack: How a Few Predictable Bits Leak a Signing Key

Q: How is a biased nonce attack different from nonce reuse?

Nonce reuse means two signatures share the exact same nonce, which solves for the private key directly from two equations. A biased nonce attack never repeats a nonce. The nonces are all different but not uniform, so a few of their bits are predictable. That small leak tells you almost nothing per signature, but stacked across hundreds of signatures and solved with a lattice, it recovers the full key.

Q: How many signatures does the attack need?

It depends on how much bias there is. A large bias, such as the top 16 bits of the nonce always being zero, can fall with a few dozen signatures. A tiny bias of two or three known bits needs hundreds to a few thousand. More signatures and more known bits both make the underlying lattice reduction easier to solve.

Q: What makes a nonce biased in real code?

Common causes are a random draw that reads too few bytes, masking off high bits, a modular reduction that skews small values, a weak or poorly seeded random number generator, and side channels such as timing that leak a couple of nonce bits per signature. Any of these leaves structure in the nonce that a lattice can exploit.

Q: How do I prevent a biased nonce attack?

Use deterministic nonces as described in RFC 6979, which derive the nonce from the private key and message hash with HMAC so there is no RNG bias. Consider a hedged nonce that also mixes in fresh randomness. Audit any RNG you do use, write the scalar multiplication in constant time to stop side channel leaks, and prefer libraries that do all of this by default.

Signature schemes like ECDSA and Schnorr need a fresh random number for every signature. That number is the nonce, sometimes called k. Most people know that repeating a nonce is fatal. Fewer know that you do not need a repeat to lose the key. A biased nonce attack recovers the private key when the nonce is only slightly predictable, a handful of bits that are always zero, or a generator that leans one way. Gather enough signatures and a lattice turns that small leak into the whole secret.

How a nonce is supposed to behave

In ECDSA each signature uses a nonce k drawn uniformly at random from the range 1 to n-1, where n is the order of the curve group. The signature is a pair (r, s) where r comes from the point k*G and s = k^-1 * (h + r*d) mod n. Here h is the message hash and d is the private key. The nonce must stay secret, and it must be uniform. Any structure you can see in k is structure an attacker can use.

Reuse is the loud failure

If you sign two different messages with the same k, both signatures share the same r, and two equations in two unknowns solve directly for d. That is the classic break covered in ECDSA nonce reuse. It is one repeated value and the key falls out in a line of algebra.

Bias is the quiet failure

A biased nonce attack is subtler and, in practice, more common. The nonces are all different, so nothing looks wrong. But they are not uniform. Maybe the top 8 bits are always zero because the generator returns a value a little too short. Maybe a modulo reduction skews the distribution. Maybe a few low bits are fixed by a buggy conversion. Each signature now quietly encodes a linear relation between the key and a small unknown. One such relation tells you almost nothing. Hundreds of them, stacked together, pin the key exactly.

You do not need to see the nonce. You only need to know that a few of its bits are not random, and that the scheme will sign as many messages as you ask.

Turning a small bias into the key with a lattice

Each signature gives you the public equation s = k^-1 * (h + r*d) mod n. Rearrange it to express the nonce k as a known value plus an unknown multiple of the private key, all mod n. If k were full size this tells you nothing useful. But if you know k is small, say the top bits are zero so k < 2^248 on a 256 bit curve, then you know a linear combination of known quantities and the secret is unusually small.

That is the hidden number problem. Write one such constraint per signature as a row, and you get a lattice, a grid of integer combinations, in which the private key corresponds to an unusually short vector. A lattice reduction algorithm such as LLL or BKZ finds that short vector, and out of it drops d.

# one row per signature, schematically
# t_i and u_i are public, built from (r_i, s_i, h_i)
#   k_i = t_i * d + u_i   (mod n),   with k_i known to be small
# stack many rows, reduce the lattice, read d from the short vector
t_i = r_i * s_i_inv mod n
u_i = h_i * s_i_inv mod n

How many signatures you need scales with how much bias there is. A large bias, like the top 16 bits always zero, can fall with a few dozen signatures. A tiny bias of 2 or 3 known bits needs hundreds to a few thousand, but the attack still works. More signatures and more known bits both make the lattice easier. This is the same engine behind partial nonce leak results that have broken real deployments where a side channel exposed a couple of bits of k per signature, the kind of timing leak covered in the RSA timing attack.

Where the bias comes from

Nobody designs a biased nonce on purpose. It leaks in through ordinary mistakes.

A short or truncated random draw. Reading fewer bytes than the curve needs, or generating a value and masking off high bits, leaves the top bits predictable.
Bad modular reduction. Taking a random number mod n without care skews small values slightly more likely, a measurable bias at scale.
A weak or seeded generator. A non cryptographic RNG, or one seeded with low entropy at boot, produces values with structure an attacker can model.
Side channels. Timing or cache behavior during the scalar multiplication can leak a few bits of k, which feeds the lattice directly even when the generator is fine.

How to defend against a biased nonce attack

Use deterministic nonces. RFC 6979 derives k from the private key and the message hash with HMAC, so the nonce is reproducible, uniform, and free of RNG bias. The same message always gives the same signature, which is fine, and two different messages never collide.
Consider a hedged or synthetic nonce. Mix fresh randomness into the deterministic derivation so a single bad RNG read cannot bias the output, and a fault cannot repeat a nonce.
Audit the RNG. If you must draw k at random, use a real CSPRNG, draw the full width, and reduce into range without skew. Seed it properly before first use.
Write the scalar multiplication in constant time. Stop the side channel that leaks nonce bits. See constant time comparison for the same idea applied to secret comparisons.
Prefer schemes and libraries that make this the default. Modern signing libraries ship RFC 6979 or hedged nonces out of the box. Use the high level call rather than feeding your own k.

For the wider family of these bugs, see our hub on cryptographic oracle attacks, or start with the vulnerability basics category.

The assumption that breaks

A biased nonce attack is a clean example of math that is sound being undone by a usage detail. ECDSA is fine. The signing equation is fine. The failure is the belief that k is uniform when a short read or a skewed reduction made it lean. The library call looks correct on its line, so the bias never shows up in review, and only a lattice over many signatures reveals it. Finding this kind of flaw means reasoning about how a nonce is actually produced and used in the app, not just whether the function was called. That is what an autonomous researcher that tests assumptions is built to do. Read more on our about page.

Frequently asked questions

How is a biased nonce attack different from nonce reuse?

Nonce reuse means two signatures share the exact same nonce, which solves for the private key directly from two equations. A biased nonce attack never repeats a nonce. The nonces are all different but not uniform, so a few of their bits are predictable. That small leak tells you almost nothing per signature, but stacked across hundreds of signatures and solved with a lattice, it recovers the full key.

How many signatures does the attack need?

It depends on how much bias there is. A large bias, such as the top 16 bits of the nonce always being zero, can fall with a few dozen signatures. A tiny bias of two or three known bits needs hundreds to a few thousand. More signatures and more known bits both make the underlying lattice reduction easier to solve.

What makes a nonce biased in real code?

Common causes are a random draw that reads too few bytes, masking off high bits, a modular reduction that skews small values, a weak or poorly seeded random number generator, and side channels such as timing that leak a couple of nonce bits per signature. Any of these leaves structure in the nonce that a lattice can exploit.

How do I prevent a biased nonce attack?

Use deterministic nonces as described in RFC 6979, which derive the nonce from the private key and message hash with HMAC so there is no RNG bias. Consider a hedged nonce that also mixes in fresh randomness. Audit any RNG you do use, write the scalar multiplication in constant time to stop side channel leaks, and prefer libraries that do all of this by default.

Put an autonomous researcher on your own systems

UnboundCompute is an autonomous security researcher that reasons about how an application fits together and proves the access control and injection bugs it finds. We are opening a small number of founding design partner seats: private early access pointed at a staging target you choose, and a say in what it looks for. If your team ships software worth pressure testing, apply to the design partner program.