TurboCipher
7 minutos de lectura
Este es un reto que diseñé para Hack the Box. Se nos proporciona el código fuente en Python del servidor:
#!/usr/bin/env python3
from Crypto.Util.number import bytes_to_long, getPrime, getRandomRange
from secret import FLAG, fast_turbonacci, fast_turbocrypt
from typing import Callable
def turbonacci(n: int, p: int, b: int, c: int) -> int:
if n < 2:
return n
return (b * turbonacci(n - 1, p, b, c) + c * turbonacci(n - 2, p, b, c)) % p
def lcg(x: int, m: int, n: int, p: int) -> int:
return (m * x + n) % p
def turbocrypt(pt: int, k: int, f: Callable[[int], int]) -> int:
return sum((f(i + 1) - f(i)) for i in range(k, pt))
def menu() -> int:
print('Choose one option')
print('1. Encrypt flag')
print('2. Encrypt ciphertext')
print('3. Exit')
return int(input('> '))
def main():
while True:
b, c, p = getPrime(512), getPrime(512), getPrime(512)
try:
for i in range(10):
assert turbonacci(i, p, b, c) == fast_turbonacci(i, p, b, c)
assert turbocrypt(i, -1, int) == fast_turbocrypt(i, -1, int)
break
except Exception:
pass
print('Welcome to TurboCipher. Please login first')
print(f'MathFA enabled. Parameters:\n{p = }\n{b = }\n{c = }\n')
nonce = getRandomRange(1, p)
print(f'Please, use {nonce = } to generate for your TurbOTP')
otp = int(input('OTP: '))
if otp != fast_turbonacci(nonce, p, b, c):
print('Login incorrect')
exit(1)
print('Login successful')
m, n, k = getPrime(512), getPrime(512), getPrime(512)
def f(x: int) -> int: return lcg(x, m, n, p)
while (option := menu()) != 3:
if option == 1:
assert len(FLAG) * 8 <= p.bit_length()
print(f'ct = {fast_turbocrypt(bytes_to_long(FLAG), k, f) % p}')
if option == 2:
pt = input('pt = ').strip().encode()
assert len(pt) * 8 <= p.bit_length()
print(f'ct = {fast_turbocrypt(bytes_to_long(pt), k, f) % p}')
print('Thank you for using TurboCipher. See you soon!')
if __name__ == '__main__':
main()
Se utiliza un módulo secret para importar FLAG y dos funciones fast_turbonacci y fast_turbocipher, que son desconocidas.
En primer lugar, el servidor solicita un OTP:
$ nc 161.35.164.52 32367
Welcome to TurboCipher. Please login first
MathFA enabled. Parameters:
p = 10661659656379701807207261625348824751044033238211111392569849487054221229293575280702103750314537453326306932228658369569073454707040110605919691900717053
b = 12467593298053953965932052065048352989295927860843731540896042086471795704069496789019816662750919938406850889847371974931468184690216537470130947978922201
c = 11194882392775831341327777305934471543299757495348856577436606655177652476332452517826350158956329959274674376711531677439838317968689922977478169623064503
Please, use nonce = 2791192687229595789736103907396883444691405059827201603678061147070993788594701998445970292672198658759814772391655851185818845695170123065778918881488885 to generate for your TurbOTP
OTP: 1234
Login incorrect
Relación de recurrencia
Este OTP se calcula usandofast_turbonacci, pero solamente nos dan turbonacci:
def turbonacci(n: int, p: int, b: int, c: int) -> int:
if n < 2:
return n
return (b * turbonacci(n - 1, p, b, c) + c * turbonacci(n - 2, p, b, c)) % p
Se parece bastante a la sucesión de Fibonacci, pero con coeficientes b y c y el módulo p. Vamos a definir $T_n$ como el término $n$-ésimo de la sucesión Turbonacci:
$$ T_0 = 0 $$
$$ T_1 = 1 $$
$$ T_n = b \cdot T_{n - 1} + c \cdot T_{n - 2} \mod{p} \quad, n > 1 $$
Para el OTP, nos dan un valor nonce. Y el OTP es $T_\text{nonce}$.
Obviamente, no podemos usar la función turbonacci porque es recursiva y no funcionará con un valor grande. Por tanto, tenemos que encontrar una forma cerrada de la sucesión Turbonacci.
Hallando una forma cerrada
Podemos comenzar cogiendo el polinomio característico (nos olvidamos del módulo de momento):
$$ t^n = b \cdot t^{n - 1} + c \cdot t^{n - 2} $$
Y esto es equivalente a
$$ t^2 = b \cdot t + c $$
Ahora resolvemos la ecuación cuadrática:
$$ t = \frac{b \pm \sqrt{b^2 + 4c}}{2} $$
Y tenemos lo siguiente, podemos expresar $T_n$ como
$$ T_n = \alpha \cdot \left(\frac{b + \sqrt{b^2 + 4c}}{2}\right)^n + \beta \cdot \left(\frac{b - \sqrt{b^2 + 4c}}{2}\right)^n $$
Sean $r_1 = \frac{b + \sqrt{b^2 + 4c}}{2}$ y $r_2 = \frac{b - \sqrt{b^2 + 4c}}{2}$.
Para encontrar $\alpha$ y $\beta$, podemos emplear dos valores conocidos (por ejemplo, $T_0$ y $T_1$).
$$ \begin{cases} T_0 = \alpha + \beta = 0 \newline T_1 = \alpha \cdot r_1 + \beta \cdot r_2 = 1 \end{cases} $$
Y ahora tenemos que resolver un sistema lineal de dos ecuaciones:
$$ \alpha = \frac{1}{r_1 - r_2} = -\beta $$
Y así conseguimos una forma cerrada de $T_n$:
$$ T_n = \frac{r_1^n - r_2^n}{r_1 - r_2} $$
Vale, ahora tenemos que aplicar el módulo $p$.
Para calcular $\sqrt{\Delta} = \sqrt{b^2 + 4c} \pmod{p}$, usaremos los métodos de Tonelli-Shanks o de Cipolla (para encontrar un $x$ tal que $x^2 \equiv n \pmod{p}$).
Necesitamos cambiar las divisiones por productos por el inverso módulo $p$.
Finalmente, la implementación de fast_turbonacci es:
def fast_turbonacci(n: int, p: int, b: int, c: int) -> int:
sqrt_delta = tonelli((pow(b, 2, p) + 4 * c), p)
r1 = (b + sqrt_delta) * pow(2, -1, p) % p
r2 = (b - sqrt_delta) * pow(2, -1, p) % p
return (pow(r1, n, p) - pow(r2, n, p)) * pow(r1 - r2, -1, p) % p
Podemos comenzar a crear el script en Python para introducir el OTP:
def main():
io = get_process()
io.recvuntil(b'p = ')
p = int(io.recvline().decode())
io.recvuntil(b'b = ')
b = int(io.recvline().decode())
io.recvuntil(b'c = ')
c = int(io.recvline().decode())
io.recvuntil(b'nonce = ')
nonce = int(io.recvuntil(b' ').strip().decode())
otp = fast_turbonacci(nonce, p, b, c)
io.sendlineafter(b'OTP: ', str(otp).encode())
io.interactive()
$ python3 solve.py 161.35.164.52:32367
[+] Opening connection to 161.35.164.52 on port 32367: Done
[*] Switching to interactive mode
Login successful
Choose one option
1. Encrypt flag
2. Encrypt ciphertext
3. Exit
> $
Alternativa
Otra manera de encontrar el OTP es calculando la potencia nonce de la siguiente matriz en $\mathbb{F}_p$:
$$ \begin{pmatrix} b & 1 \\ c & 0 \end{pmatrix} $$
El OTP será la entrada de arriba a la izquierda de la matriz resultante.
Serie telescópica
Genial, ahora podemos obtener la flag cifrada y también podemos cifrar textos arbitrarios:
while (option := menu()) != 3:
if option == 1:
assert len(FLAG) * 8 <= p.bit_length()
print(f'ct = {fast_turbocrypt(bytes_to_long(FLAG), k, f) % p}')
if option == 2:
pt = input('pt = ').strip().encode()
assert len(pt) * 8 <= p.bit_length()
print(f'ct = {fast_turbocrypt(bytes_to_long(pt), k, f) % p}')
El cifrado se gestiona con fast_turbocrypt, pero solamente tenemos turbocrypt:
def turbocrypt(pt: int, k: int, f: Callable[[int], int]) -> int:
return sum((f(i + 1) - f(i)) for i in range(k, pt))
Podemos expresar esta función en términos matemático somo (llamémosla $E$):
$$ E(\text{pt}) = \sum_{i = k}^{\text{pt} - 1} f(i + 1) - f(i) $$
Se trata de una serie telescópica, y su forma cerrada es:
$$ E(\text{pt}) = f(\text{pt}) - f(k) $$
Por tanto, fast_turbocrypt es:
def fast_turbocrypt(pt: int, k: int, f: Callable[[int], int]) -> int:
return f(pt) - f(k)
Generador Lineal Congruencial
La función f es un Generador Lineal Congruencial (LCG):
def lcg(x: int, m: int, n: int, p: int) -> int:
return (m * x + n) % p
# ...
def main():
# ...
m, n, k = getPrime(512), getPrime(512), getPrime(512)
def f(x: int) -> int: return lcg(x, m, n, p)
while (option := menu()) != 3:
if option == 1:
assert len(FLAG) * 8 <= p.bit_length()
print(f'ct = {fast_turbocrypt(bytes_to_long(FLAG), k, f) % p}')
# ...
Por tanto,
$$ f(x) = m \cdot x + n \pmod{p} $$
Ya conocemos el módulo $p$ desde el principio, pero no sabemos $m$ y $n$.
Entendiendo el cifrado
La función de cifrado mapea $\text{pt} \mapsto E(\text{pt}) = f(\text{pt}) - f(k)$. Como $f$ es un LCG, podemos expresar $E(\text{pt}) = m \cdot (\text{pt} - k) \pmod{p}$ y olvidarnos de $n$.
Para encontrar $m$, podemos cifrar dos textos:
$$ \begin{cases} \text{ct}_1 = E(\text{pt}_1) = m \cdot (\text{pt}_1 - k) \mod{p} \newline \text{ct}_2 = E(\text{pt}_2) = m \cdot (\text{pt}_2 - k) \mod{p} \end{cases} $$
Entonces
$$ \text{ct}_2 - \text{ct}_1 = m \cdot (\text{pt}_2 - \text{pt}_1) \mod{p} $$
Luego
$$ m = (\text{ct}_2 - \text{ct}_1) \cdot (\text{pt}_2 - \text{pt}_1)^{-1} \mod{p} $$
De hecho, para simplificar podemos forzar que $\text{pt}_2 - \text{pt}_1 = 1$, y así
$$ m = \text{ct}_2 - \text{ct}_1 \mod{p} $$
Una vez que tenemos $m$, podemos obtener $k$ como sigue
$$ k = \text{pt}_1 - \text{ct}_1 \cdot m^{-1} \mod{p} $$
Y finalmente, hallar la flag:
$$ \text{flag} = k + E(\text{flag}) \cdot m^{-1} \mod{p} $$
Aquí está la implementación de la segunda parte del reto:
io.sendlineafter(b'> ', b'1')
io.recvuntil(b'ct = ')
flag_enc = int(io.recvline().strip())
pt1 = b'a'
io.sendlineafter(b'> ', b'2')
io.sendlineafter(b'pt = ', pt1)
io.recvuntil(b'ct = ')
ct1 = int(io.recvline().strip())
pt2 = b'b'
io.sendlineafter(b'> ', b'2')
io.sendlineafter(b'pt = ', pt2)
io.recvuntil(b'ct = ')
ct2 = int(io.recvline().strip())
io.sendlineafter(b'> ', b'3')
io.close()
m = ct2 - ct1
k = (ord(pt1) - ct1 * pow(m, -1, p)) % p
flag = (k + flag_enc * pow(m, -1, p)) % p
log.success(bytes.fromhex(hex(flag)[2:]).decode())
Flag
$ python3 solve.py 161.35.164.52:32367
[+] Opening connection to 161.35.164.52 on port 32367: Done
[*] Closed connection to 161.35.164.52 port 32367
[+] HTB{C4lcU1u5_m33t5_Cryp70_c4n_y0u_8e1i3ve_17???}
El script completo se puede encontrar aquí: solve.py.