Kernel searcher

6 minutos de lectura

I have a super secret isogeny. Wanna know where your point ends up? Just send me your favourite coordinates.
Challenge contributed by CryptoHack
Challenge files:
Dockerfile
entry.sh
kernel_searcher.sage
kernel_searcher.xinetd

Se nos proporciona un script en SageMath que oculta la flag bajo una isogenia y nos permite evaluar la isogenia en cualquier punto que deseemos.

Análisis del código fuente

La parte relevante del script es esta:

import json
from Crypto.Util.number import bytes_to_long

proof.all(False)

A, B = 2**216, 3**137
p = A * B - 1

F.<i> = GF(p^2, modulus=[1,0,1])
E = EllipticCurve(F, [0, 6, 0, 1, 0])

# Torsion Basis for E[A]
P, Q = canonical_torsion_basis(E, A)

import os
flag = os.environ.get("FLAG", "ECSC{fake_flag_for_testing}").strip().encode()
ker = P + bytes_to_long(flag) * Q
challenge_isogeny = E.isogeny(
    ker, algorithm="factored", model="montgomery"
)

def accept_point(data):
    data = json.loads(data)
    try:
        x0 = int(data["x0"], 16)
        x1 = int(data["x1"], 16)
        x = F([x0, x1])
    except Exception as e:
        print(e)
        return {"error": "Invalid Fp2 value"}
    
    if not E.is_x_coord(x):
        return {"error": "Invalid Point"}

    P = E.lift_x(x)
    imP = challenge_isogeny(P)
    return json.dumps({"x0": hex(imP[0][0]), "x1": hex(imP[0][1])})

def main():
    print(f"Welcome to my isogeny factory!")
    print(f"My isogeny is so secret, I'll let you evaluate any point you like!")
    while True:
        data = input("Send the point you wish to evaluate: ")
        output = accept_point(data)
        print(output)

if __name__ == "__main__":
    main()

Básicamente, el servidor usa una curva elíptica dada sobre , donde .

La curva elíptica se define como:

Nótese que de es un cuerpo finito donde los elementos son polinomios en de grado . Esta curva elíptica es supersingular.

Luego, el servidor encuentra dos puntos y cuyo orden es . Con esos puntos, el servidor define el núcleo (kernel) de la isogenia como , donde es la flag.

Isogenia

Una isogenia es un homomorfismo entre dos curvas elípticas (supersingulares). Y el kernel de un homomorfismo es el conjunto de elementos que se mapean al elemento identidad.

Si denotamos la isogenia por , lo que tenemos es que . Como el kernel se define por un solo punto, cualquier múltiplo de ese punto está en el kernel (incluido el punto en el infinito). Por lo tanto, para cualquier .

Además, como es un homomorfismo entre grupos, se deduce que . Y por tanto tenemos

Solución

Podemos obtener resolviendo el problema del logaritmo discreto de curva elíptica (ECDLP). El problema aquí es que todavía no conocemos el codominio de la isogenia.

Encontrando los parámetros de la curva

Después de un poco de investigación y unas pocas pruebas, podemos ver que el codominio es una curva elíptica con la siguiente estructura:

Para un cierto que depende de .

Podemos obtener ese valor de si conocemos un punto de la curva del codominio.

Aquí, probé algunos puntos interesantes. Por ejemplo, envié el punto al servidor, y la salida fue un punto . El servidor solo devuelve la coordenada , pero al probar en local, vi que la coordenada siempre era . Por lo tanto, podemos resolver la ecuación de la curva del codominio para :

io = get_process()

io.sendlineafter(b'Send the point you wish to evaluate: ',
                 json.dumps({'x0': '0', 'x1': '0'}).encode())
data = json.loads(io.recvline().decode())
x0, x1 = int(data.get('x0'), 16), int(data.get('x1'), 16)
X = F([x0, x1])
C = (- X ** 3 - X) / (X ** 2)

EE = EllipticCurve(F, [0, C, 0, 1, 0])

Logaritmo discreto

Y ahora estamos listos para resolver el logaritmo discreto con las imágenes de los puntos y :

io.sendlineafter(b'Send the point you wish to evaluate: ',
                 json.dumps({'x0': hex(P[0][0]), 'x1': hex(P[0][1])}).encode())
data = json.loads(io.recvline().decode())
x0, x1 = int(data.get('x0'), 16), int(data.get('x1'), 16)
imP = EE.lift_x(F([x0, x1]))

io.sendlineafter(b'Send the point you wish to evaluate: ',
                 json.dumps({'x0': hex(Q[0][0]), 'x1': hex(Q[0][1])}).encode())
data = json.loads(io.recvline().decode())
x0, x1 = int(data.get('x0'), 16), int(data.get('x1'), 16)
imQ = EE.lift_x(F([x0, x1]))
io.close()

Y esto es fácil de resolver porque el orden de y es , una potencia de . Por lo tanto, las imágenes de los puntos también tienen una potencia de como orden.

Definimos y . Queremos resolver la ecuación

Dado que el orden de y son potencias de , podemos expresar en binario:

Si multiplicamos por el orden de , obtenemos , si dividimos el orden entre y multiplicamos, tenemos

Ahora, si es el punto en el infinito (el elemento neutro), sabemos que , si no, .

Después de eso, podemos ver que

Ahora multiplicamos a ambos lados por , y tenemos

De nuevo, si es cero, entonces , y si no, .

Luego,

Y multiplicaríamos por para determinar . Continuaríamos todo el proceso hasta que encontrar todos los bits desde hasta :

def dlog(G, nG):
    i = -1
    bits = []
    order = A

    while order:
        i += 1
        order //= 2

        if order * (nG - (sum(bits)) * G) != 0 * G:
            bits.append(2 ** i)

    return sum(bits)


d = dlog(imQ, -imP)
io.success(bytes.fromhex(hex(int(d))[2:]).decode())

Flag

Y finalmente, encontramos la flag:

$ python3 solve.py
[+] Starting local process '/usr/bin/sage': pid 7514
[*] Stopped process '/usr/bin/sage' (pid 7514)
[+] ECSC{learning_to_isogeny}

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