lattice-nonce-reuse-audit

Answer

I diagnosed the problem, built a working implementation, and verified it. The complete, self-contained solution is saved at:

• ~/lattice-nonce-reuse-audit/SOLUTION.md (full markdown write-up with the complete audit.js and test.js listings)
• ~/lattice-nonce-reuse-audit/audit.js — detector + scheme + benchmark
• ~/lattice-nonce-reuse-audit/test.js — 7 deterministic contract tests
• ~/lattice-nonce-reuse-audit/run-1M.txt, test-output.txt — captured verification output

What was actually wrong

In an ML‑DSA/Dilithium‑style scheme (t = A·s + e2, z = y + c·s), a faulty RNG that reuses the ephemeral mask y gives z_i − z_j = (c_i−c_j)·s, so s falls out by one ring division — total key compromise. Correlated masks y_i − y_j = δ give s = (z_i−z_j−δ)(c_i−c_j)^{-1}. A naive “hash every nonce” auditor fails because (1) memory is unbounded, (2) birthday collisions in short tags are expected and harmless, (3) the commitment w is scrambled by A, so only exact reuse is metric‑detectable, (4) hash buckets are adversarially stuffable, and (5) a sketch hit is not proof.

The fix (two stages, exact decision)

Reconstruct the public commitment w' = A·z − c·t = A·y − c·e2. Salted, fixed‑memory bucketed hash tables + LSH + Count‑Min Sketch only nominate candidates (this is where collisions/birthday/truncation happen). The algebraic verifier is the only path that can alert:

verify(a, b) {
  const dc = vecSub(a.c, b.c);
  if (linf(dc) === 0) return null;                       // no equation
  let delta = (a.nonce && b.nonce) ? vecSub(a.nonce, b.nonce) : zeros(N);
  if (!(a.nonce && b.nonce) && linf(vecSub(a.w, b.w)) > LSH_W_THRESH) return null; // cheap filter
  const s_est = ringMul(vecSub(vecSub(a.z, b.z), delta), ringInv(dc));
  if (linf(s_est) > ETA) return null;                    // decisive: short secret
  const residual = vecSub(ringMul(a.A, s_est), a.t);
  if (linf(residual) > ETA2) return null;                // decisive: reproduces pubkey
  return { kind, ids, recovered_s: s_est, residual_linf: linf(residual), ... };
}

Because the verifier accepts only genuine reuse, sketch collisions cannot cause a false positive; salted SHA‑256 denies the adversary bucket targeting.

False‑positive guarantee

Under i.i.d. uniform nonces, s_est = s + (y_i−y_j−δ)(c_i−c_j)^{-1} is uniform over R_q ≅ Z_q^n, so per tested pair

p_fp = ((2η+1)/q)^n = (5/8380417)^8 ≈ 1.606e-50
P(any FP) ≤ m·S·p_fp ≤ 10^6·8·1.6e-50 ≈ 1.28e-43

Verification (actually run)

$ node test.js
lattice-nonce-reuse-audit :: contract tests
  PASS  exact nonce reuse is detected and key recovered
  PASS  independent nonces do not verify
  PASS  correlated nonce reuse is detected with delta correction
  PASS  identical challenge is rejected
  PASS  memory footprint is O(1) in stream length
  PASS  end-to-end stream isolates planted faults
  PASS  hash/tag collisions alone do not alert (algebraic guard)
All 7 contract tests passed.

$ SEED=42 N_BENIGN=1000000 node audit.js
transcripts processed  : 1000010        throughput : 81738 rec/s
detector memory        : 36.67 MB      (fixed; same for 10^3 or 10^9 records)
candidate pairs        : 5873718
algebraic solves       : 9  (prefilter survivors = 9)
benign alerts          : 0   (must be 0)
adversarial alerts     : 0   (must be 0)
alerts total           : 9
  exact nonce reuse    : 5
  correlated nonce     : 4
recovered secret Ok    : true
recovered s (first 4)  : 1,0,0,2   |  true s : 1,0,0,2
per-pair FP bound      : 1.606e-50 | union bound : 1.284e-43
RESULT: PASS

5.87M sketch nominations collapsed to 9 algebraic solves, all genuine faults, with exact key recovery and zero false positives. The honest limitation (stated in the write‑up) is that general small‑error LWE correlation is undetectable from ciphertexts alone, and no bounded‑memory detector can catch a single adversarially‑spaced reuse pair — the Count‑Min channel covers heavy hitters; otherwise bounded memory trades recall, which is made explicit rather than hidden.

The full markdown — title, root‑cause analysis, model, algorithm, FP proof, complete audit.js and test.js, commands, and verification output — is in ~/lattice-nonce-reuse-audit/SOLUTION.md.