MSS_ADVANCE Revenge picoCTF 2026 Solution

Description

1. Step 1

   Understand the polynomial and why the system is underdetermined

   Observation

   I noticed that chall.py generates a degree-29 polynomial with 30 coefficients but outputs only 20 shares, which meant the linear system over GF(p) was underdetermined and standard Gaussian elimination would fail, pointing toward an approach that could exploit additional structure in the solution.

   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!

   Expected output

   LLL done, searching for candidate coefficients...

   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 only 20 equations the system is underdetermined, so solve_right returns one particular solution mod p that satisfies the equations but has coefficients up to 1024 bits - not the true ~256-bit coefficients. The solver cannot enforce the size bound, so the answer is wrong and decryption fails. Only lattice reduction can exploit 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 works only when evaluation is over the integers with no outer modulus. Here, f(x_i) is reduced mod p before being output, so f(x_i) mod x_i gives (y_i mod x_i), which mixes p into the residue. CRT on those residues does not recover c_29. The Revenge challenge explicitly closes this shortcut by adding the mod p step.

   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 2

   Build the lattice and run LLL

   Observation

   I noticed that all 30 coefficients in chall.py are derived from SHA-256 hashes and thus bounded to approximately 256 bits while the modulus p is 1024 bits, which meant the true solution vector was unusually short relative to the lattice and suggested using LLL lattice reduction to recover it.

   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!

   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

   Omitting the diagonal p*W block means the matrix does not encode the mod-p congruences, so LLL operates on unconstrained integer rows and returns arbitrary short vectors that have nothing to do with the polynomial coefficients. Every candidate fails the 250-260 bit size test and no flag is recovered. The p*W diagonal is what forces the lattice to respect the modular arithmetic.

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

   Without the W factor, the polynomial evaluation entries (up to p^1 ~ 2^1024) and the size-1 diagonal entries differ by 1024 bits in magnitude, making the LLL cost function essentially blind to the coefficient rows. LLL will reduce toward the tiny diagonal rows and ignore the constraint structure entirely. W ~ 2^512 balances the two scales so the algorithm jointly minimizes both.

   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 random lattice vector has norm roughly p * W^(1/2) 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_0 mod x_i, so CRT directly recovers the secret. The Revenge variant adds mod p, closing that shortcut and requiring lattice methods.

3. Step 3

   Extract MASTER_KEY and decrypt the flag

   Observation

   I noticed that chall.py sets coeffs[0] = bytes_to_long(MASTER_KEY) and MASTER_KEY is a 32-byte SHA-256 digest, so any LLL row entry with bit length between 250 and 260 was a candidate key that could be converted directly to bytes and used as the AES-CBC key to decrypt the flag.

   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"" * 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

   chall.py sets coeffs[0] = bytes_to_long(MASTER_KEY) where MASTER_KEY is already sha256(flag).digest(). LLL recovers that exact integer, so to_bytes(32, 'big') gives the raw 32-byte AES key directly. Adding another SHA-256 round produces the wrong key and AES decryption returns garbage or raises 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

   chall.py hardcodes iv = b'\x00' * 16 and does not prepend it. If you treat the first 16 bytes of the ciphertext hex as the IV, the actual first ciphertext block is shifted and decryption produces the right suffix but a garbled first 16 bytes, hiding the 'picoCTF' prefix and making it look like the key guess was 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.