Space Pirates
3 minutos de lectura
Se nos proporciona el siguiente código en Python:
from sympy import *
from hashlib import md5
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from random import randint, randbytes, seed
FLAG = b'HTB{dummyflag}'
class Shamir:
def __init__(self, prime, k, n):
self.p = prime
self.secret = randint(1, self.p - 1)
self.k = k
self.n = n
self.coeffs = [self.secret]
self.x_vals = []
self.y_vals = []
def next_coeff(self, val):
return int(md5(val.to_bytes(32, byteorder='big')).hexdigest(), 16)
def calc_coeffs(self):
for i in range(1, self.n + 1):
self.coeffs.append(self.next_coeff(self.coeffs[i - 1]))
def calc_y(self, x):
y = 0
for i, coeff in enumerate(self.coeffs):
y += coeff * x ** i
return y % self.p
def create_pol(self):
self.calc_coeffs()
self.coeffs = self.coeffs[:self.k]
for _ in range(self.n):
x = randint(1, self.p - 1)
self.x_vals.append(x)
self.y_vals.append(self.calc_y(x))
def get_share(self):
return self.x_vals[0], self.y_vals[0]
def main():
sss = Shamir(92434467187580489687, 10, 18)
sss.create_pol()
share = sss.get_share()
seed(sss.secret)
key = randbytes(16)
cipher = AES.new(key, AES.MODE_ECB)
enc_FLAG = cipher.encrypt(pad(FLAG, 16)).hex()
print(sss.coeffs)
f = open('msg.enc', 'w')
f.write('share: ' + str(share) + '\n')
f.write('coefficient: ' + str(sss.coeffs[1]) + '\n')
f.write('secret message: ' + str(enc_FLAG) + '\n')
f.close()
if __name__ == '__main__':
main()
Y este es el resultado:
share: (21202245407317581090, 11086299714260406068)
coefficient: 93526756371754197321930622219489764824
secret message: 1aaad05f3f187bcbb3fb5c9e233ea339082062fc10a59604d96bcc38d0af92cd842ad7301b5b72bd5378265dae0bc1c1e9f09a90c97b35cfadbcfe259021ce495e9b91d29f563ae7d49b66296f15e7999c9e547fac6f1a2ee682579143da511475ea791d24b5df6affb33147d57718eaa5b1b578230d97f395c458fc2c9c36525db1ba7b1097ad8f5df079994b383b32695ed9a372ea9a0eb1c6c18b3d3d43bd2db598667ef4f80845424d6c75abc88b59ef7c119d505cd696ed01c65f374a0df3f331d7347052faab63f76f587400b6a6f8b718df1db9cebe46a4ec6529bc226627d39baca7716a4c11be6f884c371b08d87c9e432af58c030382b737b9bb63045268a18455b9f1c4011a984a818a5427231320ee7eca39bdfe175333341b7c
Se está utilizando Shamir Secret Sharing (SSS) para obtener un valor compartido e inicializar random.seed, de manera que la clave para un cifrado AES es “aleatoria”. Luego, se cifra la flag con AES.
Esta vez, los parámetros de SSS son $p = 92434467187580489687$, $k = 10$ y $n = 18$. Entonces, el servidor creará un polinomio $P \in \mathbb{Z}/p\mathbb{Z}[x]$ como este:
$$ P(x) = s + a_1 x + a_2 x^2 + a_3 x^3 + \dots + a_k x^k $$
El secreto está denotado por $s$ (el término independiente).
Luego, el servidor calcula algunas parejas $(x_i, P(x_i))$. De hecho, desde $(x_1, P(x_1))$ hasta $(x_n, P(x_n))$.
El valor compartido que nos da el programa es $(x_1, P(x_1))$. También sabemos el coeficiente $a_1$.
La vulnerabilidad aquí es que los coeficientes $a_i$ están relacionados:
def next_coeff(self, val):
return int(md5(val.to_bytes(32, byteorder='big')).hexdigest(), 16)
def calc_coeffs(self):
for i in range(1, self.n + 1):
self.coeffs.append(self.next_coeff(self.coeffs[i - 1]))
Entonces, $a_{i + 1} = \mathrm{MD5}(a_i)$. Considerando que sabemos $a_1$, podemos calcular $a_2$, luego $a_3$, y por inducción $a_k$… Por lo que tenemos todos los coeficientes del polinomio $P$ excepto el término independiente $s$.
El hecho de tener todos los valores $a_i$ es útil porque también tenemos $(x_1, P(x_1))$, así que podemos resolver la siguiente ecuación en $s$, que es la única incógnita:
$$ P(x_1) = s + a_1 x_1 + a_2 x_1^2 + \dots + a_k x_1^k $$
Por tanto
$$ s = P(x_1) - a_1 x_1 - a_2 x_1^2 - \dots - a_k x_1^k $$
Y una vez que tenemos $s$, podemos inicializar random.seed y obtener la misma clave “aleatoria” que se usó con el cifrado AES y descifrar el texto que nos dan para obtener la flag.
Todos los cálculos están escritos en el siguiente script en Python: solve.py:
$ python3 solve.py
The treasure is located at galaxy VS-708.
Our team needs 3 light years to reach it.
Our solar cruise has its steam canons ready to fire in case we encounter enemies.
Next time you will hear from us brother, everyone is going to be rich!
HTB{1_d1dnt_kn0w_0n3_sh4r3_w45_3n0u9h!1337}