fizzbuzz101
7 minutos de lectura
Se nos proporciona el código fuente en Python que se ejecuta en el servidor:
#!/usr/local/bin/python
from Crypto.Util.number import *
from os import urandom
flag = open("flag.txt", "rb").read()
flag = bytes_to_long(urandom(16) + flag + urandom(16))
p = getPrime(512)
q = getPrime(512)
n = p * q
e = 0x10001
d = pow(e, -1, (p-1)*(q-1))
assert flag < n
ct = pow(flag, e, n)
print(f"{n = }")
print(f"{e = }")
print(f"{ct = }")
while True:
ct = int(input("> "))
pt = pow(ct, d, n)
out = ""
if pt == flag:
exit(-1)
if pt % 3 == 0:
out += "Fizz"
if pt % 5 == 0:
out += "Buzz"
if not out:
out = "101"
print(out)
Análisis del código fuente
El servidor utiliza un criptosistema clásico RSA para cifrar la flag rellenada con 16 bytes aleatorios en ambos lados. Se nos proporciona la clave pública $(n, e)$ y el texto cifrado.
Después de eso, tenemos la oportunidad de enviar números arbitrarios al servidor, que intentará descifrarlos con RSA (usando el exponente privado $d$). El resultado se usará para jugar a FizzBuzz.
Este reto es diferente de fizzbuzz100 en que cuando el resultado del descifrado no es un múltiplo de 3 ni 5, el resultado ya no se imprime (solo 101):
$ diff fizzbuzz100.py fizzbuzz101.py
31c31
< out = pt
---
> out = "101"
En resumen, tenemos $(n, e)$ y el texto cifrado $\mathrm{ct}$. Trataremos de encontrar $\mathrm{pt}$. Estas son las ecuaciones de RSA relevantes:
$$ \mathrm{ct} = m ^ e \mod{n} \iff \mathrm{pt} = \mathrm{ct} ^ d \mod{n} $$
Donde $d = e ^ {-1} \mod{\phi(n)}$.
Solución
Nos centraremos en $m = c ^ d \mod{n}$. Obsérvese que podemos multiplicar ambos lados por un entero, digamos $2$:
$$ 2 \cdot \mathrm{pt} = 2 \cdot \mathrm{ct} ^ d \mod{n} $$
Luego, podemos meter el $2$ dentro de la potencia de la siguiente manera, porque $ed \equiv 1 \pmod{\phi(n)}$:
$$ 2 \cdot \mathrm{pt} = (2 ^ e \cdot \mathrm{ct}) ^ d \mod{n} $$
Entonces, si enviamos $2 ^ e \cdot \mathrm{ct}$ al oráculo, este obtendrá $2 \cdot \mathrm{pt}$ y jugará a FizzBuzz con eso, pero nunca mostrará el resultado.
Intuición
La flag de fizzbuzz100 me hizo pensar en un oráculo LSB, que se puede aplicar en una situación en la que el oráculo de descifrado envía el último bit del resultado (es decir, par o impar). Con esto, podemos comenzar a multiplicar el texto cifrado por potencias de de $2 ^ e$ de manera que el resultado sea el texto claro por una potencia de $2$.
La cosa es que, dado que $n$ es impar (un producto de dos números primos) y $2 \mathrm{pt}$ es par, hay dos posibilidades dependiendo del resultado:
- Par (LSB = 0): Esto significa que $2 \cdot \mathrm{pt} \mod{n}$ es par, que implica que $2 \cdot \mathrm{pt} < n$ y el operador módulo es inútil (esto no siempre es cierto, pero se puede forzar a que lo sea por conveniencia)
- Impar (LSB = 1): Esto significa que $2 \cdot \mathrm{pt} \mod{n}$ es impar, que implica que $2 \cdot \mathrm{pt} > n$ (podríamos decir que el valor de $2 \cdot \mathrm{pt}$ da la vuelta sobre $n$)
Con este enfoque, podemos acotar el valor de $\mathrm{pt}$ usando búsqueda binaria y eventualmente encontrar el texto claro.
Adaptación al reto
Recordemos que en este reto se nos dice si el resultado del descifrado es un múltiplo de $3$, de $5$, de $15$ o nada. Podemos usar de alguna manera la intuición del oráculo LSB anterior para enfocar este reto.
Dado que el relleno del texto claro es aleatorio, podemos probar si el texto claro es un múltiplo de $5$ (específicamente, estamos interesados en textos claros que terminen en $5$, en formato decimal). Esto es porque $n$ es impar, y no puede terminar en $5$ porque $n$ no es divisible entre $5$. Por lo tanto, podemos encontrar fácilmente un entero $k$ tal que $(k - 1) \cdot \mathrm{pt} < n$ y $k \cdot \mathrm{pt} > n$.
Al enviar valores al oráculo, podemos confirmar que $k \cdot \mathrm{pt} < n$ se cumple porque el servidor devuelve Buzz (o FizzBuzz). Una vez que el resultado se da la vuelta sobre $n$, no tendremos más Buzz porque:
$$ k \cdot \mathrm{pt} > n \Longrightarrow k \cdot \mathrm{pt} = n + (k \cdot \mathrm{pt} \mod{n}) $$
Entonces, tenemos:
$$ k \cdot \mathrm{pt} \mod{n} = k \cdot \mathrm{pt} - n $$
Como $k \cdot \mathrm{pt}$ es múltiplo de $5$ y $n$ no, se sigue que $k \cdot \mathrm{pt} \mod{n}$ no es múltiplo de $5$ (no Buzz).
Con esta estrategia, podemos encontrar ese valor $k$ (digamos $k_0$) y acotar el texto claro:
$$ \mathrm{pt} \in \left[\frac{n}{k_0}, \frac{n}{k_0 - 1}\right] $$
En este punto, obtendremos los bits más significativos del texto claro (alrededor de 10 bytes serán correctos). Desde aquí, necesitamos continuar acotando la solución.
Recordemos esta parte de la explicación del oráculo LSB de arriba:
… que implica que $2 \cdot \mathrm{pt} < n$ y el operador módulo es inútil (esto no siempre es cierto, pero se puede forzar a que lo sea por conveniencia)
¡Vamos a aprovechar eso! Tenemos el valor de $k_0$ tal que $(k_0 - 1) \cdot \mathrm{pt} < n < k_0 \cdot \mathrm{pt}$, por lo que es cierto que $5 (k_0 - 1) \cdot \mathrm{pt} < 5n < 5 k_0 \cdot \mathrm{pt}$. Si nos establecemos $k \in [5 (k_0 - 1), 5 k_0]$ y probamos $k$ en el oráculo, no obtendremos Buzz hasta alcanzar esta situación:
$$ k \cdot \mathrm{pt} > 5 n \Longrightarrow k \cdot \mathrm{pt} = 5 n + (k \cdot \mathrm{pt} \mod{n}) $$
Ahora ambos $k \cdot \mathrm{pt}$ y $5 n$ son divisibles entre $5$, por lo que $k \cdot \mathrm{pt} \mod{n}$ también. Podemos usar esta indicación de que se ha dado la vuelta para obtener otro valor $k_1$ tal que $(k_1 - 1) \cdot \mathrm{pt} < 5 n < k_1 \cdot \mathrm{pt}$. El resultado es que el intervalo es más corto:
$$ \mathrm{pt} \in \left[\frac{5n}{k_1}, \frac{5n}{k_1 - 1}\right] $$
Podemos continuar el mismo procedimiento con potencias de $5$ para acotar el intervalo hasta que contenga solo el texto claro.
Implementación
Usemos un script simple en Python y pwntools para solucionar el reto. En primer lugar, vamos a definir la función oracle y vamos a coger los parámetros al conectarnos al reto. Además, como tenemos que confirmar que el texto claro es un múltiplo de $5$, si el servidor no responde Buzz a $2 \cdot \mathrm{pt}$ reiniciamos la conexión:
def oracle(x):
io.sendlineafter(b'> ', str(pow(x, e, n) * ct % n).encode())
return b'Buzz' not in io.recvline()
while True:
io = get_process()
io.recvuntil(b'n = ')
n = int(io.recvline().decode())
io.recvuntil(b'e = ')
e = int(io.recvline().decode())
io.recvuntil(b'ct = ')
ct = int(io.recvline().decode())
if not oracle(2):
break
io.close()
Ahora, hallamos el valor de $k_0$:
k = 1
while True:
k *= 2
if oracle(k):
break
left, right = binary_search(k // 2, k)
Como se puede ver, probamos potencias de $2$ hasta que el resultado dé la vuelta sobre $n$ y luego aplicamos una búsqueda binaria para delimitar un poco el intervalo y encontrar el valor de $k_0$. Por cierto, esta es la función binary_search:
def binary_search(left, right, reverse=False):
while left < right - 1:
mid = (left + right) // 2
if oracle(mid) ^ reverse:
right = mid
else:
left = mid
return left, right
Hay una opción reverse para la segunda parte, donde estamos probando contra potencias de $5$ multiplicadas por $n$ (el servidor envía Buzz cuando el resultado da la vuelta sobre alrededor de $n$). Ahora lo único que queda por hacer es hacer más búsquedas binaria y acotar el intervalo hasta que tengamos un valor único (el texto claro):
prog = io.progress('Flag')
for i in range(1, 1000):
left, right = binary_search(5 * left, 5 * right, reverse=True)
prog.status(str(long_to_bytes(5 ** i * n // right)[16:-16]))
Flag
Si ejecutamos el script, obtendremos la flag:
$ python3 solve.py be.ax 31101
[+] Opening connection to be.ax on port 31101: Done
[*] Closed connection to be.ax port 31101
[+] Opening connection to be.ax on port 31101: Done
[*] Closed connection to be.ax port 31101
[+] Opening connection to be.ax on port 31101: Done
[*] Closed connection to be.ax port 31101
[+] Opening connection to be.ax on port 31101: Done
[*] Closed connection to be.ax port 31101
[+] Opening connection to be.ax on port 31101: Done
[*] Closed connection to be.ax port 31101
[+] Opening connection to be.ax on port 31101: Done
[▗] Flag: b'corctf{\'\'.join(fizz_buzz(x) for x in range(99, 102)) == "FizzBuzz101" == cool_username}'
El script completo se puede encontrar aquí: solve.py.