fizzbuzz102

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
from secrets import randbits

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)

a = randbits(845)
b = randbits(845)
def lcg(x):
    return (a * x + b) % n

print(f"{n = }")
print(f"{e = }")
print(f"{ct = }")

while True:
    ct = int(input("> "))
    pt = lcg(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 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 ). El resultado se insertará en un LCG (, con parámetros y desconocidos) y la salida se usa para jugar FizzBuzz.

Este reto es diferente de fizzbuzz101 en el LCG:

$ diff fizzbuzz101.py fizzbuzz102.py
4d3
< from secrets import randbits
17,21d15
< a = randbits(845)
< b = randbits(845)
< def lcg(x):
<     return (a * x + b) % n
<
28c22
<     pt = lcg(pow(ct, d, n))
---
>     pt = pow(ct, d, n)

En resumen, tenemos y el texto cifrado . Trataremos de encontrar . Estas son las ecuaciones de RSA relevantes:

Donde .

Solución

La solución a este reto es bastante similar a la de fizzbuzz101. Dado que la salida del descifrado de RSA se envía a un LCG, primero intentaremos obtener el valor del LCG, y luego, multiplicaremos el texto cifrado por el inverso de , de manera que . Una vez que tengamos esto, reutilizaremos la solución de fizzbuzz101.

Además, debemos confirmar que y son divisibles entre . Podemos hacer esto enviando un al oráculo, de modo que la entrada para FizzBuzz sea . Si la salida no es (Fizz)Buzz, simplemente cerramos la conexión y lo intentamos nuevamente, ya que tanto como son enteros aleatorios. Una vez que es un múltiplo de , podemos enviar al oráculo, de modo que la entrada a FizzBuzz es . Como ya es divisible entre , si también lo es, entonces el resultado será (Fizz) Buzz; de lo contrario, tenemos que intentarlo de nuevo.

El concepto anterior es importante porque el oráculo que estamos usando es bastante similar al utilizado en fizzbuzz101. Esta vez, encontraremos un valor tal que:

Este valor se puede encontrar usando búsqueda binaria, como en fizzbuzz101. Entonces, si multiplicamos la ecuación anterior por , tenemos:

Ahora, el objetivo es encontrar un valor tal que:

De nuevo, con búsqueda binaria. Al final, tendremos un valor tal que:

Como resultado, se tiene que

Y por tanto

Dado que será presumiblemente grande y , podemos aproximar de la siguiente manera:

Si todo está bien, habrá un valor único en el intervalo, por lo que estará completamente determinado.

Una vez que tenemos , el enfoque es el mismo que en fizzbuzz101, con la diferencia que el nuevo texto cifrado es , de manera que

Dado que el enfoque intentará encontrar un valor tal que

Luego, aproximaremos

Flag

Esta vez, la solución tarda un poco más en terminar ya que hay dos etapas y además no siempre se encuentran los valores correctos. Si ejecutamos el script, eventualmente obtendremos la flag:

$ while true; do python3 solve.py be.ax 31102 && break; echo; done
[+] Opening connection to be.ax on port 31102: Done
[*] Closed connection to be.ax port 31102
[+] Opening connection to be.ax on port 31102: Done
[*] Closed connection to be.ax port 31102
[+] Opening connection to be.ax on port 31102: Done
[*] Closed connection to be.ax port 31102
[+] Opening connection to be.ax on port 31102: Done
[*] Closed connection to be.ax port 31102
[+] a: 82834200763564793343386679942748533456540246595162529051147778900336510618427370127367787174485915284948438341369216755315839043060242343715585762129988158347628763535110309558309716283913677008851731118530266053306599068386968278002334875031494292676945
[-] Flag: b'\xb79\xb0a}1jI\xca\x10FC\xc3\x99^\x9c\x1cC\x04\xfa\x8b\xb4\x05\xda\xa6\xe0\x9fW\x12\xfa\xbf#\xf5\x91x@\xae\xe3\tP\xe2Is\xdf\x86\x98&\xb2+\xe8O>\xdd[\xca\xe5\x06V_\x92"\xbf\'\xcd\nxH\xbbj\xbc\xd5\x0b\x97\xe3P\x95\x1f\xdcs[\x8b=\xac>\xa2|B]\xba\xc9\xa0$lM\xcd\x1a'
[*] Closed connection to be.ax port 31102

[+] Opening connection to be.ax on port 31102: Done
[*] Closed connection to be.ax port 31102
[+] Opening connection to be.ax on port 31102: Done
[+] a: 214656449744464164517148618544333660810514668740872313049096527413162770526398662515864633479619778476135741616482482114075759019591500595462284223550760511218890281006985312194479007330888158332055050291488361333124215387849479724087611239171283845747790
[+] Flag: b'corctf{fizzbuzz_1s_4_r4th3r_s1lly_f0rm_0f_l34k4g3_d0nt_y0u_th1nk?n0w_w1th_4dd3d_LCG_f0r_fun!}'

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