home / ctf / nns-ctf

Downhill

Hidden-parallelepiped attack on a 2003 signature scheme — recover `f` with covariance plus FFT-augmented 4th-moment gradient descent

2026.09.30 NNS CTF 2026 155 pts Crypto
FLAG NNS{WH47_r1s35_mUs7_F4ll_wH47_4sC3ND5_MU57_d35C3nd}

Flag: NNS{WH47_r1s35_mUs7_F4ll_wH47_4sC3ND5_MU57_d35C3nd}

Challenge

chall.sage implements NTRUSign without perturbation (the original, cryptanalytically-broken 2003 signature scheme):

N, q, df, dg = 251, 128, 73, 71

f, g = random 0/1 polynomials of weight df, dg  (secret)
F, G = NTRU-lattice companion polys s.t. f*G - g*F = q  (secret)
h    = public key,  f*h ≡ g (mod q)

def sign(msg):
    m = hash(msg) mod 127        # public, we choose msg
    a = round(-m*F/q)            # secret rounding
    b = round( m*f/q)            # secret rounding
    return (a*f + b*F) mod (x^N - 1)

The server prints pk = h, ct = AES-ECB(sha256(f), flag), then answers 500 signing queries on messages of our choice. No perturbation is applied to (a,b), which is exactly the setting broken by Nguyen & Regev, “Learning a Parallelepiped: Cryptanalysis of GGH and NTRUSign” (Eurocrypt 2006) — the title “Downhill” is a hint at the gradient-descent (minimize 4th moment ⇒ go “downhill”) step of that attack.

Naively LLL/BKZ-reducing the NTRU lattice from h alone (dimension 502, N=251) goes nowhere — block sizes up to 55 left the shortest vectors exactly at the trivial q·eᵢ norm (128.0), confirming the intended path uses the signature oracle, not a bare lattice attack on the public key.

The algebra: turning signatures into a hidden-parallelepiped sample

Write a = -mF/q - r_a, b = mf/q - r_b where r_a, r_b are the rounding residuals (each coordinate ≈ Uniform[-½, ½]). Substituting into s = a·f + b·F and using that the ring R = Z[x]/(xᴺ-1) is commutative (f·F = F·f), the m-dependent term cancels exactly:

s = -(r_a·f + r_b·F)                       (exact identity)

Doing the same for t := a·g + b·G and using the NTRU determinant identity f·G - g·F = q:

t = m - (r_a·g + r_b·G)                    (exact identity)

We don’t see t directly, but t ≡ s·h (mod q) (standard NTRU relation, since f·h≡g and F·h≡G mod q), and |t - m| turns out to be small enough (empirically, like s) that centering (s·h - m) mod q into (-q/2, q/2] recovers t - m exactly. So for every signature we get:

v := (s, t - m) = -( r_a·(f,g) + r_b·(F,G) )

This is precisely a sample from the hidden parallelepiped generated by the 2N vectors { xᵏ·(f,g) } ∪ { xᵏ·(F,G) } (all cyclic rotations), with r_a, r_b ~ Uniform[-½,½]ᴺ — exactly the object Nguyen–Regev attack.

Recovering f: covariance + FFT-augmented 4th-moment gradient descent

  1. Collect 500 signatures on distinct chosen messages over the raw TCP/TLS socket; reconstruct v_i = (s_i, t_i - m_i) for each (502-dim vectors).

  2. Covariance estimation via circulant symmetrization. The population covariance Σ = Cov(v) is exactly invariant under simultaneously rotating both halves of v by the same shift k (since the generator set is rotation-closed). Average the raw empirical covariance Σ_raw = VᵀV/K over all 251 rotations: Σ_sym = (1/N) Σ_k Π^k Σ_raw Π^{-k}. This turns 500 samples into an effectively ~500×251 ≈ 125,000-sample-strong estimate of the (exactly block-circulant) true covariance, giving a clean eigenvalue spectrum split into two groups of 251 — small eigenvalues from the tiny 0/1 (f,g) family, large ones from the NTRU-companion (F,G) family.

  3. Whiten: L = Σ_sym^{-1/2} (via eigendecomposition).

  4. 4th-moment gradient descent (“downhill”) on the whitened unit sphere: for uniform sources, the standardized 4th moment is minimized (value 9/5 = 1.8) exactly along the true generator axes, vs. ≈3 for a generic direction (CLT-Gaussian). Naive gradient descent using only the raw 500 samples is sample-starved (500 points for 502 whitened dimensions — trivially finds spurious directions orthogonal to all samples, m4 → 0). Fix: exploit the same rotational symmetry to augment the 4th-moment estimate itself — for a candidate direction y (unwhitened), compute the full array of rotated projections PROJ[i,k] = y · Rᵏ(v_i) for all 500 × 251 (sample, shift) pairs at once via FFT circular correlation, and its gradient via FFT circular convolution (get this backwards — used a correlation instead of a convolution in the gradient formula — and every run converges to plausible-looking but wrong ~2.5–3.0 minima; verified/found via finite-difference check against a tiny synthetic instance with a known key). With the corrected gradient, random-restart descent reliably finds true axes at m4 ≈ 1.8.

  5. Extract candidate: unwhiten the converged direction, cand = √12 · Σ_sym^{1/2} · u* (the √12 matches Var(Uniform[-½,½]ᴍ)⁻¹ᐟ² applied to a true generator’s whitened image, which has norm exactly √12 in the idealized case). Round to nearest integers; if the first 251 coordinates are all 0/1 with weight in the expected 30–120 range, try all 251 cyclic rotations as f candidates.

  6. Decrypt: AES-ECB(sha256(f), ct), unpad, check it’s printable ASCII.

Out of ~17 random restarts on the real 500-signature transcript, one converged to m4 = 1.80562, sum(f-candidate) = 73 (exactly df), and decrypting with it gave the flag directly.

Key pitfalls hit along the way

  • sage’s .list() trims trailing zero coefficients — some harvested signatures/pk came back shorter than N=251; must zero-pad.
  • Order of operations for recovering t - m mod q matters: you must compute (s·h - m) mod q then center to (-q/2, q/2] — centering s·h to recover “t” first and then subtracting m silently picks the wrong residue class for many coordinates (since m ∈ [0,127] is not itself small/centered) and corrupts everything downstream.
  • 500 raw samples is exactly sample-starved for a 502-dim whitened 4th-moment search (trivial m4→0 null-space solutions). Reuse the circulant symmetry (as done for the covariance) to effectively multiply the sample count by N=251 for the kurtosis objective too.
  • Correlation vs. convolution sign/conjugate mixup in the FFT gradient is an easy, silent bug: the objective value (m4) comes out numerically plausible either way (it’s a fixed-permutation-invariant sum), but the gradient direction is simply wrong, so descent reliably converges to bogus attractors. Caught by validating against a tiny synthetic instance with a known secret key and a naive double-loop reference implementation — always do this before trusting an FFT gradient.

Files

  • harvest.py — collects pk, ct, and 500 signatures from the live instance.
  • step10.py — final, corrected solver (covariance symmetrization + FFT-augmented gradient descent + candidate rotation/decrypt check).
  • debug_fft2.py — the finite-difference sanity check that caught the correlation/convolution bug.
  • synth_test2.py — small synthetic (N=30) end-to-end validation of the whole pipeline against a known key, at the same K=500 sample budget as the real challenge.