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, was especially fun. Also I wanted to try a jupyter notebook style write-up. Let me know if this helps comprehension or maybe 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
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)
2153 2153 2153 2153 2153
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))))