Converging Visions

9 minutos de lectura

Se nos proporciona el código fuente del servidor en Python:

from secret import FLAG, p, a, b
from random import randint
from utils import EllipticCurve

class PRNG:

    def __init__(self, p, mul1, mul2):
        self.mod = p * 6089788258325039501929073418355467714844813056959443481824909430411674443639248386564763122373451773381582660411059922334086996696436657009055324008041039  
        self.exp = 2
        self.mul1 = mul1
        self.mul2 = mul2
        self.inc = int.from_bytes(b'Coordinates lost in space', 'big')
        self.seed = randint(2, self.mod - 1)

    def rotate(self):
        self.seed = (self.mul1 * pow(self.seed, 3) + self.mul2 * self.seed +
                     self.inc) % self.mod
        return self.seed, pow(self.seed, self.exp, self.mod)


class Relic:

    def __init__(self, p, a, b):
        self.E = EllipticCurve(p, a, b)
        self.P = None
        self.EP = None
        self.p = p
        self.prng = PRNG(p, a, b)

    def setupPoints(self, x):
        if x >= self.p:
            return 'Coordinate greater than curve modulus'

        try:
            self.P = self.E.get_point(x)
            self.EP = self.P
        except:
            return 'Point not on curve'

        return ('Point confirmed on curve', self.P.x, self.P.y)

    def nextPoints(self):
        seed, enc_seed = self.prng.rotate()
        self.P *= seed
        self.EP *= enc_seed
        return ('New Points', self.EP.x, self.EP.y, self.P.x, self.P.y)


def menu():
    print('Options:\n')
    print('1. Setup Point')
    print('2. Receive new point')
    print('3. Find true point')
    option = input('> ')
    return option


def main():
    artifact = Relic(p, a, b)
    setup = False

    while True:
        try:
            option = menu()
            if option == '1':
                print('Enter x coordinate.')
                x = int(input('x : '))
                response = artifact.setupPoints(x)
                if response[0] == 'Point confirmed on curve':
                    setup = True
                print(response)
            elif option == '2':
                if setup:
                    response = artifact.nextPoints()
                    print('Response')
                    print((response[0], response[1], response[2]))
                else:
                    print('Configure origin point first')
            elif option == '3':
                if setup:
                    print('Input x,y')
                    Px = int(input('x: '))
                    Py = int(input('y: '))
                    response = artifact.nextPoints()
                    if Px == response[3] and Py == response[4]:
                        print(
                            'You have confirmed the location. However, It\'s dangerous to go alone. Take this: ',
                            FLAG)
                    else:
                        print('The vessels will never be found...')
                    exit()
                else:
                    print('Configure origin point first')
            else:
                print("Invalid option, shutting down...")
                exit()
        except Exception as e:
            response = f'An error occured: {e}'
            print(response)
            exit()


if __name__ == '__main__':
    assert p.bit_length() == 256
    main()

El servidor usa Criptografía de Curva Elíptica (ECC) con parámetros secretos (p, a, b). La implementación se encuentra en utils.py. También utiliza un generador de números pseudo-aleatorios (PRNG) personalizado con los mismos parámetros desconocidos y una cierta fórmula.

Contexto de ECC

La Criptografía de Curva Elíptica es un criptosistema de clave pública, por lo que hay una clave pública y una clave privada.

Sea $E$ una curva elíptica definida en forma de Weierstrass:

$$ E: \; y^2 = x^3 + ax + b $$

Donde $(x, y)$ son puntos de la curva.

En ECC, la curva elíptica anterior se considera sobre un cuerpo finito (por ejemplo, $\mathbb{F}_p$, con $p$ un número primo). Por lo tanto, la curva se puede expresar como $E(\mathbb{F}_p)$.

Como resultado, los puntos en la curva forman un grupo abeliano con la suma:

La operación es interna (es decir, $P + Q \in E(\mathbb{F}_p) \; \forall P, Q \in E(\mathbb{F}_p)$)
Hay un único elemento neutro que generalmente se llama $O$, tal que $P + O = O + P = P$. También se conoce como “punto en el infinito”
Todo punto tiene un único inverso, es decir $\exists! Q \in E(\mathbb{F}_p) \;|\; P + Q = O \;\; \forall P \in E(\mathbb{F}_p)$. Se podría decir que $Q = -P$, abusando de la notación aditiva
La operación es asociativa (y también conmutativa)

La operación de la suma tiene un cierto algoritmo, que se implementa en el código fuente anterior. Una vez definida la suma, podemos expresar el producto de un punto por un escalar:

$$ kP = \underbrace{P + \dots + P}_{k\; \text{times}} $$

Para usar ECC, debemos tomar un punto generador $G$ de la curva, luego tomar un número $n$ y multiplicar $n$ por $G$. La clave pública está formada por los puntos $G$ y $nG$ (aparte de los parámetros de la curva $a$, $b$ y el cuerpo finito $\mathbb{F}_p$); y la clave privada es el número $n$.

