ImaginaryCTF rrng

ImaginaryCTF is not your classical weekend CTF. Instead, they have been publishing fun challenges almost every day since April 2021 – pretty impressive. I’ve been solving some of their challenges here and there. This one, from last month, is especially fun. Also, I wanted to try a Jupyter notebook style write-up. Let me know if this helps comprehension or maybe is too much mixing of code and text.

The challenge states:

rrngg, aka random random number generator generator.

Provided are the encrypted flag in flag.enc and the Python file used to produce it:

#!/usr/bin/env python3
import random
from Crypto.Util.number import long_to_bytes as ltb
from Crypto.Util.strxor import strxor

unintended_solution_yeeter = 1

# getPrime(512) from Crypto.Util.number
prime = 9748729228494339631846388699994098788507701354484040512690379598196693697693937149457269291065421274894121574705508351692344913516332264306279955933193803

random.seed(0)
for i in range(10**100):
	r = random.getrandbits(24)
	unintended_solution_yeeter *= r
	unintended_solution_yeeter %= prime # modulus needs to be prime, cuz otherwise unintended_solution_yeeter (may) be 0
	random.seed(r)

assert unintended_solution_yeeter.bit_length() > 200  # sufficient
random.seed(random.getrandbits(24)*unintended_solution_yeeter)

with open("flag.txt", "rb") as f:
	flag = f.read()

with open("flag.enc", "wb") as f:
	f.write(strxor(flag, ltb(random.getrandbits(len(flag)*8))))

Looking at how the flag is produced, it uses XOR encryption, with random bytes as long as the flag. If the bytes are truly random, it is information-theoretically impossible to recover the flag. Therefore, we need to analyse how to predict the value of the last call to random.getrandbits. Looking at how the last seed is set, there is no secret going into this process. It completely deterministically seeds the random number generator, so re-executing the script (and swapping the files) will yield us the flag. However, the loop makes 10**100 iterations. This is more than there are atoms in the universe, to add myself to the list using this overused comparison. The goal here is to find an optimized calculation of the last seed value.

Each seed is only 24 bits and completely determines the next one, so the sequence of seeds must repeat within at most 2^24 steps – and 10^100 is far larger than that. A repeating seed leads to a cycle. A reasonably small cycle will allow us to compute the product of the cycle only once, and then use fast exponentiation in closed form.

A seed value is 24 bits, which are 3 bytes. In the worst case the cycle is 2^24 long, and storing every seed would take 2^24 · 3 bytes = 48 MiB (far more in a Python set). That is still feasible, but hopefully the cycle is shorter, so let’s find the first repeating seed.

import random

# Define the sequence of seeds starting from the explicitly set seed 0
def yield_seq():
    random.seed(0)
    while True:
        r = random.getrandbits(24)
        random.seed(r)
        yield r

# check for the first seed that appears twice
seen = set()
for r in yield_seq():
    if r in seen:
        break
    seen.add(r)
FIRST_SEED_VALUE = r
print(FIRST_SEED_VALUE)

# check at what index `FIRST_SEED_VALUE` appears first
for i, r in enumerate(yield_seq()):
    if r == FIRST_SEED_VALUE:
        break
FIRST_SEED_INDEX = i
print(FIRST_SEED_INDEX)

This is promising. The sequence has a 2429-element tail before it enters a cycle starting with 4564874 at index 2429. Let us therefore check the length of the first cycle and the next few, as a sanity check. This is just the difference between consecutive occurrences of FIRST_SEED_VALUE.

def yield_seq_starts(skip=0):
    for i, r in enumerate(yield_seq()):
        if r == FIRST_SEED_VALUE:
            if skip > 0:
                skip -= 1
            else:
                yield i

for i, j, _ in zip(yield_seq_starts(skip=1), yield_seq_starts(), range(5)):
    CYCLE_LEN = i - j
    print(CYCLE_LEN)

Now we have everything we need to efficiently calculate the final value. This is done in three parts. First, we calculate the product of everything up to and including the first occurrence of the cycle seed. Second, we replace most loop iterations in the middle with an exponentiation. For that we could manually implement Square-and-Multiply, but Python’s built-in pow function already does this and conveniently takes a modulus as its third argument. Third, we calculate the remaining elements with standard iterations. Since there are only a few thousand of them, this is easy.

prime = 9748729228494339631846388699994098788507701354484040512690379598196693697693937149457269291065421274894121574705508351692344913516332264306279955933193803
# from the chal with adjustable start and length
def seed_product(start_seed: int, length: int):
    random.seed(start_seed)
    product = 1
    for i in range(length):
        r = random.getrandbits(24)
        product *= r
        product %= prime
        random.seed(r)
    return product

cycle_product = seed_product(FIRST_SEED_VALUE, CYCLE_LEN)

prefix_product = seed_product(0, FIRST_SEED_INDEX + 1)
remaining = 10**100 - (FIRST_SEED_INDEX + 1)
main_product = pow(cycle_product, remaining // CYCLE_LEN, prime)
suffix_product = seed_product(FIRST_SEED_VALUE, remaining % CYCLE_LEN)
unintended_solution_yeeter = (prefix_product * main_product * suffix_product) % prime

Now we have the correct last value of unintended_solution_yeeter, and since suffix_product was calculated last, the RNG was last seeded with the final loop value. So the next random.getrandbits(24) returns the same value the challenge used.

random.seed(random.getrandbits(24)*unintended_solution_yeeter)

with open("flag.enc", "rb") as f:
    flag = f.read()

from Crypto.Util.number import long_to_bytes as ltb
from Crypto.Util.strxor import strxor
print(strxor(flag, ltb(random.getrandbits(len(flag)*8))))

b'ictf{cYcl3_CycLE_CYc|3_cYCL3_cYcl3_CycLE_CYc|3_cYCL3_cYcl3_CycLE_CYc|3_cYCL3}'