# 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, 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)
```

```
4564874
```

```
# 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)
```

```
2429
```

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

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

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