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
Después de eso, tenemos la oportunidad de enviar números arbitrarios al servidor, que intentará descifrarlos con RSA (usando el exponente privado
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
Donde
Solución
Nos centraremos en
Luego, podemos meter el
Entonces, si enviamos
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
La cosa es que, dado que
- Par (LSB = 0): Esto significa que
es par, que implica que 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
es impar, que implica que (podríamos decir que el valor de da la vuelta sobre )
Con este enfoque, podemos acotar el valor de
Adaptación al reto
Recordemos que en este reto se nos dice si el resultado del descifrado es un múltiplo de
Dado que el relleno del texto claro es aleatorio, podemos probar si el texto claro es un múltiplo de
Al enviar valores al oráculo, podemos confirmar que Buzz
(o FizzBuzz
). Una vez que el resultado se da la vuelta sobre Buzz
porque:
Entonces, tenemos:
Como Buzz
).
Con esta estrategia, podemos encontrar ese valor
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
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 Buzz
hasta alcanzar esta situación:
Ahora ambos
Podemos continuar el mismo procedimiento con potencias de
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 Buzz
a
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 = 1
while True:
k *= 2
if oracle(k):
break
left, right = binary_search(k // 2, k)
Como se puede ver, probamos potencias de 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 Buzz
cuando el resultado da la vuelta sobre alrededor de
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
.