Skip to content
ecdsa.com

Hidden number problem

The lattice problem of recovering a secret from many noisy linear relations that reveal a few of its bits, which turns small biases or leaks in ECDSA and DSA nonces into full private-key recovery.
Also written asHNPlattice attackbiased nonce attack

Each ECDSA signature gives s·k = z + r·d (mod n). If the top bits of every k are known to be zero or leak through a side channel, each signature is an approximate linear equation in the private key d; with enough of them, lattice reduction (LLL or BKZ) on a matrix built from the (r, s, z) triples finds d. This is the hidden number problem of Boneh and Venkatesan (1996), applied to DSA by Howgrave-Graham and Smart (2001) and Nguyen and Shparlinski (2002).

Leaking a handful of bits per signature is enough with a few hundred to a few thousand signatures, and recent techniques push the leak below one bit. Documented cases include Minerva (2019, bit-length timing leaks in smart cards and libraries), TPM-Fail (2019, Intel firmware TPM and an STMicroelectronics TPM), LadderLeak (2020) and the 2019 "Biased Nonce Sense" study, which recovered keys from real Bitcoin and Ethereum signatures with short nonces.

Defenses: generate nonces uniformly over the full range (deterministic per RFC 6979, or hedged), compute with constant-time code that does not reveal the nonce's bit length, and treat any reported nonce leak as a key compromise rather than a cosmetic bug.

Standards and references

All terms