Roulette Writeup

Crypto Retired Insane · By sampriti
A casino roulette server backed by a non-standard Mersenne Twister (N=128, M=30, 32-bit words). The wheel produces numbers 0–31, exposing only 5 bits per spin. We instantiate a symbolic clone of the Twister where every state bit is a GF(2) unknown, collect 768 spins (3,840 equations over 4,096 unknowns), solve the binary linear system with Gaussian elimination, reconstruct the full 4,096-bit hidden state, and then predict every future number exactly — turning the 10-times multiplier on exact bets into a 10-trillion-coin jackpot.

Overview

The challenge ships two files: roulette.py (the TCP server) and twister.py (a custom PRNG). The goal is to accumulate 10,000,000,000,000 coins starting from 50. The three betting options are:

  • Option 1 (Even): win/lose your bet — 2x payout, cannot grow fast enough.
  • Option 2 (Odd): same as Even.
  • Option 3 (Exact number): win 10× your bet on a correct guess, lose 10× on a wrong one.

Option 3 is the only route to 10 trillion coins — but a single wrong guess wipes 10× your stake. The only viable strategy is to predict every spin with certainty, which requires recovering the full internal state of the PRNG.

The custom Twister uses parameters N=128, M=30, and 32-bit words — significantly different from the standard MT19937 (N=624, M=397). Each call to rand() applies two XOR-rotate tempering operations and then returns the result modulo 32, revealing only the 5 least-significant bits of a 32-bit value. The hidden state is 128 × 32 = 4,096 bits.

Recon

twister.py — the PRNG

python
N = 128
M = 30
b = 32
MAGIC = 0xb249b015
mask = (1 << b) - 1

class Twister:
    def rol(self, x, d):
        ans = (x << d) & mask
        ans = ans | (x >> (b - d))
        return ans & mask

    def __init__(self, state=None):
        self.index = N
        if state is not None:
            self.STATE = state[:]
        else:
            # server seeds from os.urandom XOR random.getrandbits(32)
            self.STATE = [...]  # 128 random 32-bit words

    def twist(self):
        for i in range(N):
            self.STATE[i] ^= self.rol(self.STATE[(i+1) % N], 3)
            self.STATE[i] ^= self.rol(self.STATE[(i+M) % N], b - 9)
            self.STATE[i] ^= MAGIC

    def rand(self):
        if self.index >= N:
            self.twist()
            self.index = 0
        y = self.STATE[self.index]
        y ^= self.rol(y, 7)
        y ^= self.rol(y, b - 15)
        self.index += 1
        return y & mask

roulette.py — the server

python
money = 50
random = Twister()
while money > 0:
    option = int(self.query("Option: ").strip())
    if option == 3:
        guess = int(self.query("Pick a number: ").strip())
    bet = int(self.query("Bet: ").strip())
    number = random.rand() % 32
    self.write("The wheel stops at {}".format(number))
    if option == 1:
        money += bet if number % 2 == 0 else -bet
    elif option == 3:
        money += bet * 10 if number == guess else -bet * 10
    if money >= 10000000000000:
        self.write("Here's your reward: {}".format(open("flag.txt").read()))
        return

Key observations from reading the source:

  • The server prints the wheel result (number) for every spin, regardless of which option was chosen. We get the true output for free on every bet.
  • number = random.rand() % 32. Since rand() returns a 32-bit value, taking mod 32 (= mod 2⁵) gives exactly the 5 least-significant bits of that value.
  • Each call to twist() updates all 128 state words jointly using neighbours at i+1 and i+M. The tempering in rand() is two XOR-rotate operations applied to a single word before output.

Step 1 — Analyse the Custom Twister

The twist step mixes each word with two neighbours:

text
STATE[i] ^= ROL(STATE[i+1],  3)       # neighbour to the right, rotated 3
STATE[i] ^= ROL(STATE[i+M], 23)       # neighbour M=30 steps ahead, rotated 23
STATE[i] ^= MAGIC                     # constant XOR

The tempering in rand() applies to a single word before output:

