Categories

# “SSS”

We are given an sss.py. See https://pastebin.com/KQhdB3fa for source.

I found that SSS stands for Shamir’s Secret Sharing by copy-pasting the loop from eval_at, which brought me to this Wikipedia page: https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing

From there I learned that sss.py was basically giving out shares, with the flag as the secret. So we can just request enough shares until we meet the minimum threshold to be able to recover the secret.

Most of this code (nearly everything except main) is taken from Wikipedia’s example implementation of Shamir’s Secret Sharing

If you want to understand it, Wikipedia can explain it much better than I can.

```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'):  # pwn remote didn't like me sending a newline, so I skipped that one
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()

# hexCTF{d0nt_us3_shar3s_lik3_that}```