MSS Revenge

Este reto es el mismo que MSS, pero con una correción para evitar una solución.

Revisión del reto

El servidor crea un polinomio con coeficientes aleatorios de 256 bits:

$$ P(x) = \mathrm{key} + a_1 x + a_2 x^2 + \dots + a_{30} x^{30} $$

El objetivo es encontrar $\mathrm{key}$, que se utiliza para derivar una clave de AES para cifrar la flag. El servidor nos permite evaluar el polinomio 19 veces con valores de $0 < x \leqslant 2^{15}$.

No podemos recuperar el polinomio completo porque necesitaríamos un mínimo de 31 valores.

Solución

El problema de este reto es que el polinomio se define sobre los enteros. Como resultado, si evaluamos $P(n)$ y aplicamos módulo $n$, obtendremos el valor de $\mathrm{key} \mod{n}$.

Sabiendo esto, podemos hacer lo mismo pero con números primos. El objetivo es obtener este sistema de congruencias:

$$ \begin{cases} P(p_1) = \mathrm{key} \mod{p_1} \\ P(p_2) = \mathrm{key} \mod{p_1} \\ \dots \\ P(p_k) = \mathrm{key} \mod{p_k} \\ \end{cases} $$

Este sistema de congruencias modulares se puede resolver utilizando el Teorema Chino del Resto (CRT), que generará el valor de $\mathrm{key} \mod{\prod p_k}$. Si $\prod p_k$ es lo suficientemente grande, el módulo no tendrá efecto y encontraremos el valor exacto de $\mathrm{key}$.

Todos estos números primos deben ser menores que $2^{15}$, y podemos usar un máximo de $k = 19$. Estos límites son suficientes para obtener el valor de $\mathrm{key}$ porque es un número de 256 bits, y $\prod p_k$ tendrá un valor máximo de $15 \cdot 19 = 285$ bits.

Implementación

Podemos programar este procedimiento en Python:

io = get_process()

primes, remainders = [], []

for _ in range(19):
    p = getPrime(15)
    io.sendlineafter(b'query = ', json.dumps(
        {'command': 'get_share', 'x': p}).encode())
    r = json.loads(io.recvline().decode()).get('y')
    primes.append(p)
    remainders.append(r % p)

key = crt(primes, remainders)[0]

io.sendlineafter(b'query = ', json.dumps({'command': 'encrypt_flag'}).encode())  
io.recvuntil(b'[+] Here is your encrypted flag : ')
data = json.loads(io.recvuntil(b'}').decode())

iv = bytes.fromhex(data.get('iv'))
enc_flag = bytes.fromhex(data.get('enc_flag'))

key = sha256(str(key).encode()).digest()
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = unpad(cipher.decrypt(enc_flag), AES.block_size).decode()
io.success(flag)

Flag

Y aquí tenemos la flag:

$ python3 solve.py 94.237.52.253:33222
[+] Opening connection to 94.237.52.253 on port 33222: Done  
[+] HTB{R3venge_0f_7he_sm4ll_thr3sh0ld_!}
[*] Closed connection to 94.237.52.253 port 33222

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