text
y = STATE[index]
y ^= ROL(y,  7)
y ^= ROL(y, 17)      # b - 15 = 32 - 15 = 17
output = y & mask    # full 32-bit tempered word
observable = output % 32  # only bits [4:0]

Every operation — XOR, rotation, addition modulo 2 — is linear over GF(2) on the individual bits. This means every output bit is a GF(2) linear combination of the 4,096 initial state bits. The MAGIC constant shifts the affine part but does not break linearity. We can exploit this structure with linear algebra.

The total state is N × b = 128 × 32 = 4,096 bits. Each spin yields 5 equations. We need at least 4,096 linearly independent equations to solve the system, which means at least 820 spins in the ideal case. In practice the matrix may not reach full rank instantly, so we collect 768 spins (3,840 equations) and verify empirically that rank 4,096 is achieved.

Step 2 — Express Outputs as GF(2) Linear Equations

We implement a symbolic Twister — a clone of the real Twister where each state bit is represented not as 0 or 1 but as a symbolic GF(2) variable. Every word is a list of 32 symbolic bits. Each symbolic bit is a pair (mask, const) where mask is a 4,096-bit integer indicating which initial state bits contribute (the linear part), and const is 0 or 1 (the affine constant accumulated from MAGIC XORs).

python
NVARS = N * b   # 4096

def bxor(a, c):
    return (a[0] ^ c[0], a[1] ^ c[1])

def make_word_vars(i):
    # word i: 32 fresh variables, one per bit
    return [((1 << (i * b + k)), 0) for k in range(b)]

def make_const_word(v):
    # a fixed constant word (for MAGIC)
    return [(0, (v >> k) & 1) for k in range(b)]

def rol_word(W, d):
    # rotation is a permutation of the bit list — purely structural
    return [W[(k - d) % b] for k in range(b)]

def xor_word(A, B):
    return [bxor(A[k], B[k]) for k in range(b)]

The SymTwister class mirrors the real Twister exactly, except every arithmetic operation propagates symbolic expressions:

python
class SymTwister:
    def __init__(self):
        self.index = N
        self.STATE = [make_word_vars(i) for i in range(N)]
        self.MAGICW = make_const_word(MAGIC)

    def twist(self):
        for i in range(N):
            self.STATE[i] = xor_word(self.STATE[i], rol_word(self.STATE[(i + 1) % N], 3))
            self.STATE[i] = xor_word(self.STATE[i], rol_word(self.STATE[(i + M) % N], b - 9))
            self.STATE[i] = xor_word(self.STATE[i], self.MAGICW)

    def rand(self):
        if self.index >= N:
            self.twist(); self.index = 0
        y = self.STATE[self.index]
        y = xor_word(y, rol_word(y, 7))
        y = xor_word(y, rol_word(y, b - 15))
        self.index += 1
        return y[:OUTLEN]   # return only the 5 low-order symbolic bits

Calling sym.rand() 768 times yields 3,840 symbolic bits, each describing exactly which linear combination of the 4,096 initial state bits produces that output bit. This precomputation is done once before connecting to the server — it is independent of the secret state.

Step 3 — Collect 768 Observations

We connect to the server and place 768 consecutive bets on option 1 (Even), each for 1 coin. Even/Odd has a 50% chance of winning, so we start with 50 coins and may go broke before 768 rounds. If we go broke, we reconnect and retry — PRNG state resets each session, but the symbolic matrix was precomputed for the first 768 outputs of a fresh Twister, so it matches every new connection.

python
observed = []
for i in range(REQUESTS):        # REQUESTS = 768
    io.sendline(b'1')            # Option: Even
    io.recvuntil(b'Bet: ')
    io.sendline(b'1')            # Bet 1 coin
    line = io.recvline()
    observed.append(int(line.strip().split()[-1]))   # parse "The wheel stops at N"
    data = io.recvuntil(b'Option: ', timeout=20)
    if b'ran out of money' in data:
        raise Broke              # retry

