CUSTOMMediumCrypto

Gambler's Fallacy

XESXOR9/10/20265 min read

#crypto#custom#medium#mt19937_state_recovery#prng_prediction#seed_bruteforce

Gambler's Fallacy

Platform: uoftctf2026 | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-01-10 | Status: Solved Techniques: mt19937_state_recovery, prng_prediction, seed_bruteforce

Summary

Task: Casino game using Python's random.getrandbits(32) for server seeds, where the flag costs more money than the starting balance. Solution: Collected 624 server seeds to fully recover the Mersenne Twister state using randcrack, predicted the next seed, found a winning client_seed via brute force, then bet with minimal greed for a 49.5x multiplier to buy the flag.

Gambler's Fallacy - UofTCTF 2026

Description

"can we win a zillion dollars tonight? algorithms inspired by primedice" nc 34.162.20.138 5000

A casino game where we need to win enough money to buy the flag.

Analysis

The Vulnerability

The casino uses Python's random.getrandbits(32) to generate server seeds:

 python read-only • copy allowed
def roll_dice(self) -> int:
    self.server_seed = random.getrandbits(32)
    nonce_client_msg = f"{self.client_seed}-{self.nonce}".encode()
    sig = hmac.new(str(self.server_seed).encode(), nonce_client_msg, hashlib.sha256).hexdigest()
    index = 0
    lucky = int(sig[index*5:index*5+5], 16)
    while (lucky >= 1e6):
        index += 1
        lucky = int(sig[index * 5:index * 5 + 5], 16)
        if (index * 5 + 5 > 129):
            lucky = 9999
            break
    return round((lucky % 1e4) * 1e-2)

‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

Critical insight: Python's random module uses Mersenne Twister (MT19937), which can be fully recovered after observing exactly 624 consecutive 32-bit outputs.

Game Mechanics

Roll result determines win/loss based on "greed" parameter
Win condition: roll < greed
Multiplier: 99 / greed (lower greed = higher payout)
Server seed is revealed after each game
Nonce increments with each bet (does NOT reset when changing client_seed!)

Solution

Step 1: Collect 624 Server Seeds

‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

Play 624 games with high greed (98) to minimize losses while collecting server_seed values:

 python read-only • copy allowed
import socket
import re

def recv_until(sock, marker):
    data = b""
    while marker not in data:
        data += sock.recv(1)
    return data.decode()

sock = socket.socket()
sock.connect(("34.162.20.138", 5000))

collected_seeds = []
for i in range(624):
    recv_until(sock, "> ")
    sock.send(b"1\n")  # Play
    recv_until(sock, "> ")
    sock.send(b"1\n")  # Bet $1
    recv_until(sock, "> ")
    sock.send(b"98\n")  # High greed (safe)
    
    response = recv_until(sock, "menu")
    match = re.search(r"server_seed: (\d+)", response)
    if match:
        collected_seeds.append(int(match.group(1)))
    print(f"Collected {len(collected_seeds)}/624 seeds")

‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

Step 2: Recover MT19937 State

Use randcrack library to recover the full internal state:

 python read-only • copy allowed
from randcrack import RandCrack

rc = RandCrack()
for seed in collected_seeds[:624]:
    rc.submit(seed)

# Now we can predict future outputs!
next_server_seed = rc.predict_getrandbits(32)
print(f"Predicted next server_seed: {next_server_seed}")

Step 3: Find Winning Client Seed

Critical: After 624 games, nonce=624. We must find a client_seed that produces roll<=1 for THIS nonce:

 python read-only • copy allowed
import hmac
import hashlib
‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

def calculate_roll(server_seed, client_seed, nonce):
    nonce_client_msg = f"{client_seed}-{nonce}".encode()
    sig = hmac.new(str(server_seed).encode(), nonce_client_msg, hashlib.sha256).hexdigest()
    index = 0
    lucky = int(sig[index*5:index*5+5], 16)
    while (lucky >= 1e6):
        index += 1
        lucky = int(sig[index * 5:index * 5 + 5], 16)
        if (index * 5 + 5 > 129):
            lucky = 9999
            break
    return round((lucky % 1e4) * 1e-2)

def find_winning_seed(server_seed, nonce, target_roll=1):
    for i in range(100000):
        client_seed = str(i)
        roll = calculate_roll(server_seed, client_seed, nonce)
        if roll <= target_roll:
            return client_seed, roll
    return None, None
‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

