Light-Weight Encryption

Challenge summary

chall.sage (Sage/Python):

q, t = 2**768, 2**512
n, m, w, b = 16, 112, 130, 16
R = Zmod(q)

def keygen():
    s = random_vector(R, n)          # 16 elements mod q
    r = getPrime(32)
    p = getPrime(520)
    sk = getPrime(128)
    A = random_matrix(ZZ, m, n, x=0, y=b)   # 112x16, entries in [0,16)
    e = random_vector(ZZ, m, 0, r)          # 112 entries in [0, 2^32)
    k = R(p)/sk
    B = A*s + k*e
    return (A, B)

def encrypt(pk, pt):
    A, B = pk
    I = [random index in range(m) for _ in range(w=130)]   # with repl.
    return sum(A[i] for i in I), pt - sum(B[i] for i in I)

The public key gives the FULL A matrix and B vector (112 rows), not just a compressed “sample” — this is what makes the attack possible. Ciphertext is (ct0, ct1) with ct0 = sum_{i in I} A[i] (exact integer vector) and ct1 = flag_int - sum_{i in I} B[i] mod q, I a random multiset of 130 indices out of 112.

First (dead-end) approach

The naive idea: if you could recover the exact multiset I (equivalently the vector n with n[i] = multiplicity of index i, n[i]>=0, sum(n)=130, A^T n = ct0), then flag = ct1 + sum(n[i]*B[i]) mod q directly — no need to know s, k, e, p, or sk. n lives in a 95-dimensional lattice coset (112 unknowns, only 17 linear constraints), so this looked like a textbook closest-vector-problem: find the lattice point closest to a particular solution, expecting it to coincide with n because a real “130 draws from 112 bins” multiset should look like the shortest vector in its coset.

This turned out to be a dead end, and expensively so (many CPU-hours were sunk into it before abandoning it): the kernel lattice’s Gaussian heuristic shortest vector has norm ~4.6 (its covolume is only ~10^27.8 over 95 dimensions), but the true n has norm ~sqrt(280-300) ~ 17 — about 14x longer than the lattice’s typical short vector. A CVP/branch-and-bound search at that radius has to explore something like 10^53 lattice points before it could ever stumble on the true n (and, separately, there are about 10^36 all-non-negative solutions in that neighborhood too, so “closest non-negative point” doesn’t even pin down n uniquely). No amount of cleverness in the enumerator fixes an information-theoretically hopeless search radius — the approach itself was wrong, not the code.

The actual break: you never need n at all

The real vulnerability is that B = A*s + k*e leaks k (and hence p, sk) directly, via any short vector c in the SAME 95-dimensional kernel lattice (the one satisfying A^T c = 0, sum(c) = 0 — already computed as a side effect of the dead-end approach above, so that work wasn’t totally wasted):

c . B = c.(A s) + k (c.e) = 0 + k*(c.e)     [since A^T c = 0 kills the s term]

So for a short kernel vector c (L1 norm ~60, from the existing LLL-reduced kernel basis), y = c.B mod q satisfies y = k*u (mod q) for a small u = c.e (bounded by ||c||_1 * 2^32, well under 2^39). Since k = p * sk^{-1} mod q:

sk * y = p * u (mod q),  with |sk| < 2^128, |p*u| < 2^560 << q=2^768

Treating (sk, quotient) as an unknown short vector and using ~12 independent short kernel vectors c_j (giving 12 equations sk*y_j - p*u_j = quotient_j * q), a 13-dimensional LLL directly recovers sk exactly (128 bits, matches getPrime(128)). From there, centered sk*y_j mod q gives values close to p*u_j; their GCD across several j recovers p exactly (520 bits), and then k = p * sk^{-1} mod q — verified consistent against all the independent relations.

Finally, n is still not needed: for ANY integer vector n' with A^T n' = ct0 (not necessarily non-negative or the “real” multiset — an arbitrary Babai-rounded solution works fine, negative entries and all):

ct1 + B.n' = ct0.s + k*(e.n') = ct0.s + k*(e.n) - k*(e.(n-n')) = flag - k*Delta

where Delta = e.(n - n') is small (bounded similarly to the u_j above, since n - n' is itself a lattice vector of modest norm). A tiny 2-dimensional CVP recovers Delta exactly, and

flag_int = (ct1 + B.n' + k*Delta) mod q

decodes to 60 clean printable-ASCII bytes.

Lesson

Giving out the entire public LWE matrix/vector pair (rather than a compressed/hashed commitment to it) hands an attacker unlimited freedom to build short vectors in the kernel of A^T, and any such vector cancels the “secret” s term outright — turning “recover the secret vector s” into “recover the scalar noise-scaling trapdoor k”, a much smaller and much more structured target. The flag itself names the root cause: compact/structured LWE-style schemes that publish a full noisy relation B = As + (scalar)*e rather than treating each sample independently are a well-studied broken pattern (see the referenced eprint).