After 768 rounds we have a list of 768 integers in [0, 31]. Each integer contributes 5 bits, giving us 3,840 observed output bits to compare against the 3,840 symbolic equations.

Why bet on Even rather than the exact number? Option 1 reveals the number regardless and only risks 1 coin per round, limiting downside to -1 per loss. Option 3 would cost 10 coins per loss and would drain the 50-coin bankroll in 5 wrong guesses — long before we have enough data to solve the system.

Step 4 — GF(2) Gaussian Elimination

We have 3,840 equations of the form:

text
mask[i] · x  =  rhs[i]     (dot product over GF(2))

where:
  mask[i]  — 4096-bit integer: the linear combination from SymTwister
  x        — 4096-bit unknown state vector
  rhs[i]   — observed output bit XOR the affine constant from SymTwister

The solver performs incremental row-reduction into a pivot basis, then back-substitutes to recover all 4,096 state bits. Free variables (not determined by the observations) are set to 0 — this works because full rank is achieved with 768 observations in practice.

python
def solve_gf2(masks, rhs, ncols):
    COEFF = (1 << ncols) - 1
    basis = {}
    for mask, r in zip(masks, rhs):
        cur = mask | (r << ncols)       # augmented row: [mask | rhs_bit]
        while True:
            coeff = cur & COEFF
            if coeff == 0:
                break
            c = (coeff & -coeff).bit_length() - 1   # lowest set bit = pivot column
            if c in basis:
                cur ^= basis[c]         # eliminate using existing pivot
            else:
                basis[c] = cur          # new pivot row
                break
    # back-substitution
    sol = [0] * ncols
    for c in sorted(basis, reverse=True):
        row = basis[c]
        val = (row >> ncols) & 1
        cc = (row & COEFF) & ~(1 << c)
        while cc:
            j = (cc & -cc).bit_length() - 1
            val ^= sol[j]
            cc &= cc - 1
        sol[c] = val
    return sol

The augmented representation packs the coefficient mask and the RHS bit into a single Python integer, keeping the inner loop to pure XOR operations on arbitrary-precision integers — fast enough to run in well under a minute for a 3,840 × 4,096 system.

After recovering the 4,096 solution bits we reconstruct the 128 32-bit state words:

python
state = []
for i in range(N):
    w = 0
    for k in range(b):
        w |= sol[i * b + k] << k
    state.append(w)

Step 5 — Sync and Predict

We instantiate a real Twister with the recovered state and replay the 768 observed outputs to advance its index to exactly where the server's PRNG currently sits:

python
t = Twister(state)
# verify: every replayed output matches what the server sent us
ok = all((t.rand() % 32) == observed[i] for i in range(REQUESTS))
assert ok, "state recovery failed — retry"
# t.index is now at the same position as the server's PRNG
# every subsequent t.rand() % 32 predicts the server's next output

If verification fails (indicating that the system did not reach full rank, or a connection anomaly caused a mismatch), we reconnect and repeat the observation phase. In practice this almost never happens.

Step 6 — Win the Game

With the PRNG synced we switch to option 3 (exact number). Each correct guess multiplies the bet by 10. The strategy is to bet the entire current bankroll each round:

text
Round 0: 50 coins  → bet 1   (conservative first bet to confirm sync)
Round 1: money     → bet all → money × 10
Round 2:           → bet all → money × 10
...
After 14 correct:  50 × 10^14 = 5 × 10^15  ≫  10^13 threshold
python
money = None
for rnd in range(40):
    pred = t.rand() % 32
    io.sendline(b'3')
    io.recvuntil(b'number: ')
    io.sendline(str(pred).encode())
    io.recvuntil(b'Bet: ')
    io.sendline(b'1' if money is None else str(money).encode())
    line = io.recvline()
    rest = io.recvuntil([b'Option: ', b'reward', b'Congrats'], timeout=20)
    blob = (line + rest).decode(errors='replace')
    if 'Congrats' in blob or 'reward' in blob:
        blob += io.recvall(timeout=10).decode(errors='replace')
        m = re.search(r'HTB\{[^}]+\}', blob)
        print('[+] FLAG:', m.group(0))
        return
    mm = re.search(r'You have (\d+) coins', blob)
    if mm:
        money = int(mm.group(1))
