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:
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 $E$ sobre $\mathbb{F}_{p^2}$, donde $p = 2^{216} \, 3^{137} - 1$.
La curva elíptica se define como:
$$ E: y^2 = x^3 + 6 x^2 + x \mod{p, i^2 + 1} $$
Nótese que de $\mathbb{F}_{p^2}$ es un cuerpo finito donde los elementos son polinomios en $i$ de grado $1$. Esta curva elíptica es supersingular.
Luego, el servidor encuentra dos puntos $P$ y $Q$ cuyo orden es $2^{216}$. Con esos puntos, el servidor define el núcleo (kernel) de la isogenia como $P + d \cdot Q$, donde $d$ 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 $\phi$, lo que tenemos es que $\phi(P + d \cdot Q) = 0$. 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, $\phi(k \cdot (P + d \cdot Q)) = 0$ para cualquier $k \in \mathbb{F}_{p^2}$.
Además, como $\phi$ es un homomorfismo entre grupos, se deduce que $\phi(P + d \cdot Q) = \phi(P) + d \cdot \phi(Q) = 0$. Y por tanto tenemos
$$ -\phi(P) = d \cdot \phi(Q) $$
Solución
Podemos obtener $d$ 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:
$$ EE: y^2 = x^3 + C x^2 + x \mod{p, i^2 + 1} $$
Para un cierto $C \in \mathbb{F}_{p^2}$ que depende de $\ker{\phi}$.
Podemos obtener ese valor de $C$ si conocemos un punto de la curva del codominio.
Aquí, probé algunos puntos interesantes. Por ejemplo, envié el punto $E(0, 0)$ al servidor, y la salida fue un punto $EE(X, 0)$. El servidor solo devuelve la coordenada $\mathrm{x}$, pero al probar en local, vi que la coordenada $\mathrm{y}$ siempre era $0$. Por lo tanto, podemos resolver la ecuación de la curva del codominio para $C$:
$$ 0^2 = X^3 + C X^2 + X \iff C = \frac{-X^3 - X}{X^2} $$
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 $P$ y $Q$:
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 $P$ y $Q$ es $2^{216}$, una potencia de $2$. Por lo tanto, las imágenes de los puntos también tienen una potencia de $2$ como orden.
Definimos $P_i = \phi(P)$ y $Q_i = \phi(Q)$. Queremos resolver la ecuación $-P_i = d \cdot Q_i$
Dado que el orden de $P_i$ y $Q_i$ son potencias de $2$, podemos expresar $d$ en binario:
$$ -P_i = d \cdot Q_i = (d_0 + 2 d_1 + 2^2 d_2 + \dots + 2^m d_m) \cdot Q_i $$
Si multiplicamos por el orden de $Q_i$, obtenemos $0 = 0$, si dividimos el orden entre $2$ y multiplicamos, tenemos
$$ \begin{align*} 2^{215} \cdot (-P_i) & = 2^{215} \cdot (d_0 + 2 d_1 + 2^2 d_2 + \dots + 2^m d_m) \cdot Q_i \\ & = 2^{215} d_0 \cdot Q_i \end{align*} $$
Ahora, si $2^{215} \cdot (-P_i)$ es el punto en el infinito (el elemento neutro), sabemos que $d_0 = 0$, si no, $d_0 = 1$.
Después de eso, podemos ver que
$$ -P_i - (d_0) \cdot Q_i = (2 d_1 + 2^2 d_2 + \dots + 2^m d_m) \cdot Q_i $$
Ahora multiplicamos a ambos lados por $2^{214}$, y tenemos
$$ \begin{align*} 2^{214} \cdot (-P_i - (d_0) \cdot Q_i) & = 2^{214} \cdot (2 d_1 + 2^2 d_2 + \dots + 2^m d_m) \cdot Q_i \\ & = 2^{215} d_1 \cdot Q_i \end{align*} $$
De nuevo, si $2^{214} \cdot (-P_i - (d_0) \cdot Q_i)$ es cero, entonces $d_1 = 0$, y si no, $d_1 = 1$.
Luego,
$$ -P_i - (d_0 + 2 d_1) \cdot Q_i = (2^2 d_2 + \dots + 2^m d_m) \cdot Q_i $$
Y multiplicaríamos por $2^{213}$ para determinar $d_2$. Continuaríamos todo el proceso hasta que encontrar todos los bits desde $d_0$ hasta $d_m$:
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.