Roulette
17 minutos de lectura
Se nos proporciona el código fuente del servidor en 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()
El servidor usa una clase llamada Twister como generador de números pseudo-aleatorios (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
Configuración del entorno
En primer lugar, el código Python anterior funciona en Python versión 2. Para arreglarlo y que funcione con Python 3, necesitaremos modificar esta instrucción de twister.py:
+ self.STATE[i] = int(os.urandom(4).hex(), 16)
- self.STATE[i] = int(os.urandom(4).encode('hex'), 16)
Y para hacer que roulette.py funcione en local, decidí eliminar el servidor de socket y solo usar funciones print e input:
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()
Análisis del código fuente
El servidor simula una ruleta y nos da la oportunidad de apostar. La rueda se detiene en un número entre 0 y 31. Tenemos tres opciones:
$ 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:
Luego, se nos pregunta qué cantidad de dinero queremos apostar. El servidor verificará si ganamos o perdemos la ronda:
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
Para la opción 3, la apuesta se multiplica por 10, ya que es más difícil adivinar el número exacto (probabilidad de $1/32$) que la paridad del número (probabilidad de $1/2$).
Obtendremos la flag cuando lleguemos a 10000000000000 monedas ($10^{13}$).
Como limitación, hay un timeout de 500 segundos (8 minutos y 20 segundos):
signal.alarm(500)
Por lo tanto, no será suficiente usar las opciones 1 y 2 para obtener la flag, ya que necesitaremos muchas rondas. Solo para probarlo, supongamos que tenemos una forma de predecir la paridad del número de cada ronda, y tenemos $C$ monedas en la ronda $k$. Apostaremos la cantidad máxima de dinero que tenemos en cada ronda para maximizar los resultados. Sea $M_k = C$, entonces:
$$ \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} $$
Así, conseguimos que $M_{k + n} = 2^n C = 10^{13}$, luego $n = \log_{2}{\frac{10^{13}}{C}}$. Por tanto, asumiendo $C = 1$, necesitaremos un mínimo de $n = 44$ para obtener más de $10^{13}$ monedas.
En cambio, es mejor usar la opción 3, donde la apuesta se multiplica por $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} $$
Ahora tenemos que $M_{k + n} = 11^n C = 10^{13}$, por lo que $n = \log_{11}{\frac{10^{13}}{C}}$, que resulta en $n = 13$ para $C = 1$.
Bueno. De todos modos, ambos enfoques son factibles. Pero para implementarlos, necesitaremos predecir las salidas del PRNG.
PRNG
El servidor usa la clase Twister como PRNG:
random = Twister()
Para cada ronda, el siguiente paso del PRNG se calcula con random.rand, aunque el resultado se reduce $\mod{32}$ (es decir, se nos dan los 5 bits menos significativos de las salidas):
number = random.rand() % 32
print("The wheel stops at {}".format(number))
No importa si ganamos o perdemos, el resultado siempre se muestra.
Generación del estado
Cuando la clase Twister se instancia, el atributo STATE se genera de forma aleatoria:
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)
El STATE se compone de 128 valores (N = 128), que son enteros de 32 bits (4 bytes). Se emplea os.urandom, que es un generador de números aleatorios criptográficamente seguro. El uso de random.getrandbits(32) no es relevante, ya que el STATE se genera solo una vez.
Salidas aleatorias
Este es el método rand (donde b = 32 y 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
Olvidemos el bloque if de momento, el método rand toma un número determinado del STATE (en self.index) y realiza algunas operaciones binarias. Esto es rol (rotación hacia la izquierda):
def rol(self, x, d):
ans = (x << d) & mask
ans = ans | (x >> (b - d))
return ans & mask
Digamos que $(y_0, y_1, \dots, y_{30}, y_{31})$ son los bits de STATE[self.index] ($y_{31}$ es el bit más significativo). En otras palabras,
STATE[self.index] $= \displaystyle\sum_{i = 0}^{31} y_i \cdot 2^i$
Entonces, self.rol(y, 7) es $(y_{25}, y_{26}, \dots, y_{31}, y_0, y_1, \dots, y_{24})$.
Por razones de simplicidad, calcularemos los valores intermedios:
y = self.STATE[self.index]
r = self.rol(y, 7)
s = y ^ r
t = self.rol(s, b - 15)
u = s ^ t
Ahora podemos decir que $r_i = y_{i + 25}$. Entonces tenemos que $s_i = y_i \oplus r_i = y_i \oplus y_{i + 25}$.
Después, $t_i = s_{i + 15} = y_{i + 15} \oplus y_{i + 40}$, que se traduce en $t_i = y_{i + 8} \oplus y_{i + 15}$ ya que $40 \equiv 8 \pmod{32}$.
Finalmente, $u_i = s_i \oplus t_i$, que es lo mismo que
$$ u_i = y_i \oplus y_{i + 8} \oplus y_{i + 15} \oplus y_{i + 25} $$
Recordemos que solo se nos muestran los últimos 5 bits, por lo que sabemos $(u_0, u_1, u_2, u_3, u_4)$ después de cada ronda:
$$ \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} $$
Podemos verificar que las expresiones anteriores sean correctas usando Python (cargando 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
>>>
Podemos realizar las mismas verificaciones para los 128 valores del estado:
$ 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]
...
>>>
Hay que tener en cuenta que estamos haciendo trampa, porque estamos tomando el valor actual del estado y guardándolo en la variable y. Para resolver el reto, nuestro objetivo es recuperar la variable y a partir de los valores de u, que son los valores que el servidor muestra en cada ronda.
Para cada ronda, obtendremos 5 ecuaciones que involucran 20 variables binarias (es decir, $y_i \in \{0, 1\}$). Esto significa que podemos trabajar en $\mathbb{F}_2$, que es el cuerpo finito de dos elementos, donde AND es la multiplicación y XOR es la suma.
Dado que el estado está compuesto por 128 números de 32 bits, modelaremos el estado como un total de 4096 variables binarias. Una vez que completemos 128 rondas, tendremos un total de 640 ecuaciones que involucran 2560 variables. Esto no es suficiente para recuperar completamente el estado.
Twister
Además, si el algoritmo PRNG regresara a self.STATE[0] sin ninguna modificación, el PRNG tendría un ciclo de 128 rondas, siendo fácilmente comprometido. Sin embargo, hay un paso de twist cuando self.index es igual a 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
Cada valor de estado se actualiza utilizando XOR y self.rol respecto al siguiente valor de estado a la derecha y al valor a 30 posiciones a la derecha (M = 30). Luego, el resultado se ajusta con un valor MAGIC. Podríamos expresar el código de Python anterior en términos matemáticos para comprender mejor cómo funciona el método twist. Sin embargo, no es relevante para resolver el reto, ya que usaremos cálculos simbólicos.
Además, es muy complejo modelar el método twist en términos matemáticos, ya que STATE[98] se actualizará según STATE[99] y STATE[0] (se da la vuelta); y este valor de STATE[0] se actualizó dentro de la misma llamada a twist, por lo que tendremos algunos casos especiales (desde STATE[98] hasta STATE[127]) que deberían ser considerados si se quisieran escribir las ecuaciones a mano.
El método twist obligará a todas las variables a aparecer al menos una vez en las ecuaciones posteriores, de modo que el sistema de ecuaciones que resolveremos tiene una solución única.
Además, la primera llamada a rand llamará a twist porque self.index = N cuando se instancia la clase. Esto no ocasiona problemas, ya que se puede asumir que el estado inicial es el que se obtiene después de esta llamada inicial a twist.
En este punto, podemos decir que esta clase Twister implementa una variante de Mersenne Twister, que es un PRNG usado en el módulo random de Python, por ejemplo.
Modelo del PRNG
Ya sabemos que el estado del PRNG puede interpretarse como una lista de 4096 variables binarias. Además, todas las operaciones involucradas son XOR y rotaciones hacia la izquierda, que se pueden adaptar fácilmente a $\mathbb{F}_2$. Usaremos SageMath para trabajar con un polinomio booleano en este cuerpo:
F = GF(2)
P = BooleanPolynomialRing(names=','.join(f'y{i}' for i in range(N * b)))
Luego, podemos tomar las variables del polinomio y usarlas para crear un estado variable:
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)
Como se puede ver, estoy usando una clase VarTwister, que es solo una clase Twister que funciona con variables binarias en 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]
Obsérvese que también las funciones xor y rol han cambiado un poco.
En este punto, cada vez que usemos var_twister.rand, SageMath realizará todos los cálculos simbólicamente con las 4096 variables. Como resultado, podemos solicitar al menos 4096 bits de salidas del PRNG para que podamos igualar las ecuaciones anteriores con los bits. Al final, resolveremos un sistema de ecuaciones en 4096 variables binarias, cuya solución es el estado inicial del PRNG.
Veamos si las ecuaciones escritas a mano coinciden con las de 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
¡Perfecto, es correcto!
Solución
Usaremos esta función de ayuda para apostar:
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
Ahora necesitamos obtener al menos 4096 ecuaciones para resolver el sistema de 4096 variables binarias del estado del PRNG. Hay que tener en cuenta que en cada ronda obtenemos 5 bits y podemos modelar 5 ecuaciones. Por lo tanto, necesitaremos un mínimo de $\lceil 4096/5 \rceil = 820$ rondas para obtener suficientes ecuaciones:
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}')
Como se puede ver, solo estamos usando var_twister.rand al mismo tiempo que obtenemos una nueva salida del PRNG. Luego, agregamos la ecuación resultante a la lista equations y los valores de $u_i$ en u_values.
Nótese que estamos usando bet(), que por defecto apuesta por un número impar y solo 1 moneda. Necesitamos considerar el caso en el que nos quedamos sin dinero antes de completar todas las rondas (el bloque try-except).
Una vez que tenemos todos los valores necesarios, podemos usar algunas funciones de SageMath para convertir todas las ecuaciones a una matriz de coeficientes $A$ en $\mathbb{F}_2$ y resolver una ecuación matricial para todos los bits $u_i$ recogidos en 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()
Una vez aquí, y habiendo verificado que la matriz de coeficientes $A$ por los bits de estado $S$ dan como resultado el vector u_values, podemos transformar los 4096 bits en 128 valores de 32 bits para inicializar un objeto Twister:
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
En este punto, el PRNG debe inicializarse en la primera semilla (después de primer twist, de ahí que forcemos que twister.index = 0). Luego, necesitamos calcular tantas salidas como hayamos recolectado, y afirmar que coinciden:
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')
Con esto, hemos verificado que el estado del PRNG es adecuado para generar todas las salidas recolectadas. Además, dado que hemos usado más de 4096 ecuaciones, es probable que la solución que tenemos sea única, lo que significa que tenemos el estado exacto del PRNG. Esto también significa que las salidas futuras coincidirán con el PRNG del servidor, y podremos ganar el juego en unas pocas rondas:
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())
Con todo esto, podemos tratar de resolver el reto en local:
$ 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)
¡Impresionante, hemos ganado! Y el tiempo no fue una restricción al final, ha tardado menos de 10 segundos.
Flag
Probemos de en la instancia remota (tarda alrededor de 3 minutos):
$ 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
El script completo se puede encontrar aquí: solve.py.