fizzbuzz100

3 minutes to read

We are given the Python source code that is running on a server:

#!/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)

Source code analysis

The server uses a classic RSA cryptosystem to encrypt the flag padded with 16 random bytes in both sides. We are given the public key $(n, e)$ and the ciphertext.

After that, we have the chance to send arbitrary numbers to the server, and it will try to decrypt them with RSA (using the private exponent $d$). The result will be used to play FizzBuzz.

Notice that if the decryption result is not a multiple of $3$ nor $5$, then the result is printed out. This is important to solve the challenge. Moreover, we cannot simply send the ciphertext to get the initial plaintext, because the server will close the connection.

In summary, we have $(n, e)$ and the ciphertext $\mathrm{ct}$. We will try to find $\mathrm{pt}$. These are the relevant RSA equations:

$$ \mathrm{ct} = m ^ e \mod{n} \iff \mathrm{pt} = \mathrm{ct} ^ d \mod{n} $$

Where $d = e ^ {-1} \mod{\phi(n)}$.

Solution

We will be focusing on $m = c ^ d \mod{n}$. Notice that we can multiply both sides by an integer, let’s say $2$:

$$ 2 \cdot \mathrm{pt} = 2 \cdot \mathrm{ct} ^ d \mod{n} $$

Then, we can enter the $2$ inside the power as follows because $ed \equiv 1 \pmod{\phi(n)}$:

$$ 2 \cdot \mathrm{pt} = (2 ^ e \cdot \mathrm{ct}) ^ d \mod{n} $$

So, if we send $2 ^ e \cdot \mathrm{ct}$ to the oracle, we will get $2 \cdot \mathrm{pt}$ (if it is not a divisible of $3$ or $5$, a bit of trial an error is required, or a different multiplier).

Implementation

Take RSA parameters:

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

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

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

Send it to the oracle:

> 99086625619852540936623635556230012463079813834865380884904299029472685839028830059513275539238051771877418421071073700669634899190573413111482453027987312740551870182126250298908070949136898840226450522847280369296877910983192456553821603543001501276095227829671286875791612752168166070157392972060686516980  
1699667029836895248652842019127582898809421425420846344305753366288950848560443796504597286090139689791336990960624583041186613837259329404644307699057011847530830577456252005671313989276639770557657048506178233207770150454513019754986114698939483077793367329785304876232974584786

Find the plaintext:

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

Flag

Finally, we have the 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}'