Share

Se nos proporciona el código fuente en Python del servidor:

#!/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())

Análisis del código fuente

El código es simple. Básicamente, nos permite ingresar un número primo $p$ y un número $n$ tal que $13 < n < p$ para crear un esquema de Shamir Secret Sharing. El polinomio $P(x)$ de grado $n - 1$ tendrá coeficientes aleatorios en $\mathbb{F}_p$ y el secreto $S$ será el término independiente ($S = P(0)$). Se nos dan estos shares: $\big\{P(1), \dots, P(n - 1)\big\}$.

Esquema de Shamir Secret Sharing

Deje que el polinomio generado sea:

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

Podríamos recuperar todos los coeficientes del polinomio de grado $(n - 1)$ si tuviéramos al menos $n$ puntos distintos, digamos

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

Con ellos, podemos construir un sistema de ecuaciones sobre los $n$ coeficientes ($S$ y $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} $$

El sistema anterior se puede resolver utilizando una ecuación de matriz. Sin embargo, hay otra implementación, que es el polinomio interpolador de Lagrange. Este método será más rápido que crear una matriz y resolver los coeficientes.

El objetivo

Intentaremos encontrar el secreto $S$, que es un número de 32 bytes generado por os.urandom, y es diferente en cada ejecución del servidor. Obsérvese que todos los coeficientes están en $\mathbb{F}_p$, para un prime $p$ elegido. Y eso afecta el secreto $S$ también.

Cuando esto sucede, podríamos convertir el problema en tener algunos restos de $S$ módulo algunos números primos diferentes y luego usar el Teorema Chino del Resto (CRT) para encontrar $S$ (suponiendo que el producto de todos los primos elegidos es de más de 32 bytes).

Problemas

Un gran problema es que solo nos dan $n - 1$ shares, que no son suficientes para recuperar todos los coeficientes. Nos queda un grado de libertad. Podríamos pensar en hacer una fuerza bruta sobre el último valor de share, que es asequible (iterando de $0$ a $p - 1$), pero necesitamos saber si los coeficientes resultantes son correctos o no.

Para empeorar las cosas, el servidor se desconecta después de 30 segundos…

El fallo de seguridad

El error de la implementación de SSS está aquí:

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)]  

La salida de getRandomRange(0, p - 1) es un número aleatorio entre $0$ y $p - 2$ (ambos incluidos). Entonces, no habrá ningún coeficiente con un valor de $p - 1$ en el resultado de la interpolación de Lagrange. Por lo tanto, podemos usar esto para determinar si un polinomio es correcto o no.

Solución

Para cada número primo $p$, seleccionaremos $n = p - 1$ para aumentar el número de coeficientes del polinomio y, por lo tanto, la probabilidad de tener un coeficiente de $p - 1$ en el polinomio interpolador de Lagrange. Iteraremos $P(0) = s_x$ en $0 \leqslant s_x < p$. Descartaremos los $s_x$ que dan como resultado algún coeficiente igual a $p - 1$. Solicitaremos otro polinomio con los mismos valores $p$ y $n$ hasta que solo tengamos un solo valor posible para $s_x$. En ese momento, tendremos un resto $s_x = S \mod{p}$, por lo que pasamos al siguiente primo.

Esta función implementa el procedimiento anterior:

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]

La variable all_shares es un iterador con todas los shares para varios polinomios de los mismos $p$ y $n$. Hay un diccionario llamado polys donde guardo PolynomialRing(GF(p)) para todos los números primos p elegidos, por rapidez. En el primer bucle for, tomo los valores de sx que son válidos usando solo un conjunto de shares. Luego, en el bucle while, elimino aquellos sx que están mal usando los otros conjuntos de shares hasta que queda un solo valor en possible.

Optimización

Si ejecutamos la función anterior con suficientes polinomios para todos los números primos entre $17$ y $199$ obtendremos como resultado un número suficiente de congruencias para resolver el CRT y recuperar el secreto de 32 bytes. Pero ahora el problema es el tiempo.

En local no hay problema. El código más simple se ejecuta en aproximadamente 10 segundos, pero necesita más de 200 consultas al servidor. En remoto, cada conexión durará medio segundo, y el servidor se desconecta después de 30 segundos…

Perdí algo de tiempo tratando de pensar en métodos para usar primos más grandes, o menos consultas, pero en realidad eran más lentos. Usar $n = 14$ fue más rápido localmente, pero necesitaba alrededor de 2000 consultas, por lo que no era factible tampoco.

Luego se me ocurrió una forma de enviar varias consultas en el mismo mensaje y recibir todos los shares para todas mis consultas en el mismo mensaje también. Me refiero a esto:

$ 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 =

Entonces, eso es lo que haré: por cada primo $p$, usaré $n = p - 1$ y solicitaré un total de 9 polinomios (funciona la mayoría de las veces). Luego, envío todos los shares junto con el valor p a get_secret_mod para calcular $S \mod{p}$.

Esta fue una gran mejora, pero no fue suficiente. Lo que hice entonces fue usar multiprocessing, para consultar al servidor mientras otros procesos trabajaban en get_secret_mod. Esto fue mucho más rápido, pero aún no suficiente para terminar en menos de 30 segundos. Después de eso, lo que hice fue usar números primos entre $107$ y $293$ en orden inverso, de manera que los primeros primos que se procesan son los que tardarán más en calcular get_secret_mod. El siguiente código ilustra la explicación anterior:

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

El último bucle while es solo para esperar a que todos los procesos pongan su resultado en crt_remainders (ejecución de callback).

Finalmente, solo tomamos los números primos como módulos y los restos y aplicamos el CRT. Si el resultado $S$ es un número de 32 bytes, entonces lo enviamos al servidor para obtener la flag; de lo contrario, necesitamos ejecutar el script nuevamente (algunas veces, 9 polinomios no son suficientes para obtener un solo valor en 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

Y esta es la 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

El script completo se puede encontrar aquí: solve.py.