Calibrator
6 minutos de lectura
Se nos proporciona una instancia remota a la que conectarnos:
$ nc 165.227.224.40 31139
[OK] Memory check
[OK] Syncing filesystem
[OK] Detecting sensors
[OK] Module loader
[OK] Reading configurations
Inititing calibration process ...
┌──────────────────────────────────────────────────────────────────────┐
│┼───────────────────┼────────────────────────┼┼──────────────────────┼│
││ XenoCal 2000 │ . ││ ││
│┼───────────────────┤ ┌─┐ x││ . . ││
││ Iteration: 42 │ x ► └─┘ ││ x ││
│┼─────────┬─────────┤ ││ ││
││ X:1337 │ Y:65189 │ . x ┌───┼┼───┐ ││
│┼─────────┴─────────┘ x ┌─┘ ││ └─┐ x ││
││ . ┌─┘ ││ └─┐ ││
││ ┌─┐ x ▼ ┌┘ . ││ └┐ x ││
││ └─┘ . ┌┘ ││ └┐ ││
││ . │ ││ . │ ││
│┼──────────────────────────────────┼─────────┼┼─────────┼────────────┼│
││ x │ x ││ │ ▼ ││
││ x ──►x └┐ ││ ┌┘ ││
││ . ▼ └┐ ││ ┌┘ . ││
││ . └─┐ ││ ┌─┘ ││
││ ┌─┐ x └─┐ ││ ┌─┘ x ││
││ └─┘ ┌─┐ ┌─┐ └───┼┼───┘ ││
││ └─┘ └─┘ ││ ││
││ x . . ││ . ││
││ . x ││ x ││
││ x ▼ x . ││ x ││
││ ││ ││
│┼────────────────────────────────────────────┼┼──────────────────────┼│
└──────────────────────────────────────────────────────────────────────┘ ┌─
│
┌─┬───────────────────────────┬─┐ ┌──────┐ ┌───┼┐
│ │┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼│ │ │[=()=]│ ├────┤
│ │┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼│ │ ┌──┼──────┼──┐ │ │
│ │┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼│ │ │◄├┼┼┼┼┼┼┼┼┤►│ │ │
│ │┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼│ │ └──┼──────┼──┘ ├────┤
└─┴───────────────────────────┴─┘ │[=()=]│ └────┘
└──────┘
Iteration 0:
>
Análisis de código fuente
Y también tenemos el código fuente en Python:
from FLAG import flag
import random
import math
import time
ITERATIONS = 47
SIDE_LENGTH = 2 * 10 ** 9
ATTEMPTS = 300
HI = SIDE_LENGTH // 2
LO = -SIDE_LENGTH // 2
def banner():
banner = """
┌──────────────────────────────────────────────────────────────────────┐
│┼───────────────────┼────────────────────────┼┼──────────────────────┼│
││ XenoCal 2000 │ . ││ ││
│┼───────────────────┤ ┌─┐ x││ . . ││
││ Iteration: 42 │ x ► └─┘ ││ x ││
│┼─────────┬─────────┤ ││ ││
││ X:1337 │ Y:65189 │ . x ┌───┼┼───┐ ││
│┼─────────┴─────────┘ x ┌─┘ ││ └─┐ x ││
││ . ┌─┘ ││ └─┐ ││
││ ┌─┐ x ▼ ┌┘ . ││ └┐ x ││
││ └─┘ . ┌┘ ││ └┐ ││
││ . │ ││ . │ ││
│┼──────────────────────────────────┼─────────┼┼─────────┼────────────┼│
││ x │ x ││ │ ▼ ││
││ x ──►x └┐ ││ ┌┘ ││
││ . ▼ └┐ ││ ┌┘ . ││
││ . └─┐ ││ ┌─┘ ││
││ ┌─┐ x └─┐ ││ ┌─┘ x ││
││ └─┘ ┌─┐ ┌─┐ └───┼┼───┘ ││
││ └─┘ └─┘ ││ ││
││ x . . ││ . ││
││ . x ││ x ││
││ x ▼ x . ││ x ││
││ ││ ││
│┼────────────────────────────────────────────┼┼──────────────────────┼│
└──────────────────────────────────────────────────────────────────────┘ ┌─
│
┌─┬───────────────────────────┬─┐ ┌──────┐ ┌───┼┐
│ │┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼│ │ │[=()=]│ ├────┤
│ │┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼│ │ ┌──┼──────┼──┐ │ │
│ │┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼│ │ │◄├┼┼┼┼┼┼┼┼┤►│ │ │
│ │┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼│ │ └──┼──────┼──┘ ├────┤
└─┴───────────────────────────┴─┘ │[=()=]│ └────┘
└──────┘
"""
print(banner)
def load():
boot_messages = \
"""
[\033[92mOK\033[0m] Memory check
[\033[92mOK\033[0m] Syncing filesystem
[\033[92mOK\033[0m] Detecting sensors
[\033[92mOK\033[0m] Module loader
[\033[92mOK\033[0m] Reading configurations
Inititing calibration process ...
""".split('\n')
for m in boot_messages:
print(m)
time.sleep(random.random())
# Calibrator's error acceptance threshold
e = 2
if __name__ == '__main__':
load()
banner()
for i in range(ITERATIONS):
print(f"Iteration {i}:")
R = random.randint(SIDE_LENGTH // 4, SIDE_LENGTH // 2)
X = random.randint(LO + R, HI - R)
Y = random.randint(LO + R, HI - R)
for a in range(ATTEMPTS):
line = input("> ")
x, y = [int(n) for n in line.split(' ')]
D = math.sqrt((X - x) ** 2 + (Y - y) ** 2)
if D <= e:
print("\033[94mREFERENCE", end="\n\033[0m")
break
elif D <= R:
print("\033[92mDETECTED", end="\n\033[0m")
else:
print("\033[91mUNDETECTED", end="\n\033[0m")
else:
exit(0)
print(flag)
El reto ejecuta 47 iteraciones, y en cada iteración, se nos dan 300 intentos de ingresar un punto $(x, y)$. No sabía que existía la sintaxis for-else en Python. El bloque else se ejecuta cuando el bucle for termina (más información en www.w3schools.com), pero no si sale con un break.
Entonces, mirando nuevamente el código de reto, debemos entrar en la declaración if donde D <= e, para que se ejecute break y el servidor no llame a exit(0).
Dibujando el problema
En cada iteración, debemos introducir en un punto $(x, y)$. El servidor ha calculado un punto aleatorio $(X, Y)$ y un radio aleatorio $R$ (dentro de un rango definido por variables LO, HI y SIDE_LENGTH).
Para pasar la iteración, debemos calcular un punto $(x, y)$ tal que $D = \sqrt{(X - x)^2 + (Y - y)^2} \leqslant 2$. Si la distancia euclídea es $2 < D \leqslant R$, el servidor responde DETECTED. Y si $D > R$, entonces nuestro punto $(x, y)$ es UNDETECTED.
La siguiente figura muestra todas estas secciones:
Tenga en cuenta que no conocemos ninguno valor de $X, Y, R$. Solo tenemos un oráculo que dice DETECTED, UNDETECTED para encontrar de alguna manera un punto $(x, y)$ que resulte en REFERENCE.
Búsqueda binaria
Como solo tenemos 300 intentos, debemos encontrar un algoritmo de búsqueda rápido que nos permita encontrar un punto REFERENCE. Ya que tenemos un oráculo “binario” (DETECTED o UNDETECTED), intentaremos encontrar una manera de aplicar búsqueda binaria.
El objetivo es encontrar $X$ e $Y$. Lo haremos usando búsqueda binaria cuatro veces. La primera será usando un punto $(x, 0)$ (desde 0 hasta HI), de forma que $D = \sqrt{(X - x)^2 + Y^2}$. El resultado de esta búsqueda binaria será un valor $x_1$ tal que $R = \sqrt{(X - x_1)^2 + Y^2}$. Visualmente, el punto objetivo $(x_1, 0)$ estará en el eje horizontal a la derecha del punto $(X, Y)$.
Entonces, haremos otra búsqueda binaria en el punto $(x, 0)$ (pero con un rango diferente, desde LO hasta 0), tal que $R = \sqrt{(X - x_2)^2 + Y^2}$. Visualmente, el punto objetivo $(x_2, 0)$ estará en el eje horizontal a la izquierda del punto $(X, Y)$.
Análogamente, los otros dos algoritmos de búsqueda binaria generarán $y_1$ e $y_2$ tales que $R = \sqrt{X^2 + (Y - y_1)^2} = \sqrt{X^2 + (Y - y_2)^2}$.
Por lo tanto, podemos construir este sistema de ecuaciones:
$$ \begin{cases} X^2 - 2 X x_1 + x_1^2 + Y^2 = R^2 \\ X^2 - 2 X x_2 + x_2^2 + Y^2 = R^2 \\ X^2 + Y^2 - 2 Y y_1 + y_1^2 = R^2 \\ X^2 + Y^2 - 2 Y y_2 + y_2^2 = R^2 \\ \end{cases} $$
Restando las dos primeras ecuaciones y las dos últimas, tenemos este sistema de ecuaciones reducido:
$$ \begin{cases} 2 X x_1 - 2 X x_2 + x_2^2 - x_1^2 = 0 \\ 2 Y y_1 - 2 Y y_2 + y_2^2 - y_1^2 = 0 \\ \end{cases} $$
Entonces, podemos despejar $X$ e $Y$ de la siguiente manera:
$$ X = \frac{x_1^2 - x_2^2}{2(x_1 - x_2)} \qquad Y = \frac{y_1^2 - y_2^2}{2(y_1 - y_2)} $$
Una vez que sepamos el punto $(X, Y)$, podemos calcular un punto $(x, y)$ tal que $D = \sqrt{(X - x)^2 + (Y - y)^2} \leqslant 2$ y seguir a la siguiente iteración. Este proceso se repite 47 veces.
Flag
Después de programar el procedimiento anterior, ejecutamos el script y eventualmente encontramos la flag:
$ python3 solve.py 165.227.224.40:31139
[+] Opening connection to 165.227.224.40 on port 31139: Done
[+] Round: Done
[+] HTB{b1n4ry_s34rch_15_und3rr4t3d}
[*] Closed connection to 165.227.224.40 port 31139
El script completo se puede encontrar aquí: solve.py.