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:
twist_and_shout.py
Dockerfile
twist_and_shout.xinetd

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 $\mathrm{x}$ de un punto de la curva elíptica. El servidor usará esa coordenada $\mathrm{x}$ Para multiplicar la flag por dicho punto la curva (es decir, cifra la flag) y se nos da la coordenada $\mathrm{x}$ resultante:

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 $P$, el servidor calcula $Q = d \cdot P$. Nuestro objetivo es encontrar $d$ y, por tanto, necesitamos resolver el problema del logaritmo discreto de curva elíptica (ECDLP), que es difícil ya que el orden de la curva es un número primo.

Obsérvese que el servidor utiliza un algoritmo no convencional para sumar dos puntos, usando solo las coordenadas $\mathrm{x}$ de los puntos:

# 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 = d \cdot P$, y el valor resultante es $Q_\mathrm{x}$ (que es exactamente 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 $\mathrm{x}$ dada. Podemos probar en local:

$ 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 $\mathrm{x}$ igual a $1$, pero el script de Python mostró un resultado. Veamos si tal punto existe en la curva:

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 $b$ de la curva expresada en forma de Weierstrass ($y^2 = x^3 + a x + b$). Entonces, solo modificando ese parámetro $b$ es posible encontrar otra curva donde el ECDLP sea fácil de resolver. Por ejemplo, si el orden de la curva es smooth (tiene muchos factores primos pequeños), el ECDLP se soluciona usando el algoritmo de Pohlig-Hellman.

Twist

En esta situación, el servidor utiliza otro método para la suma y la multiplicación, y emplea tanto $a$ como $b$. Sin embargo, dado que el nombre del desafío habla sobre de “twist”, podemos pensar en el twist de una curva elíptica, que es una curva sobre un cuerpo finito de una potencia de un número primo. Entonces, si tenemos $E(\mathbb{F}_q)$, un twist (cuadrático) de esta curva sería $E(\mathbb{F}_{q^2})$.

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 $P$ con coordenada $\mathrm{x} = 1$ al servidor
El punto resultado $Q = d \cdot P$ no está dentro $E(\mathbb{F}_q)$ pero sí en $E(\mathbb{F}_{q^2})$
Resolver el ECDLP $Q = d \cdot P$ en $E(\mathbb{F}_{q^2})$ usando Pohlig-Hellman porque el pedido de $P$ 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.