Hidden Number Problem — recovering a secret from many small-bounded-error samples

The Hidden Number Problem (HNP) recovers a secret alpha mod p from many samples of the form t_i * alpha - u_i = e_i (mod p), where each e_i is *small* (bounded by some 2^l) — the general lattice formulation of "I leaked a few most- or least-significant bits of something per sample." Introduced by Boneh and Venkatesan to study the bit-security of Diffie-Hellman, it is best known in CTF as the machinery behind biased-nonce ECDSA/DSA breaks.

The signal that gives it away

You have many (dozens to hundreds) instances of a linear relation in one unknown secret, each contaminated by a small, bounded error you can bound in bits — not an exact relation (that would just be a linear system), and not a fully unknown error (that would be unsolvable). Concretely: - Signatures where a few bits of each per-signature nonce k leak (MSB via a biased RNG, LSB via a hardware quirk, or a side-channel oracle) — this is DSA/ECDSA Biased-Nonce Lattice Attack — turning partial nonce leaks into a private-key recovery, the flagship instantiation. - A Diffie-Hellman-style shared secret where you only learn its top bits across many exchanges. - Any oracle that gives you t_i (attacker-known/chosen) and a value that's "close to" t_i * alpha but off by something small and bounded.

Rule of thumb carried over from field use: 2-4 known/biased bits over ~100 signatures usually suffices; more precisely, the bias needed scales roughly like n_bits / leaked_bits in the number of required samples — the fewer bits you get per sample, the more samples you need to compensate. This matches the theoretical bound of roughly sqrt(log p) + log log p bits of leakage from the original Boneh-Venkatesan analysis. In practice, real breaks (e.g. the Minerva/TPM-Fail class of ECDSA nonce leaks) show that even sub-single-bit average bias, if consistent across enough signatures, is exploitable — don't dismiss a "tiny" leak as noise before running the numbers.

How to exploit it

1. Reduce every sample to the canonical HNP shape. Eliminate whatever "known" values you have (message hash, signature components) so each sample becomes t_i * alpha - u_i = e_i (mod p) with alpha the one thing you don't know and e_i bounded by 2^l. For ECDSA/DSA this means solving the signing equation s_i k_i = m_i + r_i d (mod n) for k_i in terms of d, giving k_i ≈ A_i d + B_i (mod n) — see DSA/ECDSA Biased-Nonce Lattice Attack — turning partial nonce leaks into a private-key recovery for the full derivation. 2. Build the lattice. Standard construction (see Lattice Fundamentals — encoding a bounded unknown as a short vector): a diagonal block of the modulus p (one row per sample, so the lattice "knows" every relation is only defined mod p), one row carrying the t_i (or A_i) coefficients, one row carrying the u_i (or B_i) offsets, with a scaling factor K = 2^l on the last two rows so the bound on e_i dominates the basis geometry — get this weighting wrong and LLL will not converge on the planted vector. ``python from sage.all import Matrix, QQ rows = [[n if i==j else 0 for j in range(m)] + [0,0] for i in range(m)] rows.append(A + [B/n, 0]) rows.append(U + [0, B]) key = Matrix(QQ, rows).LLL() # scan rows for alpha `` 3. **Reduce with LLL Reduction — the polynomial-time workhorse behind almost every lattice attack and scan the resulting short rows for the coordinate that decodes to `alpha` (in the ECDSA case, the private key `d`). This is one of the few places where lattice reduction alone (no exhaustive SVP oracle) reliably breaks real cryptography — it is often cited as the flagship positive application of LLL in cryptanalysis. 4. Verify before trusting.** Reconstruct the public key from the candidate alpha (re-sign a known message, or re-derive Q = alpha*G) — a wrong-but-short vector is a common false positive, not a rare edge case. 5. If plain LLL doesn't surface the vector at higher sample counts/dimensions, escalate to Babai's nearest-plane algorithm on the LLL-reduced basis (the CVP-embedding variant most public references actually use) or BKZ with a larger block size — see LLL Reduction — the polynomial-time workhorse behind almost every lattice attack for the dimension ceiling where LLL alone starts missing the true shortest vector.

Build the individual relations using modular-arithmetic over whatever group order applies (curve order for ECDSA, q for DSA, the DH modulus for the original Boneh-Venkatesan setting).

What does NOT work

- Skipping the weighting/scaling step. An unweighted lattice (all entries the same order of magnitude) has no reason to make the planted small-error vector the *shortest* one — LLL will happily return a short vector that has nothing to do with your secret. The K = 2^l scaling on the error rows is not cosmetic; it's what makes the geometry favor the real solution. - Confusing MSB-leak and LSB-leak formulations. They are not interchangeable — which end of k (or alpha) is "small" changes which rows carry the modulus weight versus the value weight. Copy-pasting an MSB-oracle lattice construction onto an LSB leak (or vice versa) silently produces a lattice with no meaningful short vector. - Trusting the first short row without verification. A candidate that "looks" like a plausible secret (right bit length, right range) can still be wrong; always re-derive the public value and check it matches before spending time downstream. - Assuming any nonzero bias is automatically enough. Below roughly the sqrt(log p) + log log p bit threshold, or with too few samples relative to leaked bits per sample, the embedding genuinely has no short-enough planted vector for LLL/Babai to find — collect more samples or find a bigger leak rather than debugging the lattice code. - **Reaching for HNP when the relation between samples is *exactly* known rather than small-and-bounded.** If nonces are related by a known linear formula (a counter, a fixed offset) rather than merely "close" to a linear relation, that's a direct linear-algebra solve, not a lattice problem — see Repeated / Linearly-Related Nonce Recovery — when nonces aren't reused, but ARE related by a known formula instead; forcing it through an HNP lattice wastes effort a 2x2 system would settle instantly.

Related

Lattice Fundamentals — encoding a bounded unknown as a short vector LLL Reduction — the polynomial-time workhorse behind almost every lattice attack DSA/ECDSA Biased-Nonce Lattice Attack — turning partial nonce leaks into a private-key recovery Repeated / Linearly-Related Nonce Recovery — when nonces aren't reused, but ARE related by a known formula ECDSA Fundamentals — the s*k = h + d*r identity that routes every nonce attack Elliptic Curve Discrete Logarithm Problem — the curve order's factorization picks your attack