Light-Weight Encryption — Lattice Attack | NNS CTF

Platform: NNS CTF 2026
Category: Cryptography
Challenge author: Zukane

1. Challenge construction

The Sage challenge generates a public key with n = 16 secret coordinates and m = 112 public equations. The modulus is q = 2^768. The matrix A is sampled with very small entries, while the error vector e contains values bounded by a 32-bit prime. The relevant construction is:

q, t = 2**768, 2**512
n, m, w, b = 16, 112, 130, 16
A = random_matrix(ZZ, m, n, x=0, y=b)
e = random_vector(ZZ, m, 0, r)
B = A*s + k*e

The scalar k is formed from a large prime ratio, but the public relation still exposes the same small-error structure. Encryption chooses 130 row indices and returns sums of the corresponding rows.

2. Why the parameters are weak

The intended hardness depends on hiding the error. Here, three properties work together against the scheme:

• the columns of A are tiny and have only 16 dimensions;
• there are 112 equations, giving substantial redundancy;
• the error coordinates are only about 32 bits while the modulus is 768 bits.

That imbalance makes a short-vector formulation possible. The public equation can be rearranged so that a lattice vector exposes the small error component modulo q.

3. Recovering the error with LLL

Build a 112-dimensional modular lattice from the columns of [A | -B]. The lattice contains the short vectors corresponding to the small columns of A, together with a vector related to e up to an integer combination of those columns. LLL reduces the basis and separates these unusually short vectors from the much larger generic combinations.

The attack does not blindly trust the first short vector. Candidate vectors are tested against the public equations and normalized into the expected small-error range. This converts lattice output into a candidate error vector suitable for the next algebraic step.

4. Solving for the adjusted secret

Once the error is known, the public equations become linear equations in the secret coordinates and the unknown scalar. Select 17 independent equations and solve for the adjusted secret and k modulo 2^768. The additional equations are deliberately retained as checks rather than being used only during fitting.

The decisive verification is:

B[i] == A[i] * s + k * e[i] (mod 2^768)

for every one of the 112 rows. The recovered result satisfied verified_public_equations=112/112, so it was not merely a plaintext-shaped lattice artifact.

5. Removing the ciphertext error

The ciphertext has the form:

ct[0] = sum(A[i] for i in I)
ct[1] = plaintext - sum(B[i] for i in I)

Combining it with the recovered secret gives:

Y = ct[1] + ct[0] * s
  = plaintext - k*E (mod 2^768)

where E is the sum of the selected error coordinates. The aggregate error is much smaller than the modulus. A two-dimensional scaled CVP lattice recovers the small integer correction. In the verified run, E = -4227640817.

6. Reproduction

cd light-weight-encryption/
python3 solve.py

The solver artifacts are preserved alongside chall.sage, including the lattice and CVP experiments. The final validation file records the aggregate error, plaintext, and all 112 equation checks.

7. Verified result

NNS{lwe,compact,broken:https://eprint.iacr.org/2017/742.pdf}

The recovered plaintext is 60 bytes, printable, has the expected wrapper, and satisfies the public equations and final ciphertext congruence.

8. Lessons

LWE-style notation does not make a construction secure automatically. Error size, dimension, modulus, sampling distribution, and the number of redundant equations must be evaluated together. A solver should always provide algebraic verification, not only a candidate flag.