Twist and shout
6 minutos de lectura
I’ll shout about my curve all day, it’s totally secure. You’ll have to pull the solution from my cold dead hands!
Challenge contributed by CryptoHack
Connect at
archive.cryptohack.org 11718
Challenge files:
Se nos proporciona un servidor que usa una curva elíptica para cifrar la flag.
Análisis del código fuente
Tenemos los parámetros de la curva:
"""
Define the elliptic curve
E: y^2 = x^3 + a*x + b
With order
n = 340282366920938463465004184633952524077
= 2^128 - 1629577202184312621
"""
q = 2**128 - 159
a = 1
b = 1494
Se nos permite ingresar a una coordenada
def gen_secret(secret):
d = secret.lstrip("ECSC{").rstrip("}")
return int.from_bytes(d.encode(), "big")
def shout(x, d):
P = (x, 1)
Q = xMUL(P, d)
return Q[0] * pow(Q[1], -1, q) % q
def challenge():
"""
My curve has prime order, so I'll let you
send as many points as you like! You'll
never recover my secret before your flight home!!
"""
import os
flag = os.environ.get("FLAG", "ECSC{fake_flag_for_testing}").strip()
d = gen_secret(flag)
while True:
x = int(input("x-coordinate: "))
print(shout(x, d))
Por lo tanto, lo que tenemos es que, dado un punto
Obsérvese que el servidor utiliza un algoritmo no convencional para sumar dos puntos, usando solo las coordenadas
# Curve addition law using only x-coordinates, coded from
# https://www.hyperelliptic.org/EFD/g1p/data/shortw/xz/ladder/ladd-2002-it
def xDBLADD(P, Q, PQ):
(X1, Z1), (X2, Z2), (X3, Z3) = PQ, P, Q
X4 = (X2**2 - a * Z2**2) ** 2 - 8 * b * X2 * Z2**3
Z4 = 4 * (X2 * Z2 * (X2**2 + a * Z2**2) + b * Z2**4)
X5 = Z1 * ((X2 * X3 - a * Z2 * Z3) ** 2 - 4 * b * Z2 * Z3 * (X2 * Z3 + X3 * Z2))
Z5 = X1 * (X2 * Z3 - X3 * Z2) ** 2
X4, Z4, X5, Z5 = (c % q for c in (X4, Z4, X5, Z5))
return (X4, Z4), (X5, Z5)
El algoritmo de multiplicación por escalar es más común, usando Montgomery Ladder:
# Montgomery Ladder for scalar multiplication
def xMUL(P, k):
Q, R = (1, 0), P
for i in reversed(range(k.bit_length() + 1)):
if k >> i & 1:
R, Q = Q, R
Q, R = xDBLADD(Q, R, P)
if k >> i & 1:
R, Q = Q, R
return Q
Incluso si esto es extraño, el servidor solo está calculando Q[0] * pow(Q[1], -1, q) % q
):
def shout(x, d):
P = (x, 1)
Q = xMUL(P, d)
return Q[0] * pow(Q[1], -1, q) % q
El fallo de seguridad
La vulnerabilidad es que el servidor no verifica si hay un punto en la curva que tiene la coordenada
$ python3 twist_and_shout.py
x-coordinate: 1
273502621369416944597939413671202860337
Y en SageMath:
$ sage -q
sage: q = 2 ** 128 - 159
....: a = 1
....: b = 1494
sage: E = EllipticCurve(GF(q), [a, b])
sage: E.lift_x(1)
...
ValueError: No point with x-coordinate 1 on Elliptic Curve defined by y^2 = x^3 + x + 1494 over Finite Field of size 340282366920938463463374607431768211297
Como se puede ver, no hay tal punto con coordenada
sage: E.lift_x(273502621369416944597939413671202860337)
...
ValueError: No point with x-coordinate 273502621369416944597939413671202860337 on Elliptic Curve defined by y^2 = x^3 + x + 1494 over Finite Field of size 340282366920938463463374607431768211297
Tampoco…
Ataque de curva inválida
Con esta configuración, que el servidor no verifica la existencia del punto, pero aun así calcula la multiplicación, podemos intentar realizar un ataque de curva inválida. La idea es encontrar una curva en la que sea fácil resolver el ECDLP, tomar algún punto, enviarlo al servidor, devolver el resultado a la curva inválida y resolver el ECDLP.
Por lo general, los ataques de curva inválida aprovechan el hecho de que la suma y la multiplicación no dependen del parámetro
Twist
En esta situación, el servidor utiliza otro método para la suma y la multiplicación, y emplea tanto
Y sorprendentemente, los puntos anteriores se encuentran en el twist de la curva:
sage: E2 = EllipticCurve(GF(q ** 2), [a, b])
sage: E2.lift_x(1)
(1 : 195291075018479657145988939598502694512*z2 + 75013447040380062933758487920479163178 : 1)
sage: E2.lift_x(273502621369416944597939413671202860337)
(273502621369416944597939413671202860337 : 137188032605880964854730507512363736488*z2 + 62763016274206965317903115936606943492 : 1)
Además, el orden de la curva es relativamente smooth:
sage: factor(E2.order())
3 * 79 * 644899 * 1283505703 * 19385376821 * 89480282251 * 340282366920938463465004184633952524077
En realidad, para Pohlig-Hellman necesitamos que el orden del punto sea smooth, y lo es:
sage: factor(E2.lift_x(1).order())
3 * 79 * 644899 * 1283505703 * 19385376821 * 89480282251
Entonces, tenemos todo lo que necesitamos para resolver el ECDLP:
- Enviar punto
con coordenada al servidor - El punto resultante
no está dentro pero sí en - Resolver el ECDLP
en usando Pohlig-Hellman porque el orden de es smooth
Flag
Ahora, podemos escribir un script de Python para resolver el reto:
$ python3 solve.py archive.cryptohack.org 11718
[+] Opening connection to archive.cryptohack.org on port 11718: Done
[*] Closed connection to archive.cryptohack.org port 11718
[+] ECSC{7w1st_&&_sh0ut!}
El script completo se puede encontrar aquí: solve.py
.