ECC se puede utilizar para el Protocolo de intercambio de claves Diffie-Hellman (ECDH), para el algoritmo de firma digital (ECDSA) o para cifrado (ECIES), entre otros. La seguridad de este criptosistema recae en la dificultad de resolver el Problema del Logaritmo Discreto de Curva Elíptica (ECDLP), es decir, encontrar $n$ a partir de $G$ y $nG$.

Encontrando los parámetros de la curva

En la opción 1, se nos permite ingresar un número $x$ y el servidor intentará darnos el correspondiente valor $y$ para que el punto $(x, y)$ pertenezca a la curva:

            if option == '1':
                print('Enter x coordinate')
                x = int(input('x : '))
                response = artifact.setupPoints(x)
                if response[0] == 'Point confirmed on curve':  
                    setup = True
                print(response)

Sin embargo, echemos un vistazo al método setupPoints:

    def setupPoints(self, x):
        if x >= self.p:
            return 'Coordinate greater than curve modulus'

        try:
            self.P = self.E.get_point(x)
            self.EP = self.P
        except:
            return 'Point not on curve'

        return ('Point confirmed on curve', self.P.x, self.P.y)

Aquí tenemos un oráculo para encontrar $p$ usando búsqueda binaria, porque podemos probar valores de $x$ y aproximarnos a $p$ dependiendo de la respuesta ('Coordinate greater than curve modulus' vs. otro mensaje). Este es el código para encontrar $p$:

def main():
    io = get_process()

    left, right = 2 ** 16, 2 ** 256
    m = (left + right) // 2

    while left < right - 1:
        m = (left + right) // 2

        io.sendlineafter(b'> ', b'1')
        io.sendlineafter(b'x : ', str(m).encode())

        data = io.recvline()
        if b'Coordinate greater than curve modulus' in data:  
            right = m - 1
        else:
            left = m + 1

    p = m - 1
    io.info(f'Got modulus {p = }')

Luego podemos encontrar $a$ y $b$ tomando dos puntos aleatorios de la curva (opciones 1 o 2). El proceso consiste en resolver un sistema de dos ecuaciones modulares en $a$ y $b$:

$$ \begin{cases} y_1^2 = x_1^3 + a x_1 + b \mod{p} \\ y_2^2 = x_2^3 + a x_2 + b \mod{p} \\ \end{cases} $$

Restando ambas ecuaciones, tenemos:

$$ y_1^2 - y_2^2 = x_1^3 - x_2^3 + a (x_1 - x_2) \mod{p} $$

Entonces, podemos despejar $a$:

$$ a = (y_1^2 - y_2^2 - x_1^3 + x_2^3) \cdot (x_1 - x_2)^{-1} \mod{p} $$

Y luego es trivial encontrar $b$:

$$ b = y_1^2 - x_1^3 - a x_1 \mod{p} $$

Esta es la implementación en Python:

    points = []
    x = 0

    while len(points) < 2:
        io.sendlineafter(b'> ', b'1')
        io.sendlineafter(b'x : ', str(x).encode())

        data = io.recvline()

        if b'Point confirmed on curve' in data:
            point = tuple(
                map(int, data.decode().replace(')', '').split(', ')[1:]))  
            points.append(point)

        x += 1

    (x1, y1), (x2, y2) = points
    a = (y1 ** 2 - y2 ** 2 - x1 ** 3 + x2 ** 3) * pow(x1 - x2, -1, p) % p
    b = (y1 ** 2 - x1 ** 3 - a * x1) % p

    io.info(f'Got parameters {a = } and {b = }')

Comprendiendo el reto

Ahora que hemos recuperado los parámetros de la curva, revisemos el reto nuevamente para ver cómo debemos capturar la flag.

En la opción 3, debemos proporcionar las coordenadas de un punto P correctamente para ver la flag (solo tenemos una oportunidad):

            elif option == '3':
                if setup:
                    print('Input x,y')
                    Px = int(input('x: '))
                    Py = int(input('y: '))
                    response = artifact.nextPoints()
                    if response[3] == Px and response[4] == Py:
                        print(
                            'You have confirmed the location. It\'s dangerous however to go alone. Take this: ',  
                            FLAG)
                    else:
                        print('The vessels will never be found...')
                    exit()
                else:
                    print('Configure origin point first')

Este punto P proviene de las dos últimas entradas de response, que es una tupla devuelta por nextPoints:

    def nextPoints(self):
        seed, enc_seed = self.prng.rotate()
        self.P *= seed
        self.EP *= enc_seed
        return ('New Points', self.EP.x, self.EP.y, self.P.x, self.P.y)

Usando la opción 2 descubrimos el punto EP, cuyas coordenadas son las posiciones 1 y 2 de la tupla que devuelve nextPoints:

            elif option == '2':
                if setup:
                    response = artifact.nextPoints()
                    print('Response')
                    print((response[0], response[1], response[2]))  
                else:
                    print('Configure origin point first')

Obsérvese que podemos controlar el valor de P y EP en setupPoints, pero no sabemos los valores de seed y enc_seed. Entonces, dado que conocemos el punto $\mathrm{EP}$ y $\mathrm{enc\_seed} \cdot \mathrm{EP}$, de alguna manera debemos encontrar $\mathrm{enc\_seed}$, esto es, resolver el ECDLP.

