Share
8 minutos de lectura
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
Esquema de Shamir Secret Sharing
Deje que el polinomio generado sea:
Podríamos recuperar todos los coeficientes del polinomio de grado
Con ellos, podemos construir un sistema de ecuaciones sobre los
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 os.urandom
, y es diferente en cada ejecución del servidor. Obsérvese que todos los coeficientes están en
Cuando esto sucede, podríamos convertir el problema en tener algunos restos de
Problemas
Un gran problema es que solo nos dan
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
Solución
Para cada número 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 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
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
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
a get_secret_mod
para calcular
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 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 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
.