Elliptic Labyrinth Revenge

5 minutos de lectura

Este reto es una modificación de Elliptic Labyrinth para obligar a los jugadores de CTF a usar la vía intencionada de resolver el reto.

Encontrando diferencias

El código fuente proporcionado es un poco diferente:

import os, json
from hashlib import sha256
from random import randint
from Crypto.Util.number import getPrime, long_to_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from sage.all_cmdline import *
from secret import FLAG


class ECC:

    def __init__(self, bits):
        self.p = getPrime(bits)
        self.a = randint(1, self.p)
        self.b = randint(1, self.p)

    def gen_random_point(self):
        return EllipticCurve(GF(self.p), [self.a, self.b]).random_point()


def menu():
    print("1. Get parameters of path")
    print("2. Try to exit the labyrinth")
    option = input("> ")
    return option


def main():
    ec = ECC(512)

    A = ec.gen_random_point()
    print("This is the point you calculated before:")
    print(json.dumps({'x': hex(A[0]), 'y': hex(A[1])}))

    while True:
        choice = menu()
        if choice == '1':
            r = randint(ec.p.bit_length() // 3, 2 * ec.p.bit_length() // 3)
            print(
                json.dumps({
                    'p': hex(ec.p),
                    'a': hex(ec.a >> r),
                    'b': hex(ec.b >> r)
                }))
        elif choice == '2':
            iv = os.urandom(16)
            key = sha256(long_to_bytes(pow(ec.a, ec.b, ec.p))).digest()[:16]
            cipher = AES.new(key, AES.MODE_CBC, iv)
            flag = pad(FLAG, 16)
            print(
                json.dumps({
                    'iv': iv.hex(),
                    'enc': cipher.encrypt(flag).hex()
                }))
        else:
            print('Bye.')
            exit()


if __name__ == '__main__':
    main()

Esta vez, no existe la opción para solicitar puntos aleatorios en la curva. Solo tenemos un punto aleatorio al principio:

    A = ec.gen_random_point()
    print("This is the point you calculated before:")
    print(json.dumps({'x': hex(A[0]), 'y': hex(A[1])}))

Entonces solo tenemos opción 1, que muestra el número primo y los bits más significativos de y (como en Elliptic Labyrinth):

        if choice == '1':
            r = randint(ec.p.bit_length() // 3, 2 * ec.p.bit_length() // 3)
            print(
                json.dumps({
                    'p': hex(ec.p),
                    'a': hex(ec.a >> r),
                    'b': hex(ec.b >> r)
                }))

La opción 2 es la opción 3 de Elliptic Labyrinth. Utiliza como clave AES para cifrar la flag:

        elif choice == '2':
            iv = os.urandom(16)
            key = sha256(long_to_bytes(pow(ec.a, ec.b, ec.p))).digest()[:16]
            cipher = AES.new(key, AES.MODE_CBC, iv)
            flag = pad(FLAG, 16)
            print(
                json.dumps({
                    'iv': iv.hex(),
                    'enc': cipher.encrypt(flag).hex()
                }))

Entonces, el objetivo es encontrar los parámetros y dado un solo punto de la curva, y los bits más significativos de y .

Método de Coppersmith

Pongamos la información que tenemos en términos matemáticos. Definimos y como los bits más significativos de y , respectivamente. Por lo tanto, sabemos que y para algunos . Si podemos encontrar , y , podremos encontrar y .

La única ecuación que podemos usar es la ecuación de la curva:

Sustituyendo y obtenemos:

Obsérvese que las incógnitas son principalmente y (podemos hacer un ataque de fuerza bruta en si fuera necesario).

Por lo tanto, podemos definir un polinomio que satisface que :

Como sucedía en Bank-er-smith, cuando se conocen los bits más significativos de un número, un método típico para aplicar es Coppersmith (que utiliza reducción de retículo mediante LLL por detrás). Esta vez, el problema es que tenemos un polinomio de dos variables. Pero hay implementaciones de métodos de Coppersmith para polinomios de varias variables.

Encontrar una implementación

Las implementaciones más utilizadas son defund y ubuntor. La flag de Elliptic Labyrinth hacía referencia a la implementación de defund, pero no logré que funcionara correctamente (tampoco la de ubuntor).

Al final, encontré este Gist de GitHub con otra implementación del método de Coppersmith para polinomios de dos variables que funcionaba la mayoría de las veces.

Implementación en Python

Luego, solo tenemos que recopilar la información del reto y aplicar el método de Coppersmith tratando de adivinar (podemos hacer un poco de fuerza bruta):

def main():
    io = get_process()
    io.recvline()

    data = json.loads(io.recvline().decode())
    x_p, y_p = int(data['x'], 16), int(data['y'], 16)

    io.sendlineafter(b'> ', b'2')
    data = json.loads(io.recvline().decode())
    iv, enc = bytes.fromhex(data['iv']), bytes.fromhex(data['enc'])

    a_highs, b_highs = [], []

    for _ in range(50):
        io.sendlineafter(b'> ', b'1')
        data = json.loads(io.recvline().decode())

        p = int(data['p'], 16)
        a_highs.append(int(data['a'], 16))
        b_highs.append(int(data['b'], 16))

    aH, bH = sorted(a_highs)[-1], sorted(b_highs)[-1]

    r_mean = 512 - aH.bit_length()
    found = False

    for r in range(r_mean - 5, r_mean + 5):
        PR = PolynomialRing(Zmod(p), names='x,y')
        x, y = PR.gens()
        S = y_p ** 2 - x_p ** 3 - (aH << r) * x_p - (bH << r)

        pol = x_p * x + y - S

        try:
            aL, bL = bivariate(pol, 2 ** r, 2 ** r)
            a, b = int(aL + (aH << r)), int(bL + (bH << r))

            if (y_p ** 2 - x_p ** 3 - a * x_p - b) % p == 0:
                found = True
                break
        except IndexError:
            pass

    if found:
        key = sha256(long_to_bytes(pow(a, b, p))).digest()[:16]
        cipher = AES.new(key, AES.MODE_CBC, iv)
        io.success(unpad(cipher.decrypt(enc), 16).decode())
    else:
        io.failure('Not found')

Observe que recopilo algunos valores por y y elijo los que son más grandes, por lo que es más probable que el método de Coppersmith tenga éxito.

Flag

Al ejecutar el script, fallará algunas veces, pero eventualmente tendrá éxito:

$ python3 solve.py 165.232.108.240:31791
[+] Opening connection to 165.232.108.240 on port 31791: Done
[-] Not found
[*] Closed connection to 165.232.108.240 port 31791

$ python3 solve.py 165.232.108.240:31791
[+] Opening connection to 165.232.108.240 on port 31791: Done
[+] HTB{y0u_5h0u1d_h4v3_u53d_c00p325m17h}
[*] Closed connection to 165.232.108.240 port 31791

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