Junior.Crypt.2025 CTF - PPC - Randomized Flag

flag: `grodno{4eed30575fdec77ad787fe33143569f0e03}`

We are given the source code:

from random import  getrandbits

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

for i in range(2**64):
    print(getrandbits(32) + flag[getrandbits(32) % len(flag)])
    a = input()  # 1 - I known flag, else - next number
    if a == '1':
        ans = input('Flag is: ')
        if ans == flag.decode():
            print (f"Your flag: {flag}")
            break

First of all, the last few lines look a little weird (comparing flags and then printing the same flag again). It turns out that the code running on the server is slightly different. We have to recover a "temporary" flag (different each time we connect), send it (after choosing option 1) and finally receive the "real" flag. Both flags have the same format so it can be misleading (intentionally or not).

In order to recover the flag ("temporary" flag), we need to known exact generated pseudo-random numbers. At each iteration two numbers are generated. We basically know nothing about the second number but we partially know the first one. We don't know all of its bits because one of the flag characters is added each time. Still, we know some of it's most significant bits (how many exactly depends on the number of zeroes preceding last 7 bits).

random.getrandbits() method is supplied with the Mersenne Twister pseudorandom number generator. There's a tool that allows to recover its state (and generate next numbers) based on partially known 32-bit numbers:

https://github.com/icemonster/symbolic_mersenne_cracker/blob/main/main.py

If we don't supply enough input, the correct state won't be recovered and future predictions won't be accurate. If we supply too much input, Z3 won't be able to solve the problem in reasonable time. In our case we have number pairs where one number has (on average) 9 uknown bits and another number has all 32 bits uknown. After some testing I found out that submitting 6000 numbers (3000 pairs) recovers the generator's state in a few minutes.

Because of the issue mentioned at the beginning, we have to keep the connection open and send the recovered flag to get the "real" flag.

import pwn

# https://github.com/icemonster/symbolic_mersenne_cracker/blob/main/main.py
from cracker import Untwister


HOST = "ctf.mf.grsu.by"
PORT = 9048

conn = pwn.remote(HOST, PORT)


conn.recvuntil(b"found ...\n")
conn.recvline()
conn.recvline()


# COLLECT DATA
DATA_SIZE = 5000
data = []

# for some reason sending/receiving in bulk doesn't work very well
for i in range(DATA_SIZE):
    if i % 1000 == 0:
        print(f"{i} / {DATA_SIZE}")
    conn.sendline(b"0")
    resp = conn.recvline().strip()
    if resp:
        data.append(int(resp))


# CALCULATE PREDICTIONS
def n_to_bits(n):
    b = bin(n)[2:].zfill(32)

    known_end = 0
    for i in range(32 - 7):
        if b[i] == "1":
            known_end = i

    res = b[:known_end].ljust(32, "?")
    return res


SAMPLE_SIZE = 3000
OBF_SIZE = DATA_SIZE - SAMPLE_SIZE
PRED_SIZE = 2 * OBF_SIZE

untwister = Untwister()

for n in data[:SAMPLE_SIZE]:
    b = n_to_bits(n)
    untwister.submit(b)
    untwister.submit("?" * 32)

gen = untwister.get_random()
predictions = [gen.getrandbits(32) for _ in range(PRED_SIZE)]


# RECOVER TEMPORARY FLAG
def recover_flag(flag_len, rand_nums, obf_nums):
    assert len(rand_nums) == 2 * len(obf_nums)
    arr = bytearray(flag_len)

    for _ in range(len(obf_nums)):
        r1 = rand_nums.pop(0)
        r2 = rand_nums.pop(0)
        obf = obf_nums.pop(0)

        idx = r2 % flag_len
        val = obf - r1
        arr[idx] = val

    return bytes(arr)


for flag_len in range(8, 100):
    rand_nums = predictions.copy()
    obf_nums = data[SAMPLE_SIZE : SAMPLE_SIZE + len(rand_nums) // 2]

    flag = recover_flag(flag_len, rand_nums, obf_nums)
    if flag.startswith(b"grodno{"):
        print(flag)


# SUBMIT TEMPORARY FLAG MANUALLY
conn.sendline(b"1")
conn.interactive()

flag: grodno{4eed30575fdec77ad787fe33143569f0e03}

flag: `grodno{4eed30575fdec77ad787fe33143569f0e03}`