MSS_ADVANCE Revenge picoCTF 2026 Solution

Description

1. Step 1Understand the scheme
   This is a variant of Shamir Secret Sharing where the polynomial coefficients have an algebraic relationship. The secret is the polynomial's constant term, and the shares are evaluations at specific points. LLL lattice reduction can exploit the structure to recover the secret.
   Learn more

   Shamir's Secret Sharing (SSS) is a cryptographic scheme that splits a secret into n shares such that any k shares reconstruct the secret, but fewer than k shares reveal nothing. The standard construction encodes the secret as the constant term of a random degree-(k-1) polynomial over a finite field, then distributes evaluations of the polynomial at distinct points as shares. Reconstruction uses Lagrange interpolation.

   The "advanced revenge" variant departs from standard SSS by imposing an algebraic relationship between the polynomial's coefficients. This means the coefficients are not independently random - they lie on a lattice of small-norm vectors. Standard SSS is information-theoretically secure when fewer than k shares are known; this modified scheme is not, because the coefficient structure leaks information that lattice algorithms can exploit.

   LLL (Lenstra-Lenstra-Lovász) lattice basis reductionis a polynomial-time algorithm that finds a "short" basis for a lattice. If the secret polynomial's coefficients are small relative to the modulus, LLL can recover them from the share evaluations. This is a classical attack in cryptanalysis: many cryptographic constructions that use "random-looking but structured" values are vulnerable to lattice attacks.

2. Step 2Set up the lattice
   Express the shares as polynomial constraints, anchor the modulus, and run LLL. If the first reduction returns no useful short vector, debug the lattice: check the polynomial degree matches the number of shares, the modulus matches chall.py exactly, and each row encodes the constraint right.
   python

   # In SageMath:
   sage << 'EOF'
   from output import shares, modulus  # load from output.txt
   
   # Build the lattice matrix from the share evaluations
   # Each share: y_i = f(x_i) mod p where f has small coefficients
   # Set up a lattice and apply LLL
   
   # Example structure (adjust to match chall.py):
   n   = len(shares)
   deg = n - 1
   M   = Matrix(ZZ, n+1, n+1)
   for i, (x, y) in enumerate(shares):
       for j in range(deg+1):
           M[i, j] = (x^j * modulus)
       M[i, n] = y
   
   M[n, n] = 1  # small-entry anchor
   
   L = M.LLL()
   secret = int(L[0][-1]) % modulus
   print("Secret:", secret)
   # Pad odd-length hex with a leading zero before bytes.fromhex
   h = hex(secret)[2:]
   if len(h) % 2: h = "0" + h
   print(bytes.fromhex(h))
   EOF

   Copied!
   Learn more

   SageMath is a mathematics software system built on top of Python. It provides a Matrix(ZZ, ...) class for integer matrices and an .LLL() method that implements the LLL algorithm. SageMath is the standard tool for lattice-based cryptanalysis in CTF competitions because it has built-in support for all the required linear algebra over arbitrary integer rings.

   The lattice construction encodes the shares as constraints: each share (x_i, y_i) gives an equation y_i = a_0 + a_1*x_i + ... + a_{d}*x_i^d (mod p). By rearranging and embedding into a lattice matrix, the short coefficient vector (a_0, a_1, ..., a_d) becomes the shortest vector in the lattice - which LLL can find efficiently. The secret is the constant term a_0.

   LLL on a Shamir lattice (toy parameters):
     Modulus p = 257, threshold k = 3, polynomial f(x) = a0 + a1*x + a2*x^2
     with small-norm coefficients (each |ai| < 16).
   
   Suppose shares are (1, 200), (2, 134), (3, 81).
     200 = a0 +   a1 +   a2  (mod 257)
     134 = a0 + 2*a1 + 4*a2  (mod 257)
      81 = a0 + 3*a1 + 9*a2  (mod 257)
   
   Build a lattice basis where rows enforce these mod-p relations:
     [ 1   0   0   |  -200 ]
     [ 0   1   0   |  -134 ]
     [ 0   0   1   |   -81 ]
     [ 1   1   1   |   257 ]   <-- p anchor row
     [ 1   2   4   |   257 ]
     [ 1   3   9   |   257 ]
   
   After LLL reduction the shortest vector contains the coefficients
      (a0, a1, a2) = (3, -7, 12)   (small-norm, as expected).
   
   Bigger picture: with k shares producing k equations, the secret
   coefficient vector becomes the unique short vector in a 2k-dim
   lattice. LLL runs in O(d^6 log^3 B) where B is the entry size.

   Lattice attacks are one of the most powerful techniques in modern cryptanalysis. They have been used to break:

   • ECDSA with biased nonces (used to break Bitcoin private keys)
   • RSA with small private exponents (Wiener's attack and Coppersmith's method)
   • GnuPG DSA signatures with weak randomness
   • Learning With Errors (LWE) instances with small parameters

   One thing the toy 257-modulus example above does not capture: real challenges use 256-bit moduli where the "small coefficient" bound is much looser, and LLL alone may need help (BKZ reduction, scaling rows, weighting columns) before the short vector pops out. The strategy is the same; the bound and lattice tuning are not. The toy walkthrough shows the structure; expect to iterate on row scaling, weighting, and embedding before the actual instance reduces. See the RSA attacks guide for adjacent lattice patterns (Coppersmith, Wiener) on number-theoretic CTF challenges.

   Ironically, post-quantum cryptography (the next generation of encryption designed to resist quantum computers) is based on the hardness of lattice problems like LWE and NTRU, the same mathematical structures that make these attacks possible when parameters are too small.

Flag

The modified Shamir scheme's polynomial coefficients satisfy a short-norm condition exploitable with LLL lattice reduction.