Quadratic Points
7 minutos de lectura
Se nos proporciona el código fuente del servidor en Python:
from Crypto.Util.number import getPrime, bytes_to_long
from secret import FLAG
from utils import EllipticCurve, find_valid_quadratic_coefficients
import sys
import signal
def get_input_with_timeout(prompt, timeout):
def alarm_handler(signum, frame):
print("\nTime limit exceeded. Exiting...")
sys.exit()
signal.signal(signal.SIGALRM, alarm_handler)
signal.alarm(timeout)
try:
input_data = input(prompt).strip()
return int(input_data)
except KeyboardInterrupt:
pass
finally:
signal.alarm(0) # Disable the alarm
return None
for i in range(7):
x1, x2 = find_valid_quadratic_coefficients()
print(f'Hello Cryptographer, please enter the coefficients of the quadratic equation to proceed, hint: a*x^2 + b*x + c == 0, x = {x1}\n')
ai = get_input_with_timeout("a: ", 2)
bi = get_input_with_timeout("b: ", 2)
ci = get_input_with_timeout("c: ", 2)
res = ai * x1 ** 2 + bi * x1 + ci
res *= 10 ** 13 # did you think I would be that careless?
if int(res) != 0 or any(i == 0 or abs(i) > 60 for i in [ai, bi, ci]):
print("Nope!")
exit()
print("You passed the first test, now onto the second\n")
p = getPrime(40)
E = EllipticCurve(p, [bi, ci])
G = E.random_point()
flag = bytes_to_long(FLAG)
Gn = E.mul(flag, G)
print(f"G = {G.xy()}")
print(f"Gn = {Gn.xy()}")
print(f"p = {E.p}")
Análisis del código fuente
En primer lugar, el servidor nos pide que encontremos los coeficientes de un polinomio cuadrático con una raíz dada (7 veces):
for i in range(7):
x1, x2 = find_valid_quadratic_coefficients()
print(f'Hello Cryptographer, please enter the coefficients of the quadratic equation to proceed, hint: a*x^2 + b*x + c == 0, x = {x1}\n')
ai = get_input_with_timeout("a: ", 2)
bi = get_input_with_timeout("b: ", 2)
ci = get_input_with_timeout("c: ", 2)
res = ai * x1 ** 2 + bi * x1 + ci
res *= 10 ** 13 # did you think I would be that careless?
if int(res) != 0 or any(i == 0 or abs(i) > 60 for i in [ai, bi, ci]):
print("Nope!")
exit()
No conocemos la funcion find_valid_quadratic_coefficients, pero podemos suponer que calcula un polinomio cuadrático aleatorio y devuelve las raíces como x1 y x2.
Una vez que pasamos las primeras 7 preguntas, pasamos al siguiente código donde el servidor usa la flag:
print("You passed the first test, now onto the second\n")
p = getPrime(40)
E = EllipticCurve(p, [bi, ci])
G = E.random_point()
flag = bytes_to_long(FLAG)
Gn = E.mul(flag, G)
print(f"G = {G.xy()}")
print(f"Gn = {Gn.xy()}")
print(f"p = {E.p}")
Aquí, necesitaremos resolver un problema de logaritmo discreto de curva elíptica, que no será difícil ya que el primo p es un entero de 40 bits. Pero lo veremos más adelante.
Primera parte
Entonces, en términos matemáticos, nos dan $x_1$, y debemos encontrar los coeficientes $a$, $b$ y $c$ tales que:
$$ a x_1^2 + b x_1 + c = 0 $$
Además, obsérvese que $a$, $b$ y $c$ son enteros, ya que get_input_with_timeout se transforma a int:
def get_input_with_timeout(prompt, timeout):
def alarm_handler(signum, frame):
print("\nTime limit exceeded. Exiting...")
sys.exit()
signal.signal(signal.SIGALRM, alarm_handler)
signal.alarm(timeout)
try:
input_data = input(prompt).strip()
return int(input_data)
except KeyboardInterrupt:
pass
finally:
signal.alarm(0) # Disable the alarm
return None
Relaciones lineales enteras
Para cada pregunta, tenemos una sola ecuación y tres incógnitas. No hay una forma directa de resolver esto. Sin embargo, podemos usar un retículo. Por ejemplo,
$$ M = \begin{pmatrix} x^2 & x & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}; \qquad M \cdot \begin{pmatrix} a \\ b \\ c \\ \end{pmatrix} = \begin{pmatrix} 0 \\ a \\ b \\ c \end{pmatrix} $$
El retículo generado por las columnas de $M$ contiene un vector $(0, a, b, c)$, que se supone que es corto, ya que $0 < |a|, |b|, |c| \leqslant 60$:
if int(res) != 0 or any(i == 0 or abs(i) > 60 for i in [ai, bi, ci]):
print("Nope!")
exit()
Además, podemos aumentar el hecho de que el vector $(0, a, b, c)$ sea corto multiplicando por $10^{13}$, al igual que hace el servidor:
res = ai * x1 ** 2 + bi * x1 + ci
res *= 10 ** 13 # did you think I would be that careless?
Entonces, usaremos la siguiente matriz $M$:
$$ M = \begin{pmatrix} 10^{13} \cdot x^2 & 10^{13} \cdot x & 10^{13} \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} $$
Podremos encontrar el vector $(0, a, b, c)$ haciendo una reducción de la base del retículo con LLL. Este algoritmo generará una base del mismo retículo, pero con vectores cortos, y esperamos que $(0, a, b, c)$ esté en la base del retículo reducido. Se puede encontrar más información sobre esta técnica en:
Implementación
La técnica anterior se puede escribir en Python con algunas funciones de SageMath:
def find_integer_relation(x: float) -> tuple[int, int, int]:
M = Matrix(QQ, [
[x ** 2, x, 1],
[1, 0, 0],
[0, 1, 0],
[0, 0, 1],
])
M[0, :] *= 10 ** 13
L = M.T.LLL()
for row in L.rows():
ai, bi, ci = map(int, row[1:4])
res = ai * x ** 2 + bi * x + ci
res *= 10 ** 13
if int(res) == 0 and all(0 < abs(z) <= 60 for z in [ai, bi, ci]):
return ai, bi, ci
return 0, 0, 0
Observe cómo recorremos las filas de la matriz reducida (SageMath hace LLL por filas) hasta que encontremos una que sea válida para el servidor.
Entonces, repitimos este proceso 7 veces y pasamos a la segunda parte:
Segunda parte
Recordemos esta parte, que es sencilla:
p = getPrime(40)
E = EllipticCurve(p, [bi, ci])
G = E.random_point()
flag = bytes_to_long(FLAG)
Gn = E.mul(flag, G)
print(f"G = {G.xy()}")
print(f"Gn = {Gn.xy()}")
print(f"p = {E.p}")
Entonces, nos dan $G$, $n \cdot G$ y $p$, donde $G$ es un punto en la curva elíptica $E$:
$$ E : y^2 = x^3 + b_i x + c_i \mod{p} $$
Tenga en cuenta que $b_i$ y $c_i$ provienen de la última ronda de la parte anterior.
Por lo tanto, necesitamos resolver un problema de logaritmo discreto de curva elíptica (ECDLP) para encontrar $n$ a partir de $G$ y $n \cdot G$. Necesitamos esto porque $n$ es la flag como valor entero.
Esta vez, el ECDLP es fácil de resolver porque $p$ es un primo de 40 bits, por lo que hay algoritmos como Baby-step Giant-step que terminarán bastante rápido. Sin embargo, el problema es que la flag no es un entero de 40 bits (5 bytes)…
Teorema chino del resto
Aquí debemos aplicar un truco que se usa bastante en competiciones de CTF, y es volver a conectarnos al servidor. Con esto, podemos pasar la primera parte y obtener otra muestra para la flag.
Al final, nuestro objetivo es obtener algo como:
$$ \begin{cases} \mathrm{flag} \equiv n_1 \pmod{o(G_1)} \\ \mathrm{flag} \equiv n_2 \pmod{o(G_2)} \\ \dots\\ \mathrm{flag} \equiv n_k \pmod{o(G_k)} \\ \end{cases} $$
Al resolver un ECDLP, no tenemos $\mathrm{flag}$, sino $n_i = \mathrm{flag} \mod{o(G_i)}$, y el orden de $G_i$ es un número de 40 bits (más o menos). Por lo tanto, necesitamos obtener más muestras con diferentes puntos.
Como resultado, podremos unir todos los resultados utilizando el Teorema chino del resto (CRT) y encontrar $\mathrm{flag}$ finalmente. Tendremos que asegurarnos de que todos los órdenes $o(G_i)$ sean coprimos.
Para implementarlo, podemos definir una función para conectarnos al servidor, pasar la primera parte y luego resolver el ECDLP. Devolveremos los valores $n_i $ y $o(G_i)$:
def get_flag_order() -> tuple[Integer, Integer]:
io = get_process()
a = b = c = 0
for r in range(7):
round_prog.status(str(r + 1))
io.recvuntil(b'x = ')
x = float(io.recvlineS())
a, b, c = find_integer_relation(x)
if a == b == c == 0:
io.close()
return Integer(0), Integer(0)
io.sendlineafter(b'a: ', str(a).encode())
io.sendlineafter(b'b: ', str(b).encode())
io.sendlineafter(b'c: ', str(c).encode())
io.recvuntil(b'G = ')
Gx, Gy = literal_eval(io.recvlineS())
io.recvuntil(b'Gn = ')
nGx, nGy = literal_eval(io.recvlineS())
io.recvuntil(b'p = ')
p = literal_eval(io.recvlineS())
io.close()
E = EllipticCurve(GF(p), [b, c])
G = E(Gx, Gy)
nG = E(nGx, nGy)
n = nG.log(G)
order = G.order()
return n, order
A continuación, recolectamos todas las muestras y seguimos calculando el CRT hasta que obtengamos la flag como HTB{...}:
round_prog = log.progress('Round')
samples_prog = log.progress('Samples')
flag_prog = log.progress('Flag')
flags, orders = [], []
flag = b''
while not flag.startswith(b'HTB{'):
samples_prog.status(str(len(flags)))
try:
f, o = get_flag_order()
except EOFError:
continue
if f == o == 0:
continue
for oo in orders:
if gcd(oo, o) != 1:
break
else:
flags.append(f)
orders.append(o)
n = int(crt(flags, orders))
flag = long_to_bytes(n)
flag_prog.status(str(flag))
flag_prog.success(flag.decode())
Flag
En este punto, podemos obtener la bandera (puede tomar alrededor de 2 minutos):
$ python3 solve.py 94.237.54.45:31855
[\] Round: 7
[0] Samples: 16
[+] Flag: HTB{th1s_h4s_t0_b3_4_l0ng_fl4g_f0r_CRT_purp0s3s___s0rry_1f_th4t_w4s_4nn0y1ng(:}
El script completo se puede encontrar aquí: solve.py.