The first exact bet after sync uses only 1 coin as a safety guard — if for any reason the state is off by one (e.g. an extra hidden server spin we did not observe), we lose only 10 coins and the script can detect the desync before going all-in. In practice the prediction is always correct from the first guess.

Full Exploit Script

python · solve.py
#!/usr/bin/env python3
# Roulette (HTB Crypto, Insane) - pure-python GF(2) state recovery of a simplified Mersenne Twister
import sys, re, os
from pwn import remote, context

context.log_level = 'warn'

N, M, b = 128, 30, 32
MAGIC = 0xb249b015
MASK32 = (1 << b) - 1
NVARS = N * b          # 4096
OUTLEN = 5
REQUESTS = 768         # 768*5 = 3840 = needed rank

# ---------- real twister (python3 port) ----------
class Twister:
    def __init__(self, state):
        self.index = N
        self.STATE = list(state)
    def rol(self, x, d):
        return ((x << d) & MASK32) | (x >> (b - d))
    def twist(self):
        for i in range(N):
            self.STATE[i] ^= self.rol(self.STATE[(i + 1) % N], 3)
            self.STATE[i] ^= self.rol(self.STATE[(i + M) % N], b - 9)
            self.STATE[i] ^= MAGIC
    def rand(self):
        if self.index >= N:
            self.twist(); self.index = 0
        y = self.STATE[self.index]
        y ^= self.rol(y, 7)
        y ^= self.rol(y, b - 15)
        self.index += 1
        return y & MASK32

# ---------- symbolic twister over GF(2) : a "bit" = (mask:int, const:0/1) ----------
def bxor(a, c): return (a[0] ^ c[0], a[1] ^ c[1])
def make_word_vars(i): return [((1 << (i * b + k)), 0) for k in range(b)]
def make_const_word(v): return [(0, (v >> k) & 1) for k in range(b)]
def rol_word(W, d): return [W[(k - d) % b] for k in range(b)]
def xor_word(A, B): return [bxor(A[k], B[k]) for k in range(b)]

class SymTwister:
    def __init__(self):
        self.index = N
        self.STATE = [make_word_vars(i) for i in range(N)]
        self.MAGICW = make_const_word(MAGIC)
    def twist(self):
        for i in range(N):
            self.STATE[i] = xor_word(self.STATE[i], rol_word(self.STATE[(i + 1) % N], 3))
            self.STATE[i] = xor_word(self.STATE[i], rol_word(self.STATE[(i + M) % N], b - 9))
            self.STATE[i] = xor_word(self.STATE[i], self.MAGICW)
    def rand(self):
        if self.index >= N:
            self.twist(); self.index = 0
        y = self.STATE[self.index]
        y = xor_word(y, rol_word(y, 7))
        y = xor_word(y, rol_word(y, b - 15))
        self.index += 1
        return y[:OUTLEN]

def precompute_rows():
    st = SymTwister()
    rows = []
    for _ in range(REQUESTS):
        rows.extend(st.rand())
    return [m for m, c in rows], [c for m, c in rows]   # masks, consts

# ---------- GF(2) solver (incremental basis + back-substitution) ----------
def solve_gf2(masks, rhs, ncols):
    COEFF = (1 << ncols) - 1
    basis = {}
    for mask, r in zip(masks, rhs):
        cur = mask | (r << ncols)
        while True:
            coeff = cur & COEFF
            if coeff == 0:
                break
            c = (coeff & -coeff).bit_length() - 1
            if c in basis:
                cur ^= basis[c]
            else:
                basis[c] = cur
                break
    sol = [0] * ncols
    for c in sorted(basis, reverse=True):
        row = basis[c]
        val = (row >> ncols) & 1
        cc = (row & COEFF) & ~(1 << c)
        while cc:
            j = (cc & -cc).bit_length() - 1
            val ^= sol[j]
            cc &= cc - 1
        sol[c] = val
    return sol

