fizzbuzz101

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 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 ). 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 and the ciphertext . We will try to find . These are the relevant RSA equations:

Where .

Solution

We will be focusing on . Notice that we can multiply both sides by an integer, let’s say 2:

Then, we can enter the 2 inside the power as follows because :

So, if we send to the oracle, the oracle will get 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 so that the result is the plaintext times a power of .

The thing is that, since is odd (a product of two prime numbers) and is even, there are two possibilities depending on the result:

• Even (LSB = 0): This means that is even, which means that 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 is odd, which means that (we can say that the value of wraps around )

With this approach, we can bound the value of 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 , of , of 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 (specifically, we are interested in plaintexts that end in , in decimal format). This is because is odd, and it cannot end in because is not divisible by . Therefore, we can easily find an integer such that and .

When sending values to the oracle, we can confirm that holds because the server will respond with Buzz (or FizzBuzz). Once the result wraps around , we won’t have Buzz anymore, since:

Therefore, we have:

Since is a multiple of and is not, then is not a multiple of (no Buzz).

With this approach, we can find such value (let’s say ) and bound the plaintext:

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 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 such that , so it is true that . If we set and test with the oracle, we won’t get Buzz until we reach this situation:

Now, both and are divisible by , therefore too. We can use this wrap-around indication to get another value such that . The outcome is that the interval is shorter:

We can continue the same procedure with powers of 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 , if the server does not respond Buzz to 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 = 1

while True:
    k *= 2
    if oracle(k):
        break

left, right = binary_search(k // 2, k)

As can be seen, we test powers of until the result wraps around and then we apply binary search to delimit a bit the interval and find the value . 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 times (the server sends Buzz when the result wraps around ). 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.