Lattice Attacks on ECDSA: The Hidden Number Problem Explained

Lattices are not only a foundation for post-quantum cryptography. They are also one of the most effective tools for breaking classical signatures that are implemented carelessly. If an ECDSA implementation leaks even a few bits of each random nonce, through timing, a biased random number generator or a cache side channel, a lattice reduction algorithm such as LLL can combine those scraps into the full private key. The underlying mathematical problem is the hidden number problem (HNP), introduced by Boneh and Venkatesan in 1996. This guide builds the attack lattice step by step, runs it on a toy curve, and ends with the defenses that close the hole.

Why the ECDSA nonce is as secret as the key

Let $G$ be a point of prime order $n$ , let $d$ be the private key and let $h$ be the hash of the message. To sign, the signer picks a fresh nonce $k \in [1, n-1]$ , sets $r$ to the x-coordinate of $kG$ reduced mod $n$ , and computes

s = k^{-1}(h + r\,d) \bmod n.

The pair $(r,s)$ is public. Rearranging gives $d = r^{-1}(s\,k - h) \bmod n$ , so anyone who learns a single nonce completely learns the key. The degenerate case is reusing a nonce: two signatures with the same $k$ give two linear equations in two unknowns, and simple algebra recovers $k$ and then $d$ . That is how the fail0verflow team recovered Sony’s PlayStation 3 signing key in 2010, because the same nonce had been used for every signature.

The lattice attack handles the much subtler case where no nonce is ever revealed in full, but each one is slightly predictable: for example, its top few bits are always zero, or a timing measurement tells you that they probably are.

The hidden number problem

Divide the signing equation by $s$ . For every signature $i$ define the public values $t_i = r_i s_i^{-1} \bmod n$ and $u_i = h_i s_i^{-1} \bmod n$ . Then

k_i \equiv t_i\, d + u_i \pmod n.

Without extra information this says nothing: $k_i$ is uniform, so every $d$ is consistent. Now suppose the attacker knows that every nonce is small, $0 \le k_i < B$ with $B = n / 2^{\ell}$ , because its top $\ell$ bits are zero. (Known nonzero top bits reduce to this case by subtracting them off, and known low bits by a similar shift.) The hidden number problem asks: given many pairs $(t_i, u_i)$ such that $t_i d + u_i \bmod n$ is smaller than $B$ , find the hidden number $d$ .

Each signature contributes about $\ell$ bits of information about $d$ . Since $d$ has about $\log_2 n$ bits, you need at least $m \gtrsim \log_2 n / \ell$ signatures, and a lattice turns that information-theoretic count into an algorithm.

Building the attack lattice

The congruences say that the vector of nonces is close to a lattice point: each $k_i$ equals $t_i d + u_i$ minus some multiple $c_i n$ . The standard way to exploit this is an $(m+2)$ -dimensional lattice whose basis rows are

\begin{pmatrix} n & & & & 0 & 0 \\ & n & & & 0 & 0 \\ & & \ddots & & \vdots & \vdots \\ & & & n & 0 & 0 \\ t_1 & t_2 & \cdots & t_m & B/n & 0 \\ u_1 & u_2 & \cdots & u_m & 0 & B \end{pmatrix}

Take $d$ copies of the $t$ -row, one copy of the $u$ -row, and subtract $c_i$ copies of each $n$ -row. The result is the lattice vector

v = \bigl(k_1, \dots, k_m,\ dB/n,\ B\bigr).

Every coordinate of $v$ is at most $B$ , so its length is at most $B\sqrt{m+2}$ . This is the whole trick: an unusually short vector that carries the key in its second-to-last coordinate.

Why the scaling factors B/n and B?

