Share
8 minutes to read
We are given the Python source code of the server:
#!/usr/bin/env python3
from Crypto.Util.number import isPrime, getRandomRange, bytes_to_long
from typing import List
import os, signal
class SecretSharing:
def __init__(self, p: int, n: int, secret: int):
self.p = p
self.n = n
self.poly = [secret] + [getRandomRange(0, self.p - 1) for _ in range(n - 1)]
def evaluate(self, x: int) -> int:
return (
sum([self.poly[i] * pow(x, i, self.p) for i in range(len(self.poly))])
% self.p
)
def get_shares(self) -> List[int]:
return [self.evaluate(i + 1) for i in range(self.n)]
if __name__ == "__main__":
signal.alarm(30)
secret = bytes_to_long(os.urandom(32))
while True:
p = int(input("p = "))
n = int(input("n = "))
if isPrime(p) and int(13.37) < n < p:
shares = SecretSharing(p, n, secret).get_shares()
print("shares =", shares[:-1])
else:
break
if int(input("secret = ")) == secret:
print(open("flag.txt", "r").read().strip())
Source code analysis
The code is simple. Basically, it allows us to enter a prime number
Shamir Secret Sharing scheme
Let the generated polynomial be:
We would be able to recover all the coefficients of the
With those, we can build a system of equations on the
The system above can be solved using a matrix equation. However, there is another implementation, which is Lagrange interpolation. This method will be faster than creating a matrix and solving for the coefficients.
The objective
We will try to find the secret os.urandom
, and it is different on every execution of the server. Notice that all coefficients will be in
When this happens, we could turn the problem into having some remainders of
Problems
One big problem is that we are only given
To make things worse, the server disconnects after 30 seconds…
The security flaw
The bug of the SSS implementation is here:
class SecretSharing:
def __init__(self, p: int, n: int, secret: int):
self.p = p
self.n = n
self.poly = [secret] + [getRandomRange(0, self.p - 1) for _ in range(n - 1)]
The output of getRandomRange(0, p - 1)
is a random number between
Solution
For each prime number
This function implements the above procedure:
def get_secret_mod(p, all_shares):
P = polys[p]
possible = set()
shares = next(all_shares)
for sx in range(p):
ret = P.lagrange_polynomial(enumerate([sx] + shares)).coefficients(sparse=False)
if p - 1 not in ret[1:]:
possible.add(sx)
while len(possible) != 1:
try:
shares = next(all_shares)
except StopIteration:
break
for sx in list(possible):
ret = P.lagrange_polynomial(enumerate([sx] + shares)).coefficients(sparse=False)
if p - 1 in ret[1:] and sx in possible:
possible.remove(sx)
return p, list(possible)[0]
The variable all_shares
is an iterator with all the shares for several polynomials of the same polys
where I store PolynomialRing(GF(p))
for all chosen prime numbers p
, just for speed. In the first for
loop, I take the values of sx
that are valid using just one set of shares. Then, in the while
loop, I remove all sx
that are wrong using the other sets of shares until I get a single value in possible
.
Optimization
Running the function above with enough polynomials for all prime numbers between
Locally, there is no problem. The simplest code runs in about 10 seconds, but needs more than 200 queries to the server. In remote, each connection will last half a second, and the server disconnects after 30 seconds…
I lost some time trying to think of methods to use bigger primes, or less queries, but they were actually slower. Using
Then I just came up with a way to send several queries in the same message, and receive all the shares for all my queries in the same message as well. I mean this:
$ echo '17\n14\n17\n14\n17\n14' | nc chal-share.chal.hitconctf.com 11111
p = n = shares = [11, 4, 8, 0, 4, 0, 9, 0, 10, 13, 11, 10, 13]
p = n = shares = [15, 9, 9, 11, 5, 7, 6, 4, 5, 5, 6, 6, 3]
p = n = shares = [12, 6, 10, 0, 5, 4, 3, 13, 1, 9, 13, 13, 16]
p =
So, that’s what I will do: for each prime p
value to get_secret_mod
to compute
This was a great improvement, but it was not enough. What I did then is use multiprocessing
, to query the server while other processes worked on get_secret_mod
. This was much more fast, but still not enough to finish in less than 30 seconds. After that, what I did is use primes from get_secret_mod
. The following code illustrates the previous explanation:
def callback(t):
crt_remainders[t[0]] = t[1]
primes = [107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293]
crt_remainders = {p: -1 for p in primes}
polys = {p: PolynomialRing(GF(p), 'x') for p in primes}
length = 9
io = get_process()
io.recv()
with Pool(processes=8) as pool:
for p in primes[::-1]:
io.send((f'{p}\n{p - 1}\n' * length).encode())
sleep(.8)
data = b''.join(io.recvuntil(b'share') for _ in range(length)) + io.recvline()
io.recv()
shares = map(eval, re.findall(r'shares = (.*?)\n', data.decode()))
pool.apply_async(get_secret_mod, (p, shares), callback=callback)
while -1 in crt_remainders.values():
pass
The last while
loop is just to wait for all processes to put their result in crt_remainders
(callback
execution).
Finally, we just take the prime numbers as moduli and the remainders and apply the CRT. If the result get_secret_mod
).
primes, remainders = [], []
for p, r in crt_remainders.items():
primes.append(p)
remainders.append(r)
s = CRT(remainders, primes)
if 240 <= int(s).bit_length() <= 256:
io.info(f'Secret: {s}')
io.sendline(b'0')
io.sendlineafter(b'n = ', b'0')
io.sendlineafter(b'secret = ', str(s).encode())
try:
io.success(io.recv().decode())
except EOFError:
io.failure('FAIL')
else:
io.failure('FAIL')
exit()
Flag
And this is the flag:
$ python3 solve.py chal-share.chal.hitconctf.com 11111
[+] Opening connection to chal-share.chal.hitconctf.com on port 11111: Done
[*] Secret: 63092015686323036458283318406318002879418534896764705265127381722125639499808
[+] hitcon{even_off_by_one_is_leaky_in_SSS}
[*] Closed connection to chal-share.chal.hitconctf.com port 11111
The full script can be found in here: solve.py
.