Share

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 $p$ and a number $n$ such that $13 < n < p$ to create a Shamir Secret Sharing scheme. The polynomial $P(x)$ of degree $n - 1$ will have random coefficients in $\mathbb{F}_p$ and the secret $S$ will be the independent term ($S = P(0)$). We are given these shares: $\big\{P(1), \dots, P(n - 1)\big\}$.

Shamir Secret Sharing scheme

Let the generated polynomial be:

$$ P(x) = S + a_1 x + a_2 x^2 + \dots + a_{n - 1} x^{n - 1} \pmod{p} $$

We would be able to recover all the coefficients of the $(n - 1)$-degree polynomial if we had at least $n$ distinct points, let’s say

$$ \big\{(x_1, P(x_1)), (x_2, P(x_2)), \dots, (x_n, P(x_n))\big\} $$

With those, we can build a system of equations on the $n$ coefficients ($S$ and $a_i$):

$$ \begin{cases} S + a_1 x_1 + a_2 x_1^2 + \dots + a_{n - 1} x_1^{n - 1} = P(x_1) \\ S + a_1 x_2 + a_2 x_2^2 + \dots + a_{n - 1} x_2^{n - 1} = P(x_2) \\ \dots \\ S + a_1 x_n + a_2 x_n^2 + \dots + a_{n - 1} x_n^{n - 1} = P(x_n) \\ \end{cases} $$

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 $S$, which is a 32-byte number generated by os.urandom, and it is different on every execution of the server. Notice that all coefficients will be in $\mathbb{F}_p$, for a chosen prime $p$. And that will affect the secret $S$ too.

When this happens, we could turn the problem into having some remainders of $S$ modulo some different prime numbers and then use the Chinese Remainder Theorem to find $S$ (assuming that the product of all the chosen primes has a length greater than 32 bytes).

Problems

One big problem is that we are only given $n - 1$ shares, which is not enough to recover all the coefficients. We are left with one degree of freedom. We might think on doing brute force on the last share value, which is affordable (iterating from $0$ to $p - 1$), but we need to know if the resulting coefficients are right or not.

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 $0$ and $p - 2$ (both included). As a result, there won’t be any coefficient with a value of $p - 1$ in the result of the Lagrange polynomial. Hence, we can use this to determine if a polynomial is right or not.

Solution

For each prime number $p$, we will select $n = p - 1$ to increase the number of coefficients of the polynomial and thus the probability of having a $p - 1$ coefficient in the Lagrange polynomial. We will iterate $P(0) = s_x$ for $0 \leqslant s_x < p$. We will discard those $s_x$ that result in some coefficient equal to $p - 1$. We will request another polynomial with the same values $p$ and $n$ until we only have a single possible value for $s_x$. At that point, we will have one remainder $s_x = S \mod{p}$, so we move on to the next prime.

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 $p$, $n$ values. There is a dictionary called 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 $17$ and $199$ will result in a sufficient number of congruences to solve the CRT and recover the 32-byte secret. But now the problem is time.

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 $n = 14$ was faster locally, but around 2000 queries were needed, so in remote was not possible.

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$, I will use $n = p - 1$ and request a total of 9 polynomials (it works most of the times). Then, I send all the shares along with the p value to get_secret_mod to compute $S \mod{p}$.

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 $107$ to $293$ in reverse order, so that the first primes that are processed are the ones that will take longer to 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 $S$ is a 32-byte number, then we send it to the server to get the flag; otherwise, we need to run the script again (some times, 9 polynomials are not enough to get a single value from 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.