fizzbuzz101
7 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 = "101"
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.
This challenge is different from fizzbuzz100 because when the decryption result is not a multiple of 3 nor 5, the result is no longer printed out (just 101):
$ diff fizzbuzz100.py fizzbuzz101.py
31c31
< out = pt
---
> out = "101"
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, the oracle will get $2 \cdot \mathrm{pt}$ and it will play FizzBuzz with that, but it will never show the result.
Intuition
The flag of fizzbuzz100 made me think in a LSB oracle, which can be applied in a situation where the decryption oracle sends back the last bit of the result (that is, even or odd). With this, we can start multiplying the ciphertext by powers of $2 ^ e$ so that the result is the plaintext times a power of $2$.
The thing is that, since $n$ is odd (a product of two prime numbers) and $2 \mathrm{pt}$ is even, there are two possibilities depending on the result:
- Even (LSB = 0): This means that $2 \cdot \mathrm{pt} \mod{n}$ is even, which means that $2 \cdot \mathrm{pt} < n$ and the modulo operator is useless (this is not always true, but it can be forced to be true)
- Odd (LSB = 1): This means that $2 \cdot \mathrm{pt} \mod{n}$ is odd, which means that $2 \cdot \mathrm{pt} > n$ (we can say that the value of $2 \cdot \mathrm{pt}$ wraps around $n$)
With this approach, we can bound the value of $\mathrm{pt}$ using binary seach and eventually find the plaintext.
Adaptation to the challenge
Recall that in this challenge we are told if the decryption result is whether a multiple of $3$, of $5$, of $15$ or nothing. We can use somehow the previous LSB oracle intuition to target this challenge.
Since the padding of the plaintext is random, we can test if the plaintext is a multiple of $5$ (specifically, we are interested in plaintexts that end in $5$, in decimal format). This is because $n$ is odd, and it cannot end in $5$ because $n$ is not divisible by $5$. Therefore, we can easily find an integer $k$ such that $(k - 1) \cdot \mathrm{pt} < n$ and $k \cdot \mathrm{pt} > n$.
When sending values to the oracle, we can confirm that $k \cdot \mathrm{pt} < n$ holds because the server will respond with Buzz (or FizzBuzz). Once the result wraps around $n$, we won’t have Buzz anymore, since:
$$ k \cdot \mathrm{pt} > n \Longrightarrow k \cdot \mathrm{pt} = n + (k \cdot \mathrm{pt} \mod{n}) $$
Therefore, we have:
$$ k \cdot \mathrm{pt} \mod{n} = k \cdot \mathrm{pt} - n $$
Since $k \cdot \mathrm{pt}$ is a multiple of $5$ and $n$ is not, then $k \cdot \mathrm{pt} \mod{n}$ is not a multiple of $5$ (no Buzz).
With this approach, we can find such value $k$ (let’s say $k_0$) and bound the plaintext:
$$ \mathrm{pt} \in \left[\frac{n}{k_0}, \frac{n}{k_0 - 1}\right] $$
At this point, we will get the most significant bits of the plaintext right (around 10 bytes will be correct). From here, we need to continue delimiting the solution.
Remember this part of the LSB oracle explanation above:
… which means that $2 \cdot \mathrm{pt} < n$ and the modulo operator is useless (this is not always true, but it can be forced to be true)
We are going to take advantage of that! We have the value $k_0$ such that $(k_0 - 1) \cdot \mathrm{pt} < n < k_0 \cdot \mathrm{pt}$, so it is true that $5 (k_0 - 1) \cdot \mathrm{pt} < 5n < 5 k_0 \cdot \mathrm{pt}$. If we set $k \in [5 (k_0 - 1), 5 k_0]$ and test $k$ with the oracle, we won’t get Buzz until we reach this situation:
$$ k \cdot \mathrm{pt} > 5 n \Longrightarrow k \cdot \mathrm{pt} = 5 n + (k \cdot \mathrm{pt} \mod{n}) $$
Now, both $k \cdot \mathrm{pt}$ and $5 n$ are divisible by $5$, therefore $k \cdot \mathrm{pt} \mod{n}$ too. We can use this wrap-around indication to get another value $k_1$ such that $(k_1 - 1) \cdot \mathrm{pt} < 5 n < k_1 \cdot \mathrm{pt}$. The outcome is that the interval is shorter:
$$ \mathrm{pt} \in \left[\frac{5n}{k_1}, \frac{5n}{k_1 - 1}\right] $$
We can continue the same procedure with powers of $5$ to delimit the interval until contains the plaintext.
Implementation
Let’s use a simple script in Python and pwntools to solve the challenge. First of all, let’s define the oracle function and connect to the challenge to take the parameters. Also, since we need to confirm that the plaintext is a multiple of $5$, if the server does not respond Buzz to $2 \cdot \mathrm{pt}$ we restart the connection:
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()
Now, we find the value $k_0$:
k = 1
while True:
k *= 2
if oracle(k):
break
left, right = binary_search(k // 2, k)
As can be seen, we test powers of $2$ until the result wraps around $n$ and then we apply binary search to delimit a bit the interval and find the value $k_0$. By the way, this is the binary_search function:
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
There is a reverse option for the second part, where we are testing against powers of $5$ times $n$ (the server sends Buzz when the result wraps around $n$). Now the only thing left to do is more binary search and delimit the interval until we have a single value (the plaintext):
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
If we run the script, we will get the 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}'
The full script can be found in here: solve.py.