fizzbuzz100

3 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 = pt
    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.

Hay que tener en cuenta que si el resultado del descifrado no es un múltiplo de $3$ ni de $5$, entonces se imprime el resultado. Esto es importante para resolver el reto. Además, no podemos simplemente enviar el texto cifrado para obtener el texto claro inicial, porque el servidor cerrará la conexió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

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, obtendremos $2 \cdot \mathrm{pt}$ (si no es divisible entre $3$ o $5$, se necesita un poco de prueba y error o bien un multiplicador diferente).

Implementación

Cogemos los parámetros de RSA:

$ nc be.ax 31100
n = 107432142704969729744681646088424665830363610221256241911041373621960381994092238362511743491677049632323784596987597872854647506578521917344521091001359300181119285202742393276403440957674469413157823891825672605105534917578925758306480100078939844118667754624407335645378506618398412572104582794260547727717  
e = 65537
ct = 42513001833106485723220491153031625854284147241850691946392955522242933333026708844897369989687670696998224322574942238203212443980335591607624800577671264024044958153360776750066089455322767428260171873012630408405582911179993429521235971964387194840778810331150397731209912930842481543053060407302507592880
>

Calculamos $2 ^ e \cdot \mathrm{ct} \mod{n}$:

$ python3 -q
>>> n = 107432142704969729744681646088424665830363610221256241911041373621960381994092238362511743491677049632323784596987597872854647506578521917344521091001359300181119285202742393276403440957674469413157823891825672605105534917578925758306480100078939844118667754624407335645378506618398412572104582794260547727717  
>>> e = 65537
>>> ct = 42513001833106485723220491153031625854284147241850691946392955522242933333026708844897369989687670696998224322574942238203212443980335591607624800577671264024044958153360776750066089455322767428260171873012630408405582911179993429521235971964387194840778810331150397731209912930842481543053060407302507592880
>>> pow(2, e, n) * ct % n
99086625619852540936623635556230012463079813834865380884904299029472685839028830059513275539238051771877418421071073700669634899190573413111482453027987312740551870182126250298908070949136898840226450522847280369296877910983192456553821603543001501276095227829671286875791612752168166070157392972060686516980

Lo mandamos al oráculo:

> 99086625619852540936623635556230012463079813834865380884904299029472685839028830059513275539238051771877418421071073700669634899190573413111482453027987312740551870182126250298908070949136898840226450522847280369296877910983192456553821603543001501276095227829671286875791612752168166070157392972060686516980  
1699667029836895248652842019127582898809421425420846344305753366288950848560443796504597286090139689791336990960624583041186613837259329404644307699057011847530830577456252005671313989276639770557657048506178233207770150454513019754986114698939483077793367329785304876232974584786

Encontramos el texto claro:

>>> pt = 1699667029836895248652842019127582898809421425420846344305753366288950848560443796504597286090139689791336990960624583041186613837259329404644307699057011847530830577456252005671313989276639770557657048506178233207770150454513019754986114698939483077793367329785304876232974584786 // 2  
>>> ct == pow(pt, e, n)
True

Flag

Finalmente, tenemos la flag:

>>> from Crypto.Util.number import long_to_bytes
>>> long_to_bytes(pt)[16:-16]
b'corctf{h4ng_0n_th15_1s_3v3n_34s13r_th4n_4n_LSB_0r4cl3...4nyw4y_1snt_f1zzbuzz_s0_fun}'