MSS_ADVANCE Revenge picoCTF 2026 Solution

Description

1. Step 1Understand the polynomial and why the system is underdetermined

   Observation

   chall.py builds a degree-29 polynomial, 30 coefficients, and publishes only 20 shares. The linear system is underdetermined, so Gaussian elimination cannot finish it. Something else about the solution has to be exploited.

   chall.py builds a degree-29 polynomial f(x) = c_0*x^29 + c_1*x^28 + ... + c_29 over GF(p), where p is a 1024-bit prime. The leading coefficient c_0 holds MASTER_KEY. Each coefficient c_{i+1} = SHA-256(c_i), so all 30 coefficients are ~256 bits. Only 20 shares (x_i, f(x_i) mod p) are given. That is 30 unknowns but only 20 linear equations mod p, so ordinary linear algebra cannot solve it. The key insight is that all 30 coefficients are tiny (~256-bit) compared to p (1024-bit), making the solution vector unusually short in the lattice sense.

   bash

   grep -nE 'def |%|pow|coeff|MASTER|share|range' chall.py

   Copied!

   bash

   # Confirm: 30 coefficients, 20 evaluations, 'return total % p'

   Copied!

   What didn't work first

   Tried: Solve the 20x30 linear system with numpy.linalg.lstsq or sage's solve_right over GF(p)

   With 30 unknowns and 20 equations, solve_right returns one particular solution that satisfies them all while carrying 1024-bit coefficients rather than the true 256-bit ones. The solver has no way to express the size bound, so its answer is wrong. Only lattice reduction uses the short-vector structure.

   Tried: Use the CRT shortcut from the non-Revenge MSS sibling: compute f(x_i) mod x_i for each share to recover c_29 directly

   That trick needs evaluation over the integers with no outer modulus. Here each value is reduced mod p before it is printed, so taking it mod x mixes p into the residue and CRT over those residues recovers nothing. The revenge version adds that reduction specifically to close the shortcut.

   Learn more

   Why ordinary Gaussian elimination fails. The shares give us 20 equations of the form sum(c_j * x_i^j) = y_i (mod p) for i = 0..19. That is a 20x30 linear system, which is underdetermined (infinitely many solutions over GF(p)). The solution only becomes unique when you exploit the additional structure that every coefficient is bounded to ~256 bits, which is the lattice condition that LLL can exploit.

2. Step 2Build the lattice and run LLL

   Observation

   Every coefficient comes from a SHA-256 hash, so each is about 256 bits, while the modulus is 1024. The true solution vector is unusually short relative to the lattice, which is exactly what LLL finds.

   Construct a (m+n+1) x (m+n+1) integer matrix where m=20 (equations) and n=30 (unknowns). Set W = 2^512 as a weight. The left m x m block has p*W on the diagonal (absorbing the mod-p arithmetic). Each coefficient row j encodes the polynomial powers x_i^(n-1-j) mod p, scaled by W, and places 1 on the diagonal in the coefficient block. The last row encodes the negative of the evaluation values times W. Run SageMath's LLL() on this matrix. The shortest nontrivial rows will be the actual coefficient vector, because all 30 true coefficients are ~256-bit while random lattice vectors are much longer.

   python

   python3 - <<'PY'
   # Run in SageMath (sage -python or a .sage file)
   from sage.all import Matrix, ZZ
   
   m = 20   # number of shares
   n = 30   # number of coefficients (degree 29 polynomial)
   W = 2**512
   
   # pairs = [(x_i, y_i), ...] loaded from output.txt
   # p = the 1024-bit prime from chall.py
   
   L = Matrix(ZZ, m + n + 1, m + n + 1)
   
   # Left block: absorb the modular congruences
   for i in range(m):
       L[i, i] = p * W
   
   # Middle block: polynomial evaluation structure
   for j in range(n):
       for i in range(m):
           xi, _ = pairs[i]
           L[m + j, i] = pow(xi, n - 1 - j, p) * W
       L[m + j, m + j] = 1
   
   # Bottom row: the known evaluations (negated)
   for i in range(m):
       xi, yi = pairs[i]
       L[m + n, i] = -yi * W
   L[m + n, m + n] = 1
   
   lll_res = L.LLL()
   print("LLL done, searching for candidate coefficients...")
   PY

   Copied!

   Expected output

   LLL done, searching for candidate coefficients...

   What didn't work first

   Tried: Run LLL on a square n x n matrix using only the 20 evaluation rows without the p-diagonal block or the negated-evaluation bottom row

   Leave out the diagonal p times W block and the matrix no longer encodes the congruences, so LLL reduces unconstrained integer rows and returns short vectors unrelated to the coefficients. Every candidate fails the bit-length test. That diagonal is what makes the lattice respect the modular arithmetic.

   Tried: Choose W = 1 (no weight scaling) to keep the matrix entries small

   Without the weight, the evaluation entries run to about 2^1024 while the diagonal entries are size 1, a gap that leaves LLL's cost function blind to the coefficient rows: it reduces toward the tiny diagonal and ignores the constraints. A weight near 2^512 balances the two scales so both are minimized together.

   Learn more

   Why LLL works here. The lattice embeds both the polynomial constraint (f(x_i) = y_i mod p) and the size bound (coefficients are ~256-bit). The real coefficient vector, embedded in the lattice, has norm roughly 30 * 2^256. A generic lattice vector has norm around det(L)^(1/dim) = (p*W)^(20/51), roughly 2^602 here, which is enormously larger. LLL reliably finds vectors near the shortest, revealing the true coefficient vector.

   Difference from MSS (the non-Revenge sibling). The simpler MSS challenge evaluates f(x) over the integers with no modulus. That version leaks f(x_i) mod x_i = c_29 mod x_i (only the constant term survives, since every other term carries a factor of x_i), so CRT directly recovers that coefficient. The Revenge variant adds mod p, closing that shortcut and requiring lattice methods.

