fizzbuzz102

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 $(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 inserted into an LCG ($a \cdot x + b \mod{n}$, with unknown parameters $a$ and $b$) 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 $(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

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 $a$ of the LCG, and then, we will multiply the ciphertext by the inverse of $a$, so that $\mathrm{ct} \to a^{-e} \mathrm{ct} \mod{n}$. Once we have this, we will reuse the solution from fizzbuzz101.

Moreover, we need to assert that both $a$ and $b$ are divisible by $5$. We can do this by sending a $0$ to the oracle, so that the input for FizzBuzz is $b$. If the output is not (Fizz)Buzz, we just close the connection and try again, since both $a$ and $b$ are random integers. Once $b$ is a multiple of $5$, we can send $1$ to the oracle, so that the input to FizzBuzz is $a + b$. Since $b$ is already divisible by $5$, if so is $a$, 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 $k_0$ such that:

$$ a \cdot (k_0 - 1) + b < n < a \cdot k_0 + b $$

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

$$ a \cdot 5(k_0 - 1) + 5b < 5n < a \cdot 5k_0 + 5b $$

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

$$ a \cdot (k_1 - 1) + 5b < 5n < a \cdot k_1 + 5b $$

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

$$ a \cdot (k_r - 1) + 5^r b < 5^r n < a \cdot k_r + 5^r b $$

As a result, it holds that

$$ a \cdot (k_r - 1) < 5^r (n - b) < a \cdot k_r $$

$$ k_r - 1 < \frac{5^r (n - b)}{a} < k_r $$

$$ \frac{1}{k_r} < \frac{a}{5^r (n - b)} < \frac{1}{k_r - 1} $$

$$ \frac{5^r (n - b)}{k_r} < a < \frac{5^r (n - b)}{k_r - 1} $$

Therefore, we have

$$ a \in \left[\frac{5^r (n - b)}{k_r}, \frac{5^r (n - b)}{k_r - 1}\right] $$

Since $k_r$ will be presumably large and $n > b$, we can approximate as follows

$$ a \in \left[\frac{5^r n}{k_r}, \frac{5^r n}{k_r - 1}\right] $$

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

Once having $a$, the approach is the same as in fizzbuzz101, with the difference that the new ciphertext is $\mathrm{ct}’ = a^{-e} \mathrm{ct} \mod{n}$, so that

$$ \begin{align} a \cdot (\mathrm{ct}') ^ d + b \mod{n} & = a \cdot (a^{-e} \mathrm{ct}) ^ d + b \mod{n} \\ & = a \cdot (a^{-1} \mathrm{pt}) + b \mod{n} \\ & = \mathrm{pt} + b \mod{n} \end{align} $$

Since the approach will try to find a value $k_s$ such that

$$ \mathrm{pt} \cdot (k_s - 1) + 5^s b < 5^s n < \mathrm{pt} \cdot k_s + 5^s b $$

Then, we will approximate:

$$ \mathrm{pt} \in \left[\frac{5^s(n - b)}{k_s}, \frac{5^s(n - b)}{k_s - 1}\right] \approx \left[\frac{5^s n}{k_s}, \frac{5^s n}{k_s - 1}\right] $$

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.