The two extra coordinates are weights chosen so that every entry of the target vector has the same size as a nonce. The key $d$ can be as large as $n$ , so the factor $B/n$ shrinks $d B/n$ to below $B$ . The last coordinate is an embedding constant: it turns the close-vector problem “find the lattice point nearest to $(u_1,\dots,u_m)$ ” into a short-vector problem (Kannan’s embedding), and setting it to $B$ keeps it on the same scale. If one coordinate were much larger than the others, the target would stop being the shortest vector and reduction would find something else. In code, multiply every entry by $n$ to keep the basis integral.

Is $v$ really the shortest vector? The lattice has determinant $n^{m-1}B^2$ , so by the Gaussian heuristic a random vector in it has length about $\sqrt{(m+2)/(2\pi e)}\,(n^{m-1}B^2)^{1/(m+2)}$ . Requiring $\|v\|$ to be smaller and substituting $B = n/2^{\ell}$ gives roughly

m\,\ell \;>\; \log_2 n + \tfrac{m+2}{2}\log_2(2\pi e).

The first term is the information count from above. The second is the price of using a lattice, about two extra bits per signature. It explains why lattice attacks are comfortable with four or more leaked bits per nonce and struggle as the leak approaches one bit.

Solving it: LLL, BKZ, or CVP

When the gap between $\|v\|$ and the Gaussian heuristic is large, plain LLL finds $v$ . With less leakage per signature you need more signatures, the lattice dimension grows, and you move up to BKZ or sieving to solve the underlying shortest vector problem. Equivalently, you can drop the embedding row and run a closest vector algorithm such as Babai’s nearest-plane method with the target $(-u_1,\dots,-u_m, 0)$ .

Two practical details. First, the reduced basis always contains the harmless vector $(0,\dots,0,B,0)$ , which is $n$ times the $t$ -row minus multiples of the $n$ -rows. It is as short as $v$ and carries no information, so scan the reduced rows for one whose last coordinate is $\pm B$ . Second, every candidate is checked for free against the public key: $dG$ must equal it.

Worked example: a 16-bit toy curve

Take the curve $y^2 = x^3 + x + 7$ over $\mathbb{F}_{65357}$ . It has prime order $n = 65293$ , and we use the generator $G = (1, 3)$ . The private key is $d = 8806$ , giving the public key $Q = dG = (2507, 785)$ . A faulty signer draws every nonce below $B = 2^8$ , so the top 8 of 16 bits are always zero. Four signatures:

i	h	r	s	$t_i$	$u_i$	secret $k_i$
1	37303	14851	42579	24919	13276	217
2	52577	36535	44387	65082	30058	196
3	4135	46929	28026	50862	19274	66
4	7727	40682	8667	31540	15309	127

The attacker sees only the first three columns. The six-dimensional lattice has determinant $n^{3}B^2 \approx 1.8\times 10^{19}$ , so the Gaussian heuristic predicts vectors of length about 962. The target $v = (217, 196, 66, 127,\ 34.5,\ 256)$ has length about 416, less than half of that, and LLL finds it. With the basis scaled by $n$ to integers, the second row of the reduced basis is

(14168581,\ 12797428,\ 4309338,\ 8292211,\ 2254336,\ 16715008).

Dividing the first four entries by $n$ gives the nonces 217, 196, 66 and 127. The fifth entry is $dB = 2254336$ , so $d = 2254336/256 = 8806$ , and $8806\,G$ matches $Q$ . The first reduced row is the harmless $(0,0,0,0,-nB,0)$ . With only three signatures the same attack fails on some seeds, in line with the bound above: $3 \cdot 8 = 24$ bits is barely more than the 16 bits of the key plus the lattice overhead. The whole lattice step fits in a few lines of fpylll:

from fpylll import IntegerMatrix, LLL

n, B = 65293, 2**8          # group order, bound on every nonce
sigs = [(37303, 14851, 42579), (52577, 36535, 44387),
        (4135, 46929, 28026), (7727, 40682, 8667)]   # (h, r, s)

