UofTCTF 2026 - Gambler's Fallacy

Overview

Category: Cryptography / Pseudo-Random Number Generation (PRNG) Objective: The goal is to accumulate a balance of $10,000 to purchase the flag from the shop. Core Mechanism: The server runs a dice game where the result relies on a server_seed generated by Python’s random module.

Code Analysis

We are provided with the source code chall.py. Upon reviewing the DiceGame class, we identify the following critical behaviors:

1. PRNG Initialization

The game initializes by reading a seed from a file named ./serverseed and seeding Python’s random number generator:

1
with open("./serverseed", 'r') as f:
2
    random.seed(f.read())

[!NOTE] Python uses the Mersenne Twister (MT19937) algorithm for its random module. This is a deterministic generator, meaning if you know the internal state, you can predict all future numbers.

2. The Information Leak

Inside the roll_dice function, the server generates a 32-bit integer called server_seed:

1
self.server_seed = random.getrandbits(32)

While the actual “roll” result is derived from a secure HMAC operation using this seed, the code explicitly prints the server_seed back to the user after every round:

1
print(f"Game {i:05}: ... Server-Seed: {self.server_seed}")

3. The Vulnerability

The Mersenne Twister state consists of 624 32-bit integers. The random.getrandbits(32) function outputs a “tempered” version of one of these state integers. Because the server prints the raw 32-bit outputs of the generator, we can:

1. Collect 624 consecutive server_seed outputs.
2. Reverse the “tempering” process (a series of bitwise XORs and shifts) to recover the raw internal state.
3. Clone the state into our local Python script.
4. Predict every future server_seed and, consequently, every future dice roll.

Exploitation Strategy

Phase 1: Data Collection

We need to survive long enough to collect 624 samples. We play the game betting the minimum possible amount to preserve our balance while gathering the data.

• Action: Place minimum bets on high-probability outcomes (e.g., betting the roll will be under 98) to minimize losses.
• Target: Collect 624 instances of Server-Seed.

Phase 2: State Recovery (Untempering)

The Mersenne Twister output function applies the following transformation to a state value $y$:

1. $y := y \oplus ((y \gg 11) \ \& \ \text{mask})$
2. $y := y \oplus ((y \ll 7) \ \& \ \text{mask})$
3. $y := y \oplus ((y \ll 15) \ \& \ \text{mask})$
4. $y := y \oplus (y \gg 18)$

To recover the state, we must apply the inverse operations in reverse order. The solve script implements an untemper function to achieve this.

Phase 3: Prediction & Winning

Once the state is recovered using random.setstate(), our local Python script is synchronized with the server.

1. Generate the next server_seed locally.
2. Pass this seed into a replica of the predict_roll function (copied from chall.py) to calculate the exact dice roll result.
3. Bet the entire balance (“All In”) knowing exactly what the result will be.

1
graph LR
2
    A[Collect 624 Outputs] --> B[Untemper Values]
3
    B --> C[Reconstruct MT State]
4
    C --> D[Sync Local RNG]
5
    D --> E[Predict Next Seed]
6
    E --> F[Calculate Roll & Win]

Solution Script

The following script automates the attack. It uses pwntools for communication and implements the MT19937 untempering logic.

1
from pwn import *
2
import random
3
import hashlib
4
import hmac
5
import re
6

7
# [Untemper function reverses the bitwise operations of MT19937]
8
def untemper(y):
9
    y ^= (y >> 18)
10
    y ^= (y << 15) & 0xEFC60000
11
    t = y
12
    for _ in range(4):
13
        t = y ^ ((t << 7) & 0x9D2C5680)
14
    y = t
15
    t = y
16
    for _ in range(3):
17
        t = y ^ (t >> 11)
18
    y = t
19
    return y
20

21
def clone_mt_state(outputs):
22
    # Recover internal state from 624 outputs
23
    return [untemper(x) for x in outputs[:624]]
24

25
# [Replicates the server's roll logic exactly]
26
def predict_roll(server_seed, client_seed, nonce):
27
    nonce_client_msg = f"{client_seed}-{nonce}".encode()
28
    sig = hmac.new(str(server_seed).encode(), nonce_client_msg, hashlib.sha256).hexdigest()
29
    # ... (logic matches chall.py)
30
    idx = 0
31
    lucky = int(sig[idx*5:idx*5+5], 16)
32
    while lucky >= 1e6:
33
        idx += 1
34
        lucky = int(sig[idx * 5:idx * 5 + 5], 16)
35
        if idx * 5 + 5 > 129:
36
            lucky = 9999
37
            break
38
    return round((lucky % 1e4) * 1e-2)
39

40
def main():
41
    io = remote("34.162.20.138", 5000)
42
    server_seeds = []
43

44
    # --- Phase 1: Collect Seeds ---
45
    log.info("Collecting 624 seeds...")
46
    while len(server_seeds) < 624:
47
        # Play conservative games to keep balance while harvesting data
48
        # ... (sending bet inputs)
49
        data = io.recvuntil(b"Final Balance:").decode()
50
        # Parse seeds from output
51
        seeds_found = re.findall(r'Server-Seed:\s*(\d+)', data)
52
        for seed_str in seeds_found:
53
            server_seeds.append(int(seed_str))
54

55
    # --- Phase 2: Recover State ---
56
    mt_state = clone_mt_state(server_seeds[:624])
57
    random.setstate((3, tuple(mt_state + [624]), None))
58
    log.success("RNG State Recovered!")
59

60
    # --- Phase 3: Profit ---
61
    current_balance = 801.31 # Derived from logs
62
    while current_balance < 10000:
63
        # Predict the NEXT seed locally
64
        pred_seed = random.getrandbits(32)
65
        # Calculate the roll result
66
        pred_roll = predict_roll(pred_seed, "1337awesome", 624 + i)
67

68
        # Bet EVERYTHING on the predicted number
69
        # ... (sending "All in" bet inputs)
70

71
    # --- Phase 4: Buy Flag ---
72
    io.sendline(b"a") # Shop
73
    io.sendline(b"a") # Buy Flag
74
    print(io.recvall().decode())
75

76
if __name__ == "__main__":
77
    main()

Execution Output

The script successfully collected the seeds, synchronized the RNG, and won massive bets to afford the flag.

[*] Phase 1: Collecting 624 server seeds...
[*] Collected 624/624 seeds. Balance: 801.31
[+] State recovered!
[*] Phase 3: Predicting rolls and betting to win...
[*] [3] Predicted roll: 17, seed: 3493270643
[*] Betting 2726.96 with greed 17 (multiplier: 5.82x)
[+] Won! Balance: 2726.96 -> 15880.55
[+] Reached balance: 15880.55!
[*] Phase 4: Buying flag!
[+] FLAG: uoftctf{ez_m3rs3nne_untwisting!!}

Related Challenge

Funnily enough, I actually just wrote a PRNG Mersenne Twister challenge for another CTF recently! If you enjoyed untwisting the RNG in this challenge, you might want to try your hand at RPSLS (Rock Paper Scissors Lizard Spock).

You can check it out here: https://tcp.1pc.tf/games/22/challenges#494-RPSLS