DSA/ECDSA Biased-Nonce Lattice Attack — turning partial nonce leaks into a private-key recovery

When (EC)DSA nonces are only *partially* known or *partially* small — a few shared/fixed bits, or k bounded well below the group order rather than reused outright — each signature contributes one Hidden Number Problem sample in the private key, and enough samples let lattice reduction recover the key without ever seeing k directly.

The signal that gives it away

This is the middle ground between two other DSA/ECDSA breaks, and telling them apart is the whole triage: - Not ECDSA/DSA Nonce Reuse — identical r collapses the private key to closed-form algebra — you don't see two signatures sharing the exact same r (which would mean the exact same k). - Not Repeated / Linearly-Related Nonce Recovery — when nonces aren't reused, but ARE related by a known formula — you don't have an *exact*, attacker-known linear relation between nonces (a counter, a fixed stride from a broken LCG). - This attack — you have neither, but something makes each k individually *biased*: a handful of fixed/shared high or low bits, an RNG that only ever emits k < 2^B for B well under the group order's bit length, or a side-channel oracle (timing, cache, power, even something as coarse as "how many leading zero nibbles did this signature's ephemeral computation take") that leaks a few bits of k per signature without ever giving you the whole thing.

Concrete tells worth pattern-matching on: a challenge that hands you dozens to hundreds of (r, s, h) triples (a batch of signatures over different messages, same key) instead of just two; a nonce generator visibly capped below the modulus (k = random.getrandbits(160) against a 256-bit n, or similar); a comment/oracle that returns *some* information correlated with k's size or leading bits rather than k itself; or a curve/group where the private key is otherwise unreachable by every simpler DSA attack you've already ruled out. If you're staring at many signatures and none of the cheaper checks (matching r, an obviously fixed nonce-generation seed) pan out, this is the next thing to try, not a coin flip.

How to exploit it

1. Reduce every signature to a linear relation in the one unknown, `d`. Start from the signing equation s*k = h + d*r (mod n) (curve/group order n, hash h, signature (r,s)). Solve for k: k_i = s_i^{-1} h_i + s_i^{-1} r_i * d (mod n) = t_i * d + a_i (mod n) where t_i = s_i^{-1} r_i and a_i = s_i^{-1} h_i are both fully computable from the public signature — the only unknown left is d, and k_i is small (or has known bits) by the challenge's setup. This is exactly the derivation Hidden Number Problem — recovering a secret from many small-bounded-error samples leaves as "the ECDSA/DSA instantiation" — this is that instantiation, worked through. 2. Build the HNP lattice. For m signatures, build an (m+2) x (m+2) basis: a diagonal block of n (one row per sample, encoding that each relation only holds mod n), one extra row carrying all the t_i, one extra row carrying all the a_i, and scale the last two rows by K = 2^B (where 2^B bounds k_i) so that a genuinely small k_i — and hence the vector encoding d — becomes the *shortest* vector in the lattice, not just *a* short one: ``python from sage.all import * def hnp_lattice(t, a, n, B): m = len(t); K = 2**B M = Matrix(QQ, m+2, m+2) for i in range(m): M[i, i] = n for i in range(m): M[m, i] = t[i]; M[m+1, i] = a[i] M[m, m] = K / n M[m+1, m+1] = K L = M.LLL() for row in L: d = (round(row[m] * n / K)) % n # candidate; verify against the public key yield d `` 3. **Reduce with LLL Reduction — the polynomial-time workhorse behind almost every lattice attack and scan the reduced rows for a coordinate that decodes to a plausible `d`. Verify every candidate** by reconstructing the public key (Q = d*G for ECDSA, y = g^d mod p for DSA) or by re-signing a known message — LLL can and does return short-but-wrong vectors, and this is not a rare edge case worth skipping. 4. Scale the sample count to the bias, not the other way around. Field-tested rule of thumb: a lattice attack needs roughly n_bits / leaked_bits signatures to have a realistic shot — a 256-bit curve with only 2 known/biased bits per signature wants on the order of 128 samples; with 100+ signatures available, even a 1-2 bit bias per signature is routinely enough. If a challenge hands you noticeably fewer signatures than that ratio suggests, either the bias is bigger than it looks (re-check the nonce generator) or this isn't the right attack yet — don't burn hours tuning lattice dimensions before checking the sample-count math. 5. If plain LLL doesn't surface the vector, don't immediately assume the bias is too small — try Babai's nearest-plane algorithm on the LLL-reduced basis (the CVP-embedding most public implementations actually use under the hood, e.g. [bitlogik/lattice-attack](https://github.com/bitlogik/lattice-attack)), or bump to BKZ with a larger block size before concluding the sample count is insufficient.

What does NOT work

- Treating this as nonce reuse with extra steps. If you can't find two signatures with an identical r, don't try to force a two-signature closed-form solve (ECDSA/DSA Nonce Reuse — identical r collapses the private key to closed-form algebra's trick) — a *bias* across many nonces needs the full lattice machinery, not algebra on a pair. - Building the lattice without the `K` scaling. An unweighted lattice has no geometric reason to prefer the vector encoding the real, small k_is over any other short vector — this is the single most common way to burn an afternoon on a lattice that "should" work and doesn't. The scaling factor is what makes the planted solution actually the shortest vector, not decoration. - Getting the leak direction backwards. A known-high-bits (MSB) leak and a known-low-bits (LSB) leak change which values are "small" and therefore which rows carry the modulus weight versus the bound weight — silently swapping one construction for the other produces a lattice with no meaningful short vector, and the failure looks identical to "not enough bias," wasting time on the wrong fix. - Assuming a handful of signatures is always enough. Below the roughly n_bits / leaked_bits sample threshold, or below the theoretical minimum leak (on the order of sqrt(log n) + log log n bits per sample, from the original Boneh–Venkatesan bound), there is genuinely no short-enough planted vector for LLL to find — no amount of reduction-parameter tuning fixes a lattice that doesn't contain the answer. Collect more signatures or find a bigger per-signature leak instead. - Skipping verification of the LLL output. A candidate d with the right bit length is not proof; always reconstruct the public key before trusting it, and expect to filter out one or more spurious short rows. - Reaching for this when the nonce relation is exact rather than bounded. If the "bias" is actually a known, exact formula (nonces from a broken counter, a public LCG with known parameters), that's a direct linear-algebra solve — see Repeated / Linearly-Related Nonce Recovery — when nonces aren't reused, but ARE related by a known formula — and running it through an HNP lattice is solving a harder problem than the one you actually have.

Related

Hidden Number Problem — recovering a secret from many small-bounded-error samples Lattice Fundamentals — encoding a bounded unknown as a short vector LLL Reduction — the polynomial-time workhorse behind almost every lattice attack ECDSA Fundamentals — the s*k = h + d*r identity that routes every nonce attack DSA Fundamentals — the linear signing equation every DSA attack exploits ECDSA/DSA Nonce Reuse — identical r collapses the private key to closed-form algebra Repeated / Linearly-Related Nonce Recovery — when nonces aren't reused, but ARE related by a known formula Deterministic Nonce (RFC 6979) Failures — when 'no more RNG risk' still leaks the key