Ataque de Smart

La clave para resolver el ECDLP es que el orden de la curva es primo (realmente, $|E(\mathbb{F}_p)| = p$). Por lo tanto, tenemos una curva anómala, que podría ser vulnerable al ataque de Smart para resolver el ECDLP fácilmente.

El ataque de Smart es un método complejo que requiere conocimiento sobre teoría de los números algebraicos, el lema de Hensel y los números $p$-ádicos. Para obtener más información, lea estos recursos (los encontré útiles para comprender el ataque desde una perspectiva de alto nivel):

Encontré una implementación del ataque de Smart en SageMath en este write-up de un reto de CryptoHack. Usando esta implementación, podemos encontrar enc_seed:

    x2 = 6
    io.sendlineafter(b'> ', b'1')
    io.sendlineafter(b'x: ', str(x2).encode())

    E = EllipticCurve(GF(p), [a, b])
    EP = E.gens()[0]

    io.sendlineafter(b'> ', b'1')
    io.sendlineafter(b'x: ', str(EP[0]).encode())

    io.sendlineafter(b'> ', b'2')
    io.recvline()
    point = tuple(
        map(int, io.recvline().decode().replace(')', '').split(', ')[1:]))  
    enc_seed_EP = E(point[0], point[1])

    enc_seed = SmartAttack(EP, enc_seed_EP, p)
    io.info(f'Smart Attack -> {enc_seed = }')

Analizando el PRNG

Muy bien, entonces tenemos enc_seed. Echemos un vistazo a la clase PRNG:

class PRNG:

    def __init__(self, p, mul1, mul2):
        self.mod = p * 6089788258325039501929073418355467714844813056959443481824909430411674443639248386564763122373451773381582660411059922334086996696436657009055324008041039  
        self.exp = 2
        self.mul1 = mul1
        self.mul2 = mul2
        self.inc = int.from_bytes(b'Coordinates lost in space', 'big')
        self.seed = randint(2, self.mod - 1)

    def rotate(self):
        self.seed = (self.mul1 * pow(self.seed, 3) + self.mul2 * self.seed +
                     self.inc) % self.mod
        return self.seed, pow(self.seed, self.exp, self.mod)

Podemos expresar el método rotate en términos matemáticos (nótese que la clase está instanciada como self.prng = PRNG(p, a, b) en la clase Relic):

$$ s_{j + 1} = a s_j^3 + b s_j + i \mod{p q} $$

Entonces, $\mathrm{enc\_seed} = s_{j + 1}^2 \mod{p q}$. Curiosamente, la fórmula se parece a otra curva elíptica.

Los números pseudo-aleatorios $s_j$ están considerados $\mod{p q}$. Sin embargo, al multiplicar estos números por un punto de la curva elíptica, se reducirán $\mod{p}$, porque la curva está definida sobre $\mathbb{F}_p$. Por lo tanto, la fórmula del PRNG puede considerarse solo $\mod{p}$.

Como sabemos $\mathrm{enc\_seed}$ del ataque de Smart, podemos calcular la raíz cuadrada $\mod{p}$ (no $\mod{p q}$ por la explicación anterior). Una vez que tenemos la semilla $s_{j + 1}$, podremos calcular $s_{j + 2}$ aplicando la fórmula y predecir la salida de nextPoints, de manera que podamos encontrar la flag. Esta es la implementación:

    seed = int(GF(p)(enc_seed).nth_root(2))
    i = int.from_bytes(b'Coordinates lost in space', 'big')  
    next_seed = (a * pow(seed, 3) + b * seed + i) % p

    curr_P = EP * seed
    next_P = curr_P * next_seed
    io.info(f'Trying next point {next_P}...')

    io.sendlineafter(b'> ', b'3')
    io.sendlineafter(b'x: ', str(next_P[0]).encode())
    io.sendlineafter(b'y: ', str(next_P[1]).encode())

    io.success(io.recv().decode())

Flag

Si ejecutamos el script, veremos la flag:

$ python3 solve.py 138.68.166.146:32377
[+] Opening connection to 138.68.166.146 on port 32377: Done
[*] Got modulus p = 98807859381918657537428263421507671098277046895420042063839316200156326157051
[*] Got parameters a = 98708286800573747697090965573671079833937605909055221396616155663745907151444 and b = 22235152944190699843327692243188159330817147202763072426796844569091456960352
[*] Smart Attack -> enc_seed = 67440516568350265495759321275724631446066647201660934349374726772648832000938
[*] Trying next point (87513424733445795282705291920052722262294072879428526676725037034102784539109 : 46304974323527743139807054678481352167321888237327768089633252894299079270136 : 1)...  
[+] You have confirmed the location. However, It's dangerous to go alone. Take this:  HTB{th1s_4tt4ck_w4s_r3411y___SM4RT!}
[*] Closed connection to 138.68.166.146 port 32377

El script completo se puede encontrar aquí: solve.py.