def recover_state(masks, consts, observed):
    rhs = []
    for num in observed:
        for k in range(OUTLEN):
            rhs.append((num >> k) & 1)
    rhs = [r ^ c for r, c in zip(rhs, consts)]
    sol = solve_gf2(masks, rhs, NVARS)
    state = []
    for i in range(N):
        w = 0
        for k in range(b):
            w |= sol[i * b + k] << k
        state.append(w)
    return state

def selftest():
    import random
    print('[*] selftest: precompute symbolic...')
    masks, consts = precompute_rows()
    secret = [random.getrandbits(32) for _ in range(N)]
    ref = Twister(secret)
    observed = [ref.rand() % 32 for _ in range(REQUESTS)]
    print('[*] selftest: solving...')
    state = recover_state(masks, consts, observed)
    t = Twister(state)
    ok = all((t.rand() % 32) == observed[i] for i in range(REQUESTS))
    print('[*] replay matches observed:', ok)
    nxt_true = [ref.rand() % 32 for _ in range(20)]
    nxt_pred = [t.rand() % 32 for _ in range(20)]
    print('[*] future prediction matches:', nxt_true == nxt_pred)
    return ok and nxt_true == nxt_pred

def exploit(host, port):
    print('[*] precompute symbolic A...')
    masks, consts = precompute_rows()
    print('[*] done. connecting %s:%d' % (host, port))
    attempt = 0
    while True:
        attempt += 1
        print('[*] attempt %d' % attempt)
        io = remote(host, port, timeout=20)
        io.recvuntil(b'Option: ')
        observed = []
        ruined = False
        try:
            for i in range(REQUESTS):
                io.sendline(b'1')
                io.recvuntil(b'Bet: ')
                io.sendline(b'1')
                line = io.recvline()
                observed.append(int(line.strip().split()[-1]))
                data = io.recvuntil(b'Option: ', timeout=20)
                if b'ran out of money' in data or b'coins' not in data:
                    print('[!] ruined at round %d, retry' % i); ruined = True; break
        except (EOFError, ConnectionResetError):
            print('[!] connection dropped at round %d (likely ruin), retry' % len(observed))
            ruined = True
        if ruined:
            io.close(); continue

        print('[*] solving GF(2) (%d eqns / %d vars)...' % (len(masks), NVARS))
        state = recover_state(masks, consts, observed)
        t = Twister(state)
        ok = all((t.rand() % 32) == observed[i] for i in range(REQUESTS))
        print('[*] verification:', ok)
        if not ok:
            io.close(); continue

        money = None
        for rnd in range(40):
            pred = t.rand() % 32
            io.sendline(b'3')
            io.recvuntil(b'number: ')
            io.sendline(str(pred).encode())
            io.recvuntil(b'Bet: ')
            io.sendline(b'1' if money is None else str(money).encode())
            line = io.recvline()
            rest = io.recvuntil([b'Option: ', b'reward', b'Congrats'], timeout=20)
            blob = (line + rest).decode(errors='replace')
            if 'Congrats' in blob or 'reward' in blob:
                blob += io.recvall(timeout=10).decode(errors='replace')
                m = re.search(r'HTB\{[^}]+\}', blob)
                print(blob[-400:])
                if m:
                    print('[+] FLAG:', m.group(0))
                    open('flag.txt', 'w').write(m.group(0) + '\n')
                io.close(); return m.group(0) if m else None
            mm = re.search(r'You have (\d+) coins', blob)
            if mm: money = int(mm.group(1))
        io.close()
        print('[!] loop ended without flag'); return None

if __name__ == '__main__':
    if len(sys.argv) > 1 and sys.argv[1] == 'selftest':
        sys.exit(0 if selftest() else 1)
    host = sys.argv[1] if len(sys.argv) > 1 else '127.0.0.1'
    port = int(sys.argv[2]) if len(sys.argv) > 2 else 31337
    exploit(host, port)

Flag

HTB{Y0u_c4n_n0w_br43k_m3rs3nn3_tw1st3r_!!!!}