CER FRUMOS MT19937 state recovery

crypto
flag TFCCTF{ursu_ursa_bea_ursus_intrun_urus_verzuliu}

Overview

The challenge seeds Python's random module with a 128-bit integer, prints 625 partial outputs, then derives an AES-256-CBC key and IV from two later outputs and encrypts the flag. We get out.txt: 625 lines of 48-bit integers plus the hex ciphertext.

python 
1x = random.getrandbits(48)   # 32 + 16 bits from 2 tempered state words
2random.getrandbits(16)       # discarded
3print(x)
4# ... after 625 samples ...
5for _ in range(10):
6    random.getrandbits(32)   # discarded
7key = sha256(str(random.getrandbits(64)).encode()).digest()
8iv  = sha256(str(random.getrandbits(64)).encode()).digest()[:16]

Vulnerability

random is , a 624-word (19968-bit) state that is fully deterministic once known. Each 48-bit sample leaks the entire lower 32 bits of one tempered output plus the top 16 bits of the next. Across 625 samples that is more than 1000 tempered words against a 624-word state, so the state is over-determined several times over.

Insight

Every partial output is a linear constraint on the internal state. Feed enough of them to a solver, or invert the temper and solve the GF(2) recurrence directly. Either recovers the whole state, and with it every later output, including the two words that seed the key and IV.

Solution

Model the 624 state words as symbolic 32-bit bitvectors in , mirroring the twist and temper from CPython's _randommodule.c. A next_word() helper tracks the output index and re-twists on wrap. Then replay the exact call sequence:

python 
1for x in samples:
2    solver.add(next_word() == (x & 0xFFFFFFFF))          # lower 32 bits
3    solver.add(Extract(31, 16, next_word()) == (x >> 32)) # top 16 of next word
4    next_word()                                           # discarded 16-bit call
5
6for _ in range(10):
7    next_word()
8
9key_lo, key_hi = next_word(), next_word()
10iv_lo,  iv_hi  = next_word(), next_word()
11
12assert solver.check() == sat
13model = solver.model()
14key_seed = u32(key_lo) | (u32(key_hi) << 32)
15iv_seed  = u32(iv_lo)  | (u32(iv_hi)  << 32)
16key = sha256(str(key_seed).encode()).digest()
17iv  = sha256(str(iv_seed).encode()).digest()[:16]
18flag = AES.new(key, AES.MODE_CBC, iv=iv).decrypt(enc)
session 
$python3 solve.py
key seed: 4364408293663289775
iv seed:  9427524340023772294
plaintext: TFCCTF{ursu_ursa_bea_ursus_intrun_urus_verzuliu}

Notes

Z3 is overkill here. Given full lower-32-bit words for all 625 samples, inverting the temper function and solving the linear recurrence over GF(2) recovers the state far faster. Either way: never seed AES keys from random, use secrets or os.urandom.

Flag

text 
TFCCTF{ursu_ursa_bea_ursus_intrun_urus_verzuliu}