S.S.S.
15 Jul 2020This is a writeup for HexionCTF 2020, where we placed third.
Challenge Description:
Math is so beautiful and can always be used for cryptographic
encryption!
nc challenges1.hexionteam.com 5001
Solving :
We are given an sss.py. See here for source.
We found that SSS stands for Shamir’s Secret Sharing by copy-pasting the loop from eval_at, which brought me to this Wikipedia Page. Shamir Secret Sharing is based on polynomials and lagrange interpolation.
Most of this code (nearly everything except main) is taken from Wikipedia’s example implementation of Shamir’s Secret Sharing. The concept is relatively simple. The sss.py that we are given is giving out “shares”, with the flag as the secret. We can just request enough shares until we meet the minimum threshold to be able to recover the secret. From there, we can use langrage interpolation to calculate y for x=0 and retrieve our flag.
Solve Script :
from Crypto.Util.number import long_to_bytes
from pwn import remote
P = 2 ** 521 - 1
def eval_at(poly, x, prime):
accum = 0
for coeff in reversed(poly):
accum *= x
accum += coeff
accum %= prime
return accum
def extended_gcd(a, b):
x = 0
last_x = 1
y = 1
last_y = 0
while b != 0:
quot = a // b
a, b = b, a % b
x, last_x = last_x - quot * x, x
y, last_y = last_y - quot * y, y
return last_x, last_y
def divmod(num, den, p):
inv, _ = extended_gcd(den, p)
return num * inv
def _lagrange_interpolate(x, x_s, y_s, p):
k = len(x_s)
assert k == len(set(x_s)), "points must be distinct"
def PI(vals): # product of inputs
accum = 1
for v in vals:
accum *= v
return accum
nums = []
dens = []
for i in range(k):
others = list(x_s)
cur = others.pop(i)
nums.append(PI(x - o for o in others))
dens.append(PI(cur - o for o in others))
den = PI(dens)
num = sum([divmod(nums[i] * den * y_s[i] % p, dens[i], p)
for i in range(k)])
return (divmod(num, den, p) + p) % p
def recover_secret(shares, prime=P):
x_s, y_s = zip(*shares)
return _lagrange_interpolate(0, x_s, y_s, prime)
def main():
# connect to the nc server
r = remote("challenges1.hexionteam.com", 5001)
r.recvuntil(">>>")
shares = []
# request 78 shares, just to be safe (min is a random int between 48 and 63, inclusive)
for i in range(0x1, 0x50):
if i == ord('\n'):
continue
r.sendline(long_to_bytes(i))
resp = r.recvline().decode()
resp = resp.strip().strip('>').strip()
shares.append((i,int(resp)))
if len(shares) % 5 == 0:
print("Acquired", len(shares), "shares")
# print(shares)
print(long_to_bytes(recover_secret(shares)))
if __name__ == '__main__':
main()
Flag : hexCTF{d0nt_us3_shar3s_lik3_that}