fizzbuzz102

5 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
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)

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 inserted into an LCG (, with unknown parameters and ) and the output is used to play FizzBuzz.

This challenge is only different from fizzbuzz101 on the 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)

In summary, we have and the ciphertext . We will try to find . These are the relevant RSA equations:

Where .

Solution

The solution to this challenge is pretty similar to the one for fizzbuzz101. Since the output of RSA decryption is sent to an LCG, we will first try to get the value of the LCG, and then, we will multiply the ciphertext by the inverse of , so that . Once we have this, we will reuse the solution from fizzbuzz101.

Moreover, we need to assert that both and are divisible by . We can do this by sending a to the oracle, so that the input for FizzBuzz is . If the output is not (Fizz)Buzz, we just close the connection and try again, since both and are random integers. Once is a multiple of , we can send to the oracle, so that the input to FizzBuzz is . Since is already divisible by , if so is , then the output will be (Fizz)Buzz; otherwise, we need to try again.

The previous fact is important because the oracle we are using is pretty similar to the one used in fizzbuzz101. This time, we will find a value such that:

This value can be found using binary search, as in fizzbuzz101. Then, if we multiply the above equation by , we have:

Now, the aim is to find a value such that:

Again, with binary search. In the end, we will have some value such that:

As a result, it holds that

Therefore, we have

Since will be presumably large and , we can approximate as follows

If everything is nice, there will be a unique value in the interval, so will be fully determined.

Once having , the approach is the same as in fizzbuzz101, with the difference that the new ciphertext is , so that

Since the approach will try to find a value such that

Then, we will approximate:

Flag

This time, the solution takes a bit longer to finish since there are two stages and the correct values are not always found. If we run the script, we will get the flag eventually:

$ 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!}'

The full script can be found in here: solve.py.