The hidden number problem and ECDSA nonce leakage

This is where deployed elliptic-curve cryptography actually fails. Not the group, not the curve, not the key length — the per-signature nonce, and a side channel that reveals a fraction of a bit of it.

Problem
Recover d from signatures whose nonces are partly known or biased
Cost
Lattice reduction on a basis of dimension ≈ number of signatures
Leakage needed
A few bits per signature, or a sub-bit bias across many
Affects
ECDSA, DSA, Schnorr variants with a per-message secret nonce
Deployed instances
Minerva, TPM-Fail, LadderLeak, and many wallet key losses

The problem instance

Boneh and Venkatesan's hidden number problem: recover a secret α modulo n given many pairs (ti, ui) with

| αti − ui |n < n / 2ℓ+1 ui approximates αti to ℓ bits

Each sample confines α to a narrow band; enough bands intersect in a single point. Boneh and Venkatesan solved it with lattice reduction for ℓ on the order of √(log n), and the interesting part is how naturally ECDSA hands over exactly these samples.

Why ECDSA is an instance

An ECDSA signature on hash h with private key d and per-message nonce k is (r, s) with r = x(kG) mod n and s = k−1(h + rd) mod n. Rearranged:

k ≡ s−1h + s−1r · d (mod n) k is an affine function of d with publicly known coefficients

So any partial knowledge of k is partial knowledge of an affine image of d — precisely an HNP sample with α = d, ti = si−1ri and ui derived from the leaked bits and si−1hi. The degenerate cases are familiar: a repeated nonce across two signatures gives two linear equations in two unknowns and the key falls out with no lattice at all, which is how the Sony PlayStation 3 signing key and a long series of Bitcoin wallets were lost.

The lattice step

Build a lattice whose vectors encode the HNP congruences, with a final coordinate carrying the unknown. A standard construction from m samples uses the basis

B = [ n·Im | 0 ; t1 … tm , 1/2ℓ ; u1 … um , 0 , n/2ℓ ] One common (m+2)-dimensional embedding; variants abound

The vector corresponding to the true d is unusually short because every error term is bounded by the leakage. Running LLL, or BKZ when the margin is thin, finds it, and d is read off a coordinate. The practical recipe:

  1. Collect signatures and whatever side-channel measurement bounds each nonce.
  2. Filter aggressively — keep only the samples with the strongest bound, since lattice dimension is the cost driver and noisy samples poison the basis.
  3. Reduce. If it fails, resample the subset; success is probabilistic and cheap to retry.
  4. Below about four bits of leakage per signature, switch to Bleichenbacher's Fourier-analytic method, which tolerates far less bias per sample at the price of needing far more of them.

Where the leakage comes from

Every published break in this family began with a nonce that was not uniform, or a computation whose timing depended on it.

  • Modular bias. Generating a nonce by reducing a uniform 256-bit string modulo n biases the top bits whenever n is not a power of two. Small, but HNP-usable in bulk.
  • Non-constant-time scalar multiplication. If the loop runs for the bit-length of k, the signing time reveals that length — a full bit, sometimes more. This was the Minerva family of vulnerabilities, and TPM-Fail in hardware TPMs.
  • Sub-bit leakage. LadderLeak showed key recovery from less than one bit of nonce leakage per signature by combining Bleichenbacher's method with a very large signature corpus.
  • Cache and branch behaviour. Window-based or wNAF multiplication with secret-dependent table indices leaks nonce bits to a co-resident attacker; a long line of results has extracted keys from OpenSSL this way.
  • Outright repetition. Bad entropy at boot, a virtual machine rollback, or an embedded device with no entropy source. Still the most common cause of real losses.

The boundary, and how to close it

The attack needs per-signature secret randomness with exploitable structure. Remove that and the whole class disappears:

  • Deterministic nonces (RFC 6979) or hedged deterministic nonces derive k from the key and message via a PRF, removing entropy failures and modular bias in one step. Hedging with fresh randomness retains protection against fault attacks, which deterministic signing alone makes worse.
  • Constant-time scalar multiplication with a fixed loop count, uniform ladder and no secret-dependent memory addressing removes the timing and cache channels.
  • Rejection sampling or wide reduction removes modular bias where a nonce must be random.
  • Schemes without a fresh nonce per signature — EdDSA derives it deterministically by construction, which is a large part of why it is recommended.

A protocol review that checks curve choice and key length but not nonce generation and scalar-multiplication timing has checked the part that has never failed and skipped the part that has. The same machinery applies beyond signatures: any protocol leaking partial information about a secret exponent — including Diffie–Hellman premaster secrets, as in Boneh and Venkatesan's original motivation — is an HNP instance waiting to be written down.

Primary sources

  1. D. Boneh and R. Venkatesan, "Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes", CRYPTO 1996
  2. N. A. Howgrave-Graham and N. P. Smart, "Lattice attacks on digital signature schemes", Designs, Codes and Cryptography 23 (2001)
  3. P. Q. Nguyen and I. E. Shparlinski, "The insecurity of the elliptic curve digital signature algorithm with partially known nonces", Designs, Codes and Cryptography 30 (2003)
  4. J. Jancar, V. Sedlacek, P. Svenda and M. Sys, "Minerva: the curse of ECDSA nonces", CHES 2020
  5. D. Moghimi, B. Sunar, T. Eisenbarth and N. Heninger, "TPM-FAIL: TPM meets timing and lattice attacks", USENIX Security 2020
  6. D. F. Aranha, F. R. Novaes, A. Takahashi, M. Tibouchi and Y. Yarom, "LadderLeak: breaking ECDSA with less than one bit of nonce leakage", CCS 2020
  7. T. Pornin, "Deterministic usage of DSA and ECDSA", RFC 6979