3. Step 3Extract MASTER_KEY and decrypt the flag

   Observation

   The leading coefficient c_0 is the master key, a 32-byte SHA-256 digest. So any LLL row entry between 250 and 260 bits is a candidate: convert it to bytes and try it as the AES-CBC key.

   Scan each row of the LLL-reduced matrix. Any entry between 250 and 260 bits is a candidate for MASTER_KEY (which is sha256(flag) as a 256-bit integer). Convert the candidate directly to 32 bytes with big-endian encoding and use it as the AES-CBC key. The IV is 16 zero bytes (hardcoded in chall.py). Decrypt and unpad, then look for 'picoCTF' to confirm the right candidate.

   python

   python3 - <<'PY'
   from Crypto.Cipher import AES
   from Crypto.Util.Padding import unpad
   
   enc_flag = bytes.fromhex("<ciphertext from output.txt>")
   iv = b"\x00" * 16
   
   for row in lll_res:
       for val in row:
           cand = abs(int(val))
           if 250 <= cand.bit_length() <= 260:
               try:
                   key = cand.to_bytes(32, "big")   # MASTER_KEY directly, no extra hash
                   pt = unpad(AES.new(key, AES.MODE_CBC, iv).decrypt(enc_flag), 16)
                   if b"picoCTF" in pt:
                       print("FLAG:", pt.decode())
                       break
               except Exception:
                   pass
   PY

   Copied!

   The AES key is MASTER_KEY as raw bytes, not a hash of a string. Because chall.py sets MASTER_KEY = sha256(flag).digest() and then coeffs[0] = bytes_to_long(MASTER_KEY), LLL recovers that integer. Converting it back with to_bytes(32, 'big') reconstructs the 32-byte key exactly.

   What didn't work first

   Tried: Hash the recovered integer candidate with SHA-256 before using it as the AES key, assuming the script stored sha256(MASTER_KEY) as the coefficient

   The master key is already a SHA-256 digest, and LLL recovers that exact integer, so converting it to 32 bytes gives the AES key directly. Hash it again and you get a different key, so decryption returns garbage or a padding error.

   Tried: Use the CBC IV from the encrypted output instead of zero bytes, guessing that the IV was prepended to the ciphertext

   The script hardcodes an all-zero IV and does not prepend it. Treat the first 16 bytes of ciphertext as an IV and every block shifts: the suffix decrypts correctly while the first 16 bytes come out garbled, hiding the prefix and making a correct key look wrong.

   Learn more

   The lesson. Shamir's scheme is secure only when the number of shares equals the number of coefficients. Giving fewer shares than unknowns looks safe over a field, but if the coefficient vector is far shorter than the field size, LLL can still recover it. This is the same family of attacks used against NTRU and certain lattice-based signature schemes. See the number-theory CTF patterns for adjacent lattice and modular-arithmetic attacks.

Flag

The polynomial is evaluated over GF(p) (1024-bit prime) with 30 coefficients and only 20 shares, making it underdetermined. All coefficients are ~256-bit, so the real coefficient vector is short in the lattice sense. Build a (m+n+1) x (m+n+1) matrix, run LLL, and search recovered rows for a 250-260 bit value. That is MASTER_KEY. Convert it directly to 32 bytes (big-endian) as the AES-CBC key (IV = zero bytes) to decrypt the flag. This is an LLL lattice attack, not CRT.