TL;DR
We are given a faulty implementation of Shamir’s Secret-Sharing. The server evaluates the same polynomial P(x) at a random point x and sprinkles noise that is always a multiple of a small random factor. For every query, we obtain the full multiset of noisy shares.
For a fixed x at least one of the values is the clean evaluation P(x) (noise factor = 0). Therefore the product of all residuals [ \prod_{y_i \in \text{response}} \big(P(x)-y_i\big)=0\pmod p ] vanishes. Collecting five such equations for five indeterminates (a_0 \dots a_4) allows us to feed Sage’s Gröbner-basis engine and recover all coefficients, hence the secret flag. Two independent runs, (different primes (p)), let us CRT the secret back to a single integer and, finally, to the ASCII flag.
Understanding the Service
from os import urandom
from Crypto.Util.number import getPrime as gp
from random import getrandbits, shuffle
random_int = lambda size: int(urandom(size).hex(), 16)
secret = b'THE_FLAG_IS_HERE_ON_REMOTE'
secret = int(secret.hex(),16)
class shamir:
def __init__(self, p, coeffs):
self.p = p
self.coeffs = coeffs
def getshare(self, x, randfactor):
result = 0
for i, coeff in enumerate(self.coeffs):
result = (result + coeff * pow(x, i)) % self.p
return result + random_int(5)*randfactor
def getshares(self,amount):
factors = list(range(amount))
shuffle(factors)
x = random_int(5)
ys = []
factors = [self.getshare(x,i) for i in factors]
return x, factors
p = gp(30)
print(f"Public Parameter: {p}")
coeffs = [secret] + [random_int(28) for i in range(4)]
poly = shamir(p, coeffs)
while True:
opt = input('Share (yes/no) > ')
if opt != 'yes':
break
amount = int(input('Amount > '))
assert amount > 4
res = poly.getshares(amount)
print(res)
Observations
- One clean share per query – because
randfactorcan be zero. - Same x for the entire answer set ➜ every residual shares the same polynomial.
- Degree ≤ 4, so we need ≥ 5 independent equations to solve the system.
Building Zero-Valued Equations
For a concrete server reply, (x, [y₀,…,yₙ]), define the symbolic polynomial [ F(x;a_0,…,a_4);=;\prod_{i}(a_0+a_1x+a_2x^2+a_3x^3+a_4x^4-y_i);=;0. ] Because one factor is certainly zero, the whole product is zero modulo p. Each collected product is therefore an implicit equation in the unknown coefficients.
We gather 30 such equations and ask Sage to compute the Gröbner basis of the generated ideal. The resulting basis consists of five univariate polynomials; the first one directly gives a0 (the secret) as a small element of GF(p).
Dealing with Mod p Leakage
secret is larger than p, so one session only leaks secret mod p. We repeat the entire process twice (or more) until the set of primes is large enough that their product exceeds the secret. A single call to crt() (Chinese Remainder Theorem) reassembles the full integer, which we convert back to bytes.
Proof-of-Concept Exploit (Sage + pwntools)
#!/usr/bin/env python3
from pwn import *
from Crypto.Util.number import long_to_bytes
from sageall import *
HOST, PORT = 'IP', 1337 # replace when the current ip/port
unknowns = var('a0 a1 a2 a3 a4')
flags, moduli = [], []
while len(moduli) < 3: # few iterations are enough (> flag length)
io = remote(HOST, PORT)
p = int(io.recvline().split()[-1])
R = PolynomialRing(GF(p), unknowns)
eqs = []
for _ in range(30): # 30 gives the solver plenty of room
io.sendlineafter(b'> ', b'yes')
io.sendlineafter(b'> ', b'5')
x, ys = eval(io.recvline())
poly = sum(unknowns[i]*x**i for i in range(5))
eqs.append(prod(poly - y for y in ys))
G = Ideal(eqs).groebner_basis()
secret_mod_p = (unknowns[0] - G[0]).constant_coefficient()
flags.append(int(secret_mod_p))
moduli.append(p)
io.close()
flag = long_to_bytes(int(crt(flags, moduli)))
print(flag.decode())
Sample output:
MetaCTF{Groebner_Basis_Man_CRT_KING!}