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 , y debemos encontrar los coeficientes , y tales que:

Además, obsérvese que , y 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,

El retículo generado por las columnas de contiene un vector , que se supone que es corto, ya que :

    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 sea corto multiplicando por , 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 :

Podremos encontrar el vector 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 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 , y , donde es un punto en la curva elíptica :

Tenga en cuenta que y 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 a partir de y . Necesitamos esto porque es la flag como valor entero.

Esta vez, el ECDLP es fácil de resolver porque 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:

Al resolver un ECDLP, no tenemos , sino , y el orden de 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 finalmente. Tendremos que asegurarnos de que todos los órdenes 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 y :

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 flag (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.