t = [r * pow(s, -1, n) % n for h, r, s in sigs]
u = [h * pow(s, -1, n) % n for h, r, s in sigs]
m = len(sigs)

# Basis rows, multiplied by n so every entry is an integer.
rows = [[n * n if j == i else 0 for j in range(m)] + [0, 0] for i in range(m)]
rows.append([n * ti for ti in t] + [B, 0])
rows.append([n * ui for ui in u] + [0, B * n])

A = IntegerMatrix.from_matrix(rows)
LLL.reduction(A)
for row in A:
    if abs(row[-1]) == B * n:                  # the embedding coordinate
        sign = 1 if row[-1] > 0 else -1
        print("candidate d =", sign * row[-2] // B % n)
# Prints 8806 and 52739. Keep the one where d*G equals the public key.

On a real 256-bit curve the same code works unchanged in principle. What changes is the number of signatures and the strength of the reduction you need, which is where the research below comes in.

Real-world attacks

PlayStation 3 (2010). A constant nonce, the zero-bit-of-entropy extreme. No lattice needed.
TPM-Fail (2019). Moghimi, Sunar, Eisenbarth and Heninger found that TPM 2.0 devices leaked the nonce’s bit length through signing time. An Intel firmware TPM gave up a 256-bit ECDSA key after about 1,300 observations, an STMicroelectronics hardware TPM after fewer than 40,000. They also recovered a VPN server’s key remotely by timing about 45,000 handshakes.
Minerva (2019–2020). Jancar and co-authors found the same bit-length timing leak in a certified Atmel smartcard and in libgcrypt, wolfSSL, MatrixSSL, SunEC/OpenJDK and Crypto++. Recovering a P-256 key took about 1,200 signatures from library data and 2,100 from the smartcard.
LadderLeak (2020). Aranha, Novaes, Takahashi, Tibouchi and Yarom exploited a Montgomery-ladder leak in OpenSSL that reveals the top nonce bit only with some probability, less than one bit per signature. That is below what lattices handle well, so they used Bleichenbacher’s Fourier-analysis approach to HNP instead, breaking P-192 and sect163r1.

On the lattice side, Albrecht and Heninger (Eurocrypt 2021) pushed the boundary further by adding a predicate, a cheap check that recognises the correct key, to enumeration and sieving. That solved HNP instances with fewer leaked bits and fewer signatures than were previously thought reachable with lattices.

Defenses

Deterministic nonces (RFC 6979). Derive $k$ from the private key and the message hash with HMAC-DRBG. This removes bad randomness and nonce reuse as failure modes.
Hedged nonces. Mix fresh randomness into the deterministic derivation. This keeps the RNG safety net and adds protection against fault attacks that target purely deterministic signing.
Constant-time scalar multiplication. Deterministic nonces do not stop timing leaks. The scalar multiplication must take the same time and memory-access pattern for every $k$ , including ones with leading zero bits. Fixing the bit length, for example by adding $n$ or $2n$ before the ladder, closes the Minerva and TPM-Fail leak.
Unbiased sampling. Reduce a random value modulo $n$ only after drawing at least 64 extra bits, or use rejection sampling. A small modular bias is also a hidden-number leak.
Plan to migrate. ML-DSA removes the ECDSA nonce structure, but its own implementations have side channels of their own, so constant-time engineering still matters.

Common mistakes

Thinking a small leak is harmless. By the estimate above, four leaked bits per nonce across roughly 150 signatures is enough to recover a 256-bit key.
Forgetting the scaling. Without the $B/n$ weight, the $d$ coordinate dominates and the target is no longer the shortest vector.
Stopping at the first reduced row. The shortest reduced vector is often the uninformative $(0,\dots,0,B,0)$ . Test each row against the public key.
Treating RFC 6979 as a side-channel fix. It fixes randomness, not timing. A deterministic nonce that leaks its bit length is still attackable.

6.4 Lattice attacks on ECDSA: the hidden number problem