{"id":1440,"date":"2026-09-06T16:52:17","date_gmt":"2026-09-06T16:52:17","guid":{"rendered":"https:\/\/www.securesteps.tn\/?p=1440"},"modified":"2026-09-06T16:52:17","modified_gmt":"2026-09-06T16:52:17","slug":"light-weight-encryption-nns-ctf-walkthrough","status":"publish","type":"post","link":"https:\/\/www.securesteps.tn\/ar\/light-weight-encryption-nns-ctf-walkthrough\/","title":{"rendered":"Light-Weight Encryption \u2014 Lattice Attack | NNS CTF"},"content":{"rendered":"

Light-Weight Encryption \u2014 Lattice Attack<\/h1>\n

Platform:<\/strong> NNS CTF 2026
Category:<\/strong> Cryptography
Challenge author:<\/strong> Zukane<\/p>\n

1. Challenge construction<\/h2>\n

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

q, t = 2**768, 2**512\nn, m, w, b = 16, 112, 130, 16\nA = random_matrix(ZZ, m, n, x=0, y=b)\ne = random_vector(ZZ, m, 0, r)\nB = A*s + k*e<\/code><\/pre>\n
The scalar k<\/code> 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.<\/p>\n
2. Why the parameters are weak<\/h2>\n
The intended hardness depends on hiding the error. Here, three properties work together against the scheme:<\/p>\n
    \n
  • the columns of A<\/code> are tiny and have only 16 dimensions;<\/li>\n
  • there are 112 equations, giving substantial redundancy;<\/li>\n
  • the error coordinates are only about 32 bits while the modulus is 768 bits.<\/li>\n<\/ul>\n
    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<\/code>.<\/p>\n
    3. Recovering the error with LLL<\/h2>\n
    Build a 112-dimensional modular lattice from the columns of [A | -B]<\/code>. The lattice contains the short vectors corresponding to the small columns of A<\/code>, together with a vector related to e<\/code> up to an integer combination of those columns. LLL reduces the basis and separates these unusually short vectors from the much larger generic combinations.<\/p>\n
    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.<\/p>\n
    4. Solving for the adjusted secret<\/h2>\n
    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<\/code> modulo 2^768<\/code>. The additional equations are deliberately retained as checks rather than being used only during fitting.<\/p>\n
    The decisive verification is:<\/p>\n
    B[i] == A[i] * s + k * e[i] (mod 2^768)<\/code><\/pre>\n
    for every one of the 112 rows. The recovered result satisfied verified_public_equations=112\/112<\/code>, so it was not merely a plaintext-shaped lattice artifact.<\/p>\n
    5. Removing the ciphertext error<\/h2>\n
    The ciphertext has the form:<\/p>\n
    ct[0] = sum(A[i] for i in I)\nct[1] = plaintext - sum(B[i] for i in I)<\/code><\/pre>\n
    Combining it with the recovered secret gives:<\/p>\n
    Y = ct[1] + ct[0] * s\n  = plaintext - k*E (mod 2^768)<\/code><\/pre>\n
    where E<\/code> 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<\/code>.<\/p>\n
    6. Reproduction<\/h2>\n
    cd \/home\/z13db\/CTF\/crypto\/light-weight-encryption\/crypto_light-weight-encryption\npython3 solve.py<\/code><\/pre>\n
    The solver artifacts are preserved alongside chall.sage<\/code>, including the lattice and CVP experiments. The final validation file records the aggregate error, plaintext, and all 112 equation checks.<\/p>\n
    7. Verified result<\/h2>\n
    NNS{lwe,compact,broken:https:\/\/eprint.iacr.org\/2017\/742.pdf}<\/code><\/pre>\n
    The recovered plaintext is 60 bytes, printable, has the expected wrapper, and satisfies the public equations and final ciphertext congruence.<\/p>\n
    8. Lessons<\/h2>\n
    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.<\/p>\n","protected":false},"excerpt":{"rendered":"
    Detailed NNS CTF cryptography walkthrough explaining the weak LWE construction, modular lattice, error recovery, CVP step, and equation-level verification.<\/p>","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_joinchat":[],"footnotes":""},"categories":[82],"tags":[],"class_list":["post-1440","post","type-post","status-publish","format-standard","hentry","category-cryptography"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t