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 $(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 insertará en un LCG ($a \cdot x + b \mod{n}$, con parámetros $a$ y $b$ 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 $(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

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 $a$ del LCG, y luego, multiplicaremos el texto cifrado por el inverso de $a$, de manera que $\mathrm{ct} \to a^{-e} \mathrm{ct} \mod{n}$. Una vez que tengamos esto, reutilizaremos la solución de fizzbuzz101.

Además, debemos confirmar que $a$ y $b$ son divisibles entre $5$. Podemos hacer esto enviando un $0$ al oráculo, de modo que la entrada para FizzBuzz sea $b$. Si la salida no es (Fizz)Buzz, simplemente cerramos la conexión y lo intentamos nuevamente, ya que tanto $a$ como $b$ son enteros aleatorios. Una vez que $b$ es un múltiplo de $5$, podemos enviar $1$ al oráculo, de modo que la entrada a FizzBuzz es $a + b$. Como $b$ ya es divisible entre $5$, si $a$ 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 $k_0$ tal que:

$$ a \cdot (k_0 - 1) + b < n < a \cdot k_0 + b $$

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

$$ a \cdot 5(k_0 - 1) + 5b < 5n < a \cdot 5k_0 + 5b $$

Ahora, el objetivo es encontrar un valor $k_1$ tal que:

$$ a \cdot (k_1 - 1) + 5b < 5n < a \cdot k_1 + 5b $$

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

$$ a \cdot (k_r - 1) + 5^r b < 5^r n < a \cdot k_r + 5^r b $$

Como resultado, se tiene que

$$ a \cdot (k_r - 1) < 5^r (n - b) < a \cdot k_r $$

$$ k_r - 1 < \frac{5^r (n - b)}{a} < k_r $$

$$ \frac{1}{k_r} < \frac{a}{5^r (n - b)} < \frac{1}{k_r - 1} $$

$$ \frac{5^r (n - b)}{k_r} < a < \frac{5^r (n - b)}{k_r - 1} $$

Y por tanto

$$ a \in \left[\frac{5^r (n - b)}{k_r}, \frac{5^r (n - b)}{k_r - 1}\right] $$

Dado que $k_r$ será presumiblemente grande y $n > b$, podemos aproximar de la siguiente manera:

$$ a \in \left[\frac{5^r n}{k_r}, \frac{5^r n}{k_r - 1}\right] $$

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

Una vez que tenemos $a$, el enfoque es el mismo que en fizzbuzz101, con la diferencia que el nuevo texto cifrado es $\mathrm{ct}’ = a^{-e} \mathrm{ct} \mod{n}$, de manera que

$$ \begin{align} a \cdot (\mathrm{ct}') ^ d + b \mod{n} & = a \cdot (a^{-e} \mathrm{ct}) ^ d + b \mod{n} \\ & = a \cdot (a^{-1} \mathrm{pt}) + b \mod{n} \\ & = \mathrm{pt} + b \mod{n} \end{align} $$

Dado que el enfoque intentará encontrar un valor $k_s$ tal que

$$ \mathrm{pt} \cdot (k_s - 1) + 5^s b < 5^s n < \mathrm{pt} \cdot k_s + 5^s b $$

Luego, aproximaremos

$$ \mathrm{pt} \in \left[\frac{5^s(n - b)}{k_s}, \frac{5^s(n - b)}{k_s - 1}\right] \approx \left[\frac{5^s n}{k_s}, \frac{5^s n}{k_s - 1}\right] $$

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.