# Find winning seed for nonce=624
winning_seed, roll = find_winning_seed(next_server_seed, 624, target_roll=1)
print(f"Winning client_seed: {winning_seed}, predicted roll: {roll}")
# Example: "64" gives roll=1

Step 4: Execute the Attack

 python read-only • copy allowed
# Set the winning client seed
recv_until(sock, "> ")
sock.send(b"2\n")  # Change client seed
recv_until(sock, "> ")
sock.send(f"{winning_seed}\n".encode())

# Bet everything with greed=2 (multiplier = 99/2 = 49.5x)
recv_until(sock, "> ")
sock.send(b"1\n")  # Play
recv_until(sock, "> ")
sock.send(b"800\n")  # Bet remaining balance (~$800)
recv_until(sock, "> ")
sock.send(b"2\n")  # Greed=2 for 49.5x multiplier
‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

response = recv_until(sock, "menu")
print(response)
# Balance: $39,665

# Buy the flag
recv_until(sock, "> ")
sock.send(b"3\n")  # Buy flag
print(recv_until(sock, "}"))

Full Exploit

 python read-only • copy allowed
#!/usr/bin/env python3
import socket
import re
import hmac
import hashlib
from randcrack import RandCrack

def recv_until(sock, marker):
    data = b""
    while marker.encode() not in data:
        data += sock.recv(1)
    return data.decode()

def calculate_roll(server_seed, client_seed, nonce):
    nonce_client_msg = f"{client_seed}-{nonce}".encode()
    sig = hmac.new(str(server_seed).encode(), nonce_client_msg, hashlib.sha256).hexdigest()
    index = 0
    lucky = int(sig[index*5:index*5+5], 16)
    while (lucky >= 1e6):
        index += 1
        lucky = int(sig[index * 5:index * 5 + 5], 16)
        if (index * 5 + 5 > 129):
            lucky = 9999
            break
    return round((lucky % 1e4) * 1e-2)
‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

def find_winning_seed(server_seed, nonce, target_roll=1):
    for i in range(100000):
        client_seed = str(i)
        roll = calculate_roll(server_seed, client_seed, nonce)
        if roll <= target_roll:
            return client_seed, roll
    return None, None

# Connect
sock = socket.socket()
sock.connect(("34.162.20.138", 5000))

# Phase 1: Collect 624 seeds
print("[*] Collecting 624 server seeds...")
collected_seeds = []
for i in range(624):
    recv_until(sock, "> ")
    sock.send(b"1\n")
    recv_until(sock, "> ")
    sock.send(b"1\n")
    recv_until(sock, "> ")
    sock.send(b"98\n")
    
    response = recv_until(sock, "menu")
    match = re.search(r"server_seed: (\d+)", response)
    if match:
        collected_seeds.append(int(match.group(1)))
    if (i + 1) % 100 == 0:
        print(f"[*] Progress: {i+1}/624")
‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

# Phase 2: Recover MT state
print("[*] Recovering MT19937 state...")
rc = RandCrack()
for seed in collected_seeds[:624]:
    rc.submit(seed)

next_server_seed = rc.predict_getrandbits(32)
print(f"[+] Predicted next server_seed: {next_server_seed}")

# Phase 3: Find winning client seed for nonce=624
print("[*] Finding winning client seed...")
winning_seed, roll = find_winning_seed(next_server_seed, 624, target_roll=1)
print(f"[+] Winning client_seed: {winning_seed}, predicted roll: {roll}")

# Phase 4: Set client seed and win big
recv_until(sock, "> ")
sock.send(b"2\n")
recv_until(sock, "> ")
sock.send(f"{winning_seed}\n".encode())
‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

recv_until(sock, "> ")
sock.send(b"1\n")
recv_until(sock, "> ")
sock.send(b"800\n")  # Bet remaining balance
recv_until(sock, "> ")
sock.send(b"2\n")    # Greed=2 for 49.5x multiplier

response = recv_until(sock, "menu")
print(f"[+] Result: {response}")

# Phase 5: Buy flag
recv_until(sock, "> ")
sock.send(b"3\n")
flag = recv_until(sock, "}")
print(f"[+] FLAG: {flag}")

sock.close()

Key Lessons

Mersenne Twister is NOT cryptographically secure - after 624 outputs, the entire state can be recovered
Nonce handling matters - the nonce didn't reset when changing client_seed, which was crucial for the attack
randcrack library - essential tool for MT19937 state recovery attacks
Greed optimization - using high greed (98) during collection phase minimizes losses while gathering data ‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

References

Mersenne Twister Wikipedia
randcrack - Python MT19937 predictor
Primedice provably fair system ‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