400curves
10 minutos de lectura
Se nos proporciona el código fuente del servidor en Python:
from Crypto.Util.number import inverse, bytes_to_long
import socketserver
import signal
from secret import FLAG
a = 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
E = {'a': a, 'b': b, 'p': p}
class Handler(socketserver.BaseRequestHandler):
def handle(self):
signal.alarm(0)
main(self.request)
class ReusableTCPServer(socketserver.ForkingMixIn, socketserver.TCPServer):
pass
def sendMessage(s, msg):
s.send(msg.encode())
def recieveMessage(s, msg):
sendMessage(s, msg)
return s.recv(4096).decode().strip()
def add(P, Q, E):
if (P == (0, 0)):
return Q
elif (Q == (0, 0)):
return P
else:
Ea, Ep = E['a'], E['p']
x1, y1 = P
x2, y2 = Q
if ((x1 == x2) & (y1 == -y2)):
return ((0, 0))
else:
if (P != Q):
l = (y2 - y1) * inverse(x2 - x1, Ep)
else:
l = (3 * (x1**2) + Ea) * inverse(2 * y1, Ep)
x3 = ((l**2) - x1 - x2) % Ep
y3 = (l * (x1 - x3) - y1) % Ep
return x3, y3
def multiply(P, n, E):
Q = P
R = (0, 0)
while (n > 0):
if (n % 2 == 1):
R = add(R, Q, E)
Q = add(Q, Q, E)
n = n // 2
return R
def main(s):
sendMessage(s, "Establising the TLS handsake...\n")
while True:
C = recieveMessage(s, "Awaiting public key of the client...\n")
try:
x, y = [int(i) for i in C.strip().split()]
S = multiply((x, y), bytes_to_long(FLAG), E)
sendMessage(s, f"Shared secret: {S}\n")
except:
sendMessage(s, f"Error occured!\n")
if __name__ == '__main__':
socketserver.TCPServer.allow_reuse_address = True
server = ReusableTCPServer(("0.0.0.0", 1337), Handler)
server.serve_forever()
El servidor usa Criptografía de Curva Elíptica (ECC) con la curva secp256r1.
Contexto de ECC
La Criptografía de Curva Elíptica es un criptosistema de clave pública, por lo que hay una clave pública y una clave privada.
Sea $E$ una curva elíptica definida en forma de Weierstrass:
$$ E: \; y^2 = x^3 + ax + b $$
Donde $(x, y)$ son puntos de la curva.
En ECC, la curva elíptica anterior se considera sobre un cuerpo finito (por ejemplo, $\mathbb{F}_p$, con $p$ un número primo). Por lo tanto, la curva se puede expresar como $E(\mathbb{F}_p)$.
Como resultado, los puntos en la curva forman un grupo abeliano con la suma:
- La operación es interna (es decir, $P + Q \in E(\mathbb{F}_p) \; \forall P, Q \in E(\mathbb{F}_p)$)
- Hay un único elemento neutro que generalmente se llama $O$, tal que $P + O = O + P = P$. También se conoce como “punto en el infinito”
- Todo punto tiene un único inverso, es decir $\exists! Q \in E(\mathbb{F}_p) \;|\; P + Q = O \;\; \forall P \in E(\mathbb{F}_p)$. Se podría decir que $Q = -P$, abusando de la notación aditiva
- La operación es asociativa (y también conmutativa)
La operación de la suma tiene un cierto algoritmo, que se implementa en el código fuente anterior. Una vez definida la suma, podemos expresar el producto de un punto por un escalar:
$$ kP = \underbrace{P + \dots + P}_{k\; \text{times}} $$
Para usar ECC, debemos tomar un punto generador $G$ de la curva, luego tomar un número $n$ y multiplicar $n$ por $G$. La clave pública está formada por los puntos $G$ y $nG$ (aparte de los parámetros de la curva $a$, $b$ y el cuerpo finito $\mathbb{F}_p$); y la clave privada es el número $n$.
ECC se puede utilizar para el Protocolo de intercambio de claves Diffie-Hellman (ECDH), para el algoritmo de firma digital (ECDSA) o para cifrado (ECIES), entre otros. La seguridad de este criptosistema recae en la dificultad de resolver el Problema del Logaritmo Discreto de Curva Elíptica (ECDLP), es decir, encontrar $n$ a partir de $G$ y $nG$.
El fallo de seguridad
Como se dijo antes, la suma de puntos tiene un cierto algoritmo, que se implementa en el código fuente anterior. Al sumar puntos $P(x_1, y_1)$ y $Q(x_2, y_2)$, el algoritmo depende solamente de $x_1$, $x_2$, $y_1$, $y_2$, $a$ y $p$. Obsérvese que $b$ nunca se usa.
Además, las operaciones de algoritmo son operaciones básicas con números. No hay restricción en los valores $x_1$, $x_2$, $y_1$, $y_2$. Con esto quiero decir que, si $P(x_1, y_1)$ y $Q(x_2, y_2)$ son puntos de $E(\mathbb{F}_p)$, el resultado $R(x_3, y_3)$ será otro punto de la curva. Sin embargo, si $P$ y $Q$ no están en la curva, $R$ tampoco.
El razonamiento anterior es clave para comprender el fallo y el ataque de este reto. El servidor nos permite ingresar una clave pública $C(x, y)$ (un punto dentro de la curva elíptica). Luego, el servidor tomará nuestro punto y lo multiplicará por la flag en formato decimal ($s = \mathrm{flag} \cdot C$):
def main(s):
sendMessage(s, "Establising the TLS handsake...\n")
while True:
C = recieveMessage(s, "Awaiting public key of the client...\n")
try:
x, y = [int(i) for i in C.strip().split()]
S = multiply((x, y), bytes_to_long(FLAG), E)
sendMessage(s, f"Shared secret: {S}\n")
except:
sendMessage(s, f"Error occured!\n")
Las implementaciones de add y multiply son correctas, pero el servidor no verifica que los puntos de entrada pertenezcan a la curva… Por lo tanto, el servidor es vulnerable a un Ataque de Curva Inválida.
Ataque de Curva Inválida
Sabemos que ECC depende de la dificultad para resolver el ECDLP, es decir, encontrar $n$ dados $G$ y $nG$. Este problema es más fácil de resolver cuando el orden de la curva tiene factores primos pequeños (también conocido como suave, smooth), usando el algoritmo de Pohligh-Hellman.
Como el servidor no verifica los puntos de entrada, podemos definir una curva similar a la curva del servidor (secp256r1), cambiando la $b$, hasta que el orden de la curva sea suave (smooth). Luego, tomaremos un punto generador $G$ de esta nueva curva y lo enviaremos al servidor. El servidor calculará $S = \mathrm{flag} \cdot G$. Obviamente, $S$ no es un punto de la curva del servidor, pero sí de nuestra curva. Ahora podemos resolver el ECDLP y encontrar $\mathrm{flag}$ a partir de $G$ y $\mathrm{flag} \cdot G$, ya que el orden de nuestra curva es smooth.
Entonces, en primer lugar, usemos diferentes valores por $b$ hasta encontrar uno que dé una curva con orden smooth. En SageMath, podemos usar el siguiente código:
#!/usr/bin/env sage
a = 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
for b in range(10):
try:
print(f"{b = }. Curve's order:", factor(EllipticCurve(GF(p), [a, b]).order()))
except:
pass
Y estos son los resultados:
$ sage test_parameters.sage
b = 0. Curve's order: 2^96 * 7 * 274177 * 67280421310721 * 11318308927973941931404914103
b = 1. Curve's order: 71 * 823 * 1229 * 7489 * 30203 * 1275057701 * 5590685618197487513633360286414913886653362665945221
b = 3. Curve's order: 2^4 * 3 * 7 * 13 * 37 * 97 * 113 * 65364863466230065009299609518518318921279098632127819301704248465833
b = 4. Curve's order: 2^2 * 13 * 19 * 179 * 13003 * 1307093479 * 218034068577407083 * 16884307952548170257 * 10464321644447000442097
b = 5. Curve's order: 2^2 * 3 * 7 * 13 * 2447 * 43333351749528183857746664058033075385207938864390055103100636196733549
b = 6. Curve's order: 2^2 * 5 * 4003 * 16033 * 102001 * 884390526899024919222120216398419141830968591728388637593606029
b = 7. Curve's order: 2^3 * 1151 * 7103 * 68360856945170627439059632547237 * 25897883110213973866199776436038742629
b = 8. Curve's order: 2^2 * 3 * 5 * 179 * 81173 * 132819857987697940358590682448908949725127147465817820814841295533643
b = 9. Curve's order: 2^2 * 7 * 653 * 72337 * 119591 * 88586821697531 * 8263795586816543575234964957311495031799816731687
Parece que $b = 4$ da un orden suficientemente suave. Tal vez los últimos tres factores siguen siendo grandes, pero los pequeños deberían ser suficientes para resolver el ECDLP.
Implementación del ataque
Para implementar el Ataque de Curva Inválida, debemos tomar la curva vulnerable y encontrar un punto generador $G$. Luego, enviarlo al servidor y resolver el ECDLP. Estas tareas se implementan en el siguiente código Python (importando funciones de SageMath):
#!/usr/bin/env python3
from Crypto.Util.number import long_to_bytes
from pwn import log, remote, sys
from sage.all import crt, discrete_log, EllipticCurve, factor, GF
a = 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
Fp = GF(p)
host, port = sys.argv[1].split(':')
def get_S(b):
E = EllipticCurve(Fp, [a, b])
order = E.order()
factors = factor(order)
G = E.gens()[0]
log.info(f'ord(E_{b}) = {factors}')
io = remote(host, int(port))
io.sendlineafter(b'Awaiting public key of the client...\n', f'{G[0]} {G[1]}'.encode())
io.recvuntil(b'Shared secret: ')
S_tuple = eval(io.recvline().decode())
io.close()
return order, G, factors, E(S_tuple)
def get_dlogs(S, G, order, factors, new_factors, dlogs):
for prime, exponent in factors:
log.info(f'{prime = }, {exponent = }')
new_factors.append(prime ** exponent)
t = order // new_factors[-1]
dlogs.append(discrete_log(t * S, t * G, operation='+'))
def main():
order, G, factors, S = get_S(4)
new_factors, dlogs = [], []
get_dlogs(S, G, order, factors[:-3], new_factors, dlogs)
flag = crt(dlogs, new_factors)
log.success(long_to_bytes(flag).decode())
if __name__ == '__main__':
main()
Sin embargo, parece que la flag no encaja en el módulo del CRT:
$ python3 solve.py 142.93.33.226:32737
[*] ord(E_4) = 2^2 * 13 * 19 * 179 * 13003 * 1307093479 * 218034068577407083 * 16884307952548170257 * 10464321644447000442097
[+] Opening connection to 142.93.33.226 on port 32737: Done
[*] Closed connection to 142.93.33.226 port 32737
[*] prime = 2, exponent = 2
[*] prime = 13, exponent = 1
[*] prime = 19, exponent = 1
[*] prime = 179, exponent = 1
[*] prime = 13003, exponent = 1
[*] prime = 1307093479, exponent = 1
Traceback (most recent call last):
File "solve.py", line 56, in <module>
main()
File "solve.py", line 52, in main
log.success(long_to_bytes(flag).decode())
UnicodeDecodeError: 'utf-8' codec can't decode byte 0xb4 in position 1: invalid start byte
Obsérvese que el orden de la curva legítima es muy grande, en comparación con el módulo del CRT:
$ python3 -q
>>> 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
115792089210356248762697446949407573530086143415290314195533631308867097853951
>>> 2 ** 2 * 13 * 19 * 179 * 13003 * 1307093479
3005800733613248324
Por lo tanto, debemos resolver el ECDLP completo, que es muy difícil y lento. Pero hay una alternativa: podemos aplicar el mismo ataque varias veces. Por ejemplo, tomemos también $b = 0$ y $b = 1$:
def main():
order_0, G_0, factors_0, S_0 = get_S(0)
order_1, G_1, factors_1, S_1 = get_S(1)
order_4, G_4, factors_4, S_4 = get_S(4)
new_factors, dlogs = [], []
get_dlogs(S_0, G_0, order_0, factors_0[:-2], new_factors, dlogs)
get_dlogs(S_1, G_1, order_1, factors_1[:-1], new_factors, dlogs)
get_dlogs(S_4, G_4, order_4, factors_4[1:-3], new_factors, dlogs)
flag = crt(dlogs, new_factors)
log.success(long_to_bytes(flag).decode())
Nótese que estamos omitiendo el factor $2^2$ de la curva de $b = 4$ porque hay un factor $2^{96}$ de la curva con $b = 0$ (los módulos del CRT tienen que ser coprimos).
Flag
Y ahora funciona. Aquí tenemos la flag:
$ python3 solve.py 142.93.33.226:32737
[*] ord(E_0) = 2^96 * 7 * 274177 * 67280421310721 * 11318308927973941931404914103
[+] Opening connection to 142.93.33.226 on port 32737: Done
[*] Closed connection to 142.93.33.226 port 32737
[*] ord(E_1) = 71 * 823 * 1229 * 7489 * 30203 * 1275057701 * 5590685618197487513633360286414913886653362665945221
[+] Opening connection to 142.93.33.226 on port 32737: Done
[*] Closed connection to 142.93.33.226 port 32737
[*] ord(E_4) = 2^2 * 13 * 19 * 179 * 13003 * 1307093479 * 218034068577407083 * 16884307952548170257 * 10464321644447000442097
[+] Opening connection to 142.93.33.226 on port 32737: Done
[*] Closed connection to 142.93.33.226 port 32737
[*] prime = 2, exponent = 96
[*] prime = 7, exponent = 1
[*] prime = 274177, exponent = 1
[*] prime = 71, exponent = 1
[*] prime = 823, exponent = 1
[*] prime = 1229, exponent = 1
[*] prime = 7489, exponent = 1
[*] prime = 30203, exponent = 1
[*] prime = 1275057701, exponent = 1
[*] prime = 13, exponent = 1
[*] prime = 19, exponent = 1
[*] prime = 179, exponent = 1
[*] prime = 13003, exponent = 1
[*] prime = 1307093479, exponent = 1
[+] HTB{1nv411d_cu2v3_4774cks_ftw!!}
Para obtener más información sobre este reto, recomiendo leer el write-up del blog de Hack The Box.
El script completo se puede encontrar aquí: solve.py.