ImaginaryCTF rrng

Imaginary CTF 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 is 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 in to 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.

It is reasonable to check for cycles in the generated seeds, especially since 10**100 >> 2**24. A repeating seed leads to a cycle. A reasonably large 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. Still amounting to 48 MiB. so let’s check for a smaller cycle.

# 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
import random
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 == 4564874:
        break
FIRST_SEED_INDEX = i
print(FIRST_SEED_INDEX)

This is promising. A cycle starts at 2429. The cycle can’t start at the beginning, besides having 0 in there breaking the calculation, we find 4564874 as the start of the cycle. Let us therefore check the length of the cycle or the next few, just for sanity checking. This is just the difference between occurrences of FIRST_SEED_VALUE.

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

for i, j, _ in zip(yield_seq_len(skip=1), yield_seq_len(), 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 need to calculate the product of the part of before the first seed value, then we can replace most loop iterations in the middle with an exponentiation, for that we could manually implement Square-and-Multiply, but pythons exp function is already pretty fast and conveniently takes a modulus as its third argument. Third, we calculate the remaining elements with standard iterations. Knowing that the iterations are in the low thousands, easy to do.

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, random.getrandbits(24) is the correct second to last seed value.

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