Roulette
17 minutes to read
We are provided with the server source code in Python:
import socketserver
import signal
from twister import Twister
def handle(self):
signal.alarm(500)
self.write("Welcome to the Casino")
self.write("We are playing roulette today")
money = 50
random = Twister()
self.write("The wheel stops on a number between 0 and 31.")
self.write("\n")
while money > 0:
self.write("You have {} coins".format(money))
self.write("What would you like to bet on:")
self.write("1) Even")
self.write("2) Odd")
self.write("3) Number")
option = int(self.query("Option: ").strip())
if option < 1 or option > 3:
self.write("Invalid Option.")
self.close()
return
if option == 3:
guess = int(self.query("Pick a number: ").strip())
bet = int(self.query("Bet: ").strip())
if bet <= 0 or bet > money:
self.write("Invalid Bet.")
self.close()
return
number = random.rand() % 32
self.write("The wheel stops at {}".format(number))
if option == 1:
if number % 2 == 0:
money += bet
else:
money -= bet
elif option == 2:
if number % 2 == 1:
money += bet
else:
money -= bet
elif option == 3:
if number == guess:
money += bet * 10
else:
money -= bet * 10
if money >= 10000000000000:
self.write("Congrats, you beat the house.")
self.write("Here's your reward: {}".format(open("flag.txt", "rb").read()))
self.close()
return
self.write("You ran out of money. Better luck next time.")
self.close()
class RequestHandler(socketserver.BaseRequestHandler):
handle = handle
def read(self, until='\n'):
out = ''
while not out.endswith(until):
out += self.request.recv(1)
return out[:-len(until)]
def query(self, string=''):
self.write(string, newline=False)
return self.read()
def write(self, string, newline=True):
self.request.sendall(string)
if newline:
self.request.sendall('\n')
def close(self):
self.request.close()
class Server(socketserver.ForkingTCPServer):
allow_reuse_address = True
def handle_error(self, request, client_address):
self.request.close()
port = 31337
server = Server(('0.0.0.0', port), RequestHandler)
server.serve_forever()
The server uses a class called Twister as a pseudo-random number generator (PRNG):
import os
import random
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:
assert len(state) == N
self.STATE = state[:]
else:
self.STATE = [0] * N
for i in range(N):
self.STATE[i] = int(os.urandom(4).encode('hex'), 16)
for i in range(N):
self.STATE[i] ^= random.getrandbits(32)
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
Setup environment
First of all the previous Python code works in Python version 2. In order to fix it to work with Python 3, we will need to modify this sentence from twister.py:
+ self.STATE[i] = int(os.urandom(4).hex(), 16)
- self.STATE[i] = int(os.urandom(4).encode('hex'), 16)
And to make roulette.py work locally, I decided to remove the socket server and just use print and input statements:
import signal
from twister import Twister
def handle():
signal.alarm(500)
print("Welcome to the Casino")
print("We are playing roulette today")
money = 50
random = Twister()
print("The wheel stops on a number between 0 and 31.")
print("\n")
while money > 0:
print("You have {} coins".format(money))
print("What would you like to bet on:")
print("1) Even")
print("2) Odd")
print("3) Number")
option = int(input("Option: ").strip())
if option < 1 or option > 3:
print("Invalid Option.")
exit()
if option == 3:
guess = int(input("Pick a number: ").strip())
bet = int(input("Bet: ").strip())
if bet <= 0 or bet > money:
print("Invalid Bet.")
exit()
number = random.rand() % 32
print("The wheel stops at {}".format(number))
if option == 1:
if number % 2 == 0:
money += bet
else:
money -= bet
elif option == 2:
if number % 2 == 1:
money += bet
else:
money -= bet
elif option == 3:
if number == guess:
money += bet * 10
else:
money -= bet * 10
if money >= 10000000000000:
print("Congrats, you beat the house.")
print("Here's your reward: {}".format(open("flag.txt").read()))
exit()
print("You ran out of money. Better luck next time.")
exit()
handle()
Source code analysis
The server simulates a roulette and gives us the chance to bet. The wheel stops on a number between 0 and 31. We have three options:
$ python3 roulette.py
Welcome to the Casino
We are playing roulette today
The wheel stops on a number between 0 and 31.
You have 50 coins
What would you like to bet on:
1) Even
2) Odd
3) Number
Option:
Then, we are asked what amount of money we want to bet. The server will check if we won or lost the round:
if option == 3:
guess = int(input("Pick a number: ").strip())
bet = int(input("Bet: ").strip())
if bet <= 0 or bet > money:
print("Invalid Bet.")
exit()
number = random.rand() % 32
print("The wheel stops at {}".format(number))
if option == 1:
if number % 2 == 0:
money += bet
else:
money -= bet
elif option == 2:
if number % 2 == 1:
money += bet
else:
money -= bet
elif option == 3:
if number == guess:
money += bet * 10
else:
money -= bet * 10
For option 3, the bet is multiplied by 10, since it is more difficult to guess the exact number (probability of $1/32$) rather than the parity of the number (probability of $1/2$).
We will capture the flag when we reach 10000000000000 coins ($10^{13}$).
As a limitation, there is a timeout of 500 seconds (8 minutes and 20 seconds):
signal.alarm(500)
Therefore, it is not enough to use options 1 and 2 to get the flag, since we will need a lot of rounds. Just to prove it, let’s suppose that we have a way to predict the parity of the number of each round, and we have $C$ coins at round $k$. We will bet the maximum amount of money we have on each round to maximize the results. Let $M_k = C$, then:
$$ \begin{align} M_{k + 1} & = M_k + M_k & = 2 C \\ M_{k + 2} & = M_{k + 1} + M_{k + 1} & = 4 C \\ M_{k + 3} & = M_{k + 2} + M_{k + 2} & = 8 C \\ \dots \\ M_{k + n} & = M_{k + n - 1} + M_{k + n - 1} & = 2^n C \end{align} $$
So, if we set $M_{k + n} = 2^n C = 10^{13}$, then $n = \log_{2}{\frac{10^{13}}{C}}$. So, assumming $C = 1$, we need a total of $n = 44$ to achieve more than $10^{13}$ coins.
Instead, it will be better to use option 3, where the bet is multiplied by $10$:
$$ \begin{align} M_{k + 1} & = M_k + 10 \cdot M_k & = 11 C \\ M_{k + 2} & = M_{k + 1} + 10 \cdot M_{k + 1} & = 121 C \\ M_{k + 3} & = M_{k + 2} + 10 \cdot M_{k + 2} & = 1331 C \\ \dots \\ M_{k + n} & = M_{k + n - 1} + 10 \cdot M_{k + n - 1} & = 11^n C \end{align} $$
Now if $M_{k + n} = 11^n C = 10^{13}$, then $n = \log_{11}{\frac{10^{13}}{C}}$, which results in $n = 13$ for $C = 1$.
Anyways, both of the approaches are feasible. But to implement them, we will need to predict PRNG outputs.
PRNG
The server uses the class Twister as the PRNG:
random = Twister()
For each round, the next step of the PRNG is computed with random.rand, although the result is reduced $\mod{32}$ (that is, we are given the 5 least significant bits of the outputs):
number = random.rand() % 32
print("The wheel stops at {}".format(number))
It doesn’t matter if we win or lose, the result is always shown.
State generation
When the Twister class is instantiated, the STATE attribute is randomly generated:
def __init__(self, state=None):
self.index = N
if state is not None:
assert len(state) == N
self.STATE = state[:]
else:
self.STATE = [0] * N
for i in range(N):
self.STATE[i] = int(os.urandom(4).hex(), 16)
for i in range(N):
self.STATE[i] ^= random.getrandbits(32)
The STATE is composed of 128 values (N = 128), which are 32-bit (4-byte) integers. It uses os.urandom, which is a cryptographycally secure random number generator. The use of random.getrandbits(32) is not relevant, since the STATE is generated only once.
Random outputs
This is the rand method (where b = 32 and mask = 0xffffffff):
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
Let’s forget about the if statement for the moment, the rand method takes a given number from the STATE (at self.index) and performs some binary operations. This is rol (rotate to the left):
def rol(self, x, d):
ans = (x << d) & mask
ans = ans | (x >> (b - d))
return ans & mask
Let’s say $(y_0, y_1, \dots, y_{30}, y_{31})$ are the bits of STATE[self.index] ($y_{31}$ is the most significant bit). In other words,
STATE[self.index] $= \displaystyle\sum_{i = 0}^{31} y_i \cdot 2^i$
Then, self.rol(y, 7) is $(y_{25}, y_{26}, \dots, y_{31}, y_0, y_1, \dots, y_{24})$.
For the sake of simplicity, let’s compute intermediate values:
y = self.STATE[self.index]
r = self.rol(y, 7)
s = y ^ r
t = self.rol(s, b - 15)
u = s ^ t
Now, we can say that $r_i = y_{i + 25}$. Then, we have $s_i = y_i \oplus r_i = y_i \oplus y_{i + 25}$.
After that, $t_i = s_{i + 15} = y_{i + 15} \oplus y_{i + 40}$, which means that $t_i = y_{i + 8} \oplus y_{i + 15}$ since $40 \equiv 8 \pmod{32}$.
Finally, $u_i = s_i \oplus t_i$, which is the same as
$$ u_i = y_i \oplus y_{i + 8} \oplus y_{i + 15} \oplus y_{i + 25} $$
Recall that we are only given the last 5 bits, so we know $(u_0, u_1, u_2, u_3, u_4)$ after each round:
$$ \begin{cases} u_0 & = y_0 \oplus y_8 \oplus y_{15} \oplus y_{25} \\ u_1 & = y_1 \oplus y_9 \oplus y_{16} \oplus y_{26} \\ u_2 & = y_2 \oplus y_{10} \oplus y_{17} \oplus y_{27} \\ u_3 & = y_3 \oplus y_{11} \oplus y_{18} \oplus y_{28} \\ u_4 & = y_4 \oplus y_{12} \oplus y_{19} \oplus y_{29} \end{cases} $$
We can verify that the above expressions are true using Python (loading twister.py):
$ python3 -i twister.py
>>> random = Twister()
>>> random.index = 0
>>>
>>> def bits(n):
... return list(map(int, f'{n:032b}'))[::-1]
...
>>> y = bits(random.STATE[0])
>>> output = random.rand() % 32
>>> u = bits(output)[:5]
>>> for i in range(5):
... print(u[i] == y[i] ^ y[i + 8] ^ y[i + 15] ^ y[i + 25])
...
True
True
True
True
True
>>>
We can perform the same checks for all the 128 values of the state:
$ python3 -i twister.py
>>> random = Twister()
>>> random.index = 0
>>>
>>> def bits(n):
... return list(map(int, f'{n:032b}'))[::-1]
...
>>> for k in range(128):
... y = bits(random.STATE[k])
... output = random.rand() % 32
... u = bits(output)[:5]
... for i in range(5):
... assert u[i] == y[i] ^ y[i + 8] ^ y[i + 15] ^ y[i + 25]
...
>>>
Notice that we are cheating, because we are taking the current value of the state and saving it to the variable y. For the challenge, we aim to recover the variable y from the values of u, which are the values that the server shows in each round.
For each round, we will get 5 equations that involve 20 binary variables (that is, $y_i \in \{0, 1\}$). This means that we can work in $\mathbb{F}_2$, which is the finite field of two elements, where AND is just multiplication and XOR is addition.
Since the state is composed of 128 numbers with 32-bits, we will model the state as a total of 4096 binary variables. Once we complete 128 rounds, we will have a total of 640 equations involving 2560 variables. This is not enough to fully recover the state.
Twister
Moreover, if the PRNG algorithm returned to self.STATE[0] with no modification, the PRNG would have a cycle of 128 rounds, being easily cracked. However, there is a twisting step when self.index equals N (128):
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
Each state value is updated using XOR and self.rol respect to the next state value to the right and the value at 30 positions to the right (M = 30). Then, the result is adjusted with a MAGIC value. We could express the above Python code in mathematical terms to better understand how twist works. However, it is not relevant for solving the challenge, since we will use symbolic computations.
Further, it is very complex to model the twist in mathematical terms, since STATE[98] will be updated depending on STATE[99] and STATE[0] (it wraps around); and this STATE[0] value has been updated within the same twist call, so there are some special cases (from STATE[98] to STATE[127]) that must have been considered if we had written the equations by hand.
The twist method will force all variables to appear at least once in the subsequent equations, so that the system of equations we will be solving has a unique solution.
Moreover, the first call to rand will call twist because self.index = N when the class is instantiated. This does not result in any issue, since we can consider that the initial state appears just after the first call to twist.
At this point, we can say that this Twister class implements some variation of Mersenne Twister, which a PRNG used in Python’s random module, for example.
PRNG model
We already know that the PRNG state can be interpreted as a list of 4096 binary variables. Moreover, all the involved operations are XOR and rotations to the left, which are easily adapted to $\mathbb{F}_2$. We will use SageMath to work with a boolean polynomial in this field:
F = GF(2)
P = BooleanPolynomialRing(names=','.join(f'y{i}' for i in range(N * b)))
Then, we can take the variables of the polynomial and use them to create a variable state:
var_state = []
for k in range(0, N * b, b):
var_state.append([P.gens()[i] for i in range(k, k + b)])
var_twister = VarTwister(var_state)
As can be seen, I am using a VarTwister class, which is just a Twister class that works with binary variables in SageMath:
def bits(n):
return list(map(F, f'{n:032b}'))[::-1]
def xor(a, b):
return [a_i + b_i for a_i, b_i in zip(a, b)]
def rol(x, d):
return x[-d:] + x[:-d]
class VarTwister:
def __init__(self, state):
self.index = 0
assert len(state) == N
self.STATE = state[:]
def twist(self):
for i in range(N):
self.STATE[i] = xor(self.STATE[i], rol(self.STATE[(i + 1) % N], 3))
self.STATE[i] = xor(self.STATE[i], rol(self.STATE[(i + M) % N], b - 9))
self.STATE[i] = xor(self.STATE[i], bits(MAGIC))
def rand(self):
if self.index >= N:
self.twist()
self.index = 0
y = self.STATE[self.index]
y = xor(y, rol(y, 7))
y = xor(y, rol(y, b - 15))
self.index += 1
return y[:b]
Notice that also xor and rol functions have changed a little bit.
At this point, whenever we use var_twister.rand, SageMath will perform all the computations symbolically with the 4096 variables. As a result, we can query for at least 4096 bits from PRNG outputs so that we can match the previous equations with the bits. In the end, we will be solving a system of equations on 4096 binary variables, whose solution is the initial state of the PRNG.
Let’s see if the hand-written equations match with SageMath:
$ sage -q
sage: N = 128
sage: M = 30
sage: b = 32
sage: MAGIC = 0xb249b015
sage:
sage: F = GF(2)
sage: P = BooleanPolynomialRing(names=','.join(f'y{i}' for i in range(N * b)))
sage:
sage: def bits(n):
....: return list(map(F, f'{n:032b}'))[::-1]
....:
sage: def xor(a, b):
....: return [a_i + b_i for a_i, b_i in zip(a, b)]
....:
sage: def rol(x, d):
....: return x[-d:] + x[:-d]
....:
sage: class VarTwister:
....: def __init__(self, state):
....: self.index = 0
....: assert len(state) == N
....: self.STATE = state[:]
....:
....: def twist(self):
....: for i in range(N):
....: self.STATE[i] = xor(self.STATE[i], rol(self.STATE[(i + 1) % N], 3))
....: self.STATE[i] = xor(self.STATE[i], rol(self.STATE[(i + M) % N], b - 9))
....: self.STATE[i] = xor(self.STATE[i], bits(MAGIC))
....:
....: def rand(self):
....: if self.index >= N:
....: self.twist()
....: self.index = 0
....:
....: y = self.STATE[self.index]
....: y = xor(y, rol(y, 7))
....: y = xor(y, rol(y, b - 15))
....: self.index += 1
....: return y[:b]
....:
sage: var_state = []
sage:
sage: for k in range(0, N * b, b):
....: var_state.append([P.gens()[i] for i in range(k, k + b)])
....:
sage: var_twister = VarTwister(var_state)
sage: u = var_twister.rand()
sage:
sage: u[0]
y0 + y8 + y15 + y25
sage: u[1]
y1 + y9 + y16 + y26
sage: u[2]
y2 + y10 + y17 + y27
sage: u[3]
y3 + y11 + y18 + y28
sage: u[4]
y4 + y12 + y19 + y29
Perfect, it is correct!
Solution
We will use this helper function to bet:
EVEN, ODD, NUMBER = 1, 2, 3
def bet(option=ODD, amount=1, number=0):
io.sendlineafter(b'Option: ', str(option).encode())
if option == NUMBER:
io.sendlineafter(b'Pick a number: ', str(number).encode())
io.sendlineafter(b'Bet: ', str(amount).encode())
io.recvuntil(b'The wheel stops at ')
output = int(io.recvline().decode())
data = io.recvline()
if b'You have ' not in data:
return output, target
coins = int(data.decode().split(' ')[2])
return output, coins
Now we need to get at least 4096 equations in order to solve for the 4096 binary variables of the PRNG state. Notice that in each round we get 5 bits and we can model 5 equations. Therefore, we will need $\lceil 4096 / 5 \rceil = 820$ rounds to get enough equations:
outputs = []
equations = []
u_values = []
round_prog = io.progress('Round')
coins_prog = io.progress('Coins')
for r in range(rounds):
round_prog.status(f'{r + 1} / {rounds}')
coins_prog.status(f'{coins}')
y = var_twister.rand()
try:
output, coins = bet()
except EOFError:
coins_prog.failure('0')
io.warning('Try better luck next time')
exit()
outputs.append(output)
u = bits(output)
for i in range(5):
equations.append(y[i])
u_values.append(u[i])
round_prog.success(f'{rounds} / {rounds}')
As can be seen, we are just using var_twister.rand at the same time we get a new output from the PRNG. Then, we append the resulting equation to the equations list and the $u_i$ values to u_values.
Notice that we are using bet(), which defaults to bet for an odd number and only 1 coin. We need to consider the case when we run out of money before completing all the rounds (the try-except block).
Once we have all the necessary values, we can use some SageMath functions to convert all the equations to a coefficient matrix $A$ in $\mathbb{F}_2$ and solve a matrix equation for all the collected bits $u_i$ in u_values:
io.info('Solving matrix equation')
A, _ = Sequence(equations).coefficient_matrix(sparse=False)
S = A.solve_right(vector(F, u_values))
if A * S != vector(F, u_values):
io.failure('Failed to solve matrix equation')
exit()
Once here, and verified that the coefficient matrix $A$ times the resulting state bits $S$ gives the expected result (u_values), we can transform the 4096 bits into 128 values of 32 bits in order to initialize a Twister object:
state = [sum(int(y_i) * 2 ** i for i, y_i in enumerate(S[k:k + b])) for k in range(0, N * b, b)]
io.info('Got possible state bits')
twister = Twister(state)
twister.index = 0
At this point, the PRNG should be initialized at the first seed (after the very initial twist, that’s why we force twister.index = 0). Then, we need to compute as much outputs as we have collected, and assert they match:
for output in outputs:
guess = twister.rand() % 32
if output != guess:
io.failure('Some known guessed output is wrong')
exit()
io.success('Verified all state bits')
With this, we have checked that the PRNG state is suitable to generate all the collected outputs. Plus, since we have used more than 4096 equations, the solution we’ve got is likely to be unique, which means that we have the exact state of the PRNG. This also means that future outputs will match with the server’s PRNG, and we can win the game in a few rounds:
r = 0
while coins < target:
guess = twister.rand() % 32
output, coins = bet(option=NUMBER, amount=coins, number=guess)
if output != guess:
io.failure('Some unknown guessed output is wrong')
exit()
coins_prog.status(f'{coins}')
r += 1
coins_prog.success(f'>= {coins}')
io.success(f'Winning rounds: {r}')
io.success(io.recvline().decode())
With all of these, we can try to solve the challenge locally:
$ echo 'HTB{f4k3_fl4g_f0r_t3st1ng}' > flag.txt
$ python3 solve.py
[+] Starting local process '/usr/bin/python3': pid 817021
[+] Round: 820 / 820
[+] Coins: >= 10000000000000
[*] Solving matrix equation
[*] Got possible state bits
[+] Verified all state bits
[+] Winning rounds: 12
[+] Here's your reward: HTB{f4k3_fl4g_f0r_t3st1ng}
[*] Process '/usr/bin/python3' stopped with exit code 0 (pid 817021)
Awesome, we won! And time is not a constraint, it takes less than 10 seconds.
Flag
Let’s try remotely (it takes around 3 minutes):
$ python3 solve.py 143.110.169.131:32215
[+] Opening connection to 143.110.169.131 on port 32215: Done
[+] Round: 820 / 820
[+] Coins: >= 10000000000000
[*] Solving matrix equation
[*] Got possible state bits
[+] Verified all state bits
[+] Winning rounds: 11
[+] Here's your reward: HTB{Y0u_c4n_n0w_br43k_m3rs3nn3_tw1st3r_!!!!}
[*] Closed connection to 143.110.169.131 port 32215
The full script can be found in here: solve.py.