Elliptic Labyrinth
5 minutos de lectura
Se nos proporciona el código fuente del servidor en Python:
import os, json
from hashlib import sha256
from random import randint
from Crypto.Util.number import getPrime, long_to_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from sage.all_cmdline import *
from secret import FLAG
class ECC:
def __init__(self, bits):
self.p = getPrime(bits)
self.a = randint(1, self.p)
self.b = randint(1, self.p)
def gen_random_point(self):
return EllipticCurve(GF(self.p), [self.a, self.b]).random_point()
def menu():
print("1. Get parameters of path")
print("2. Get point in path")
print("3. Try to exit the labyrinth")
option = input("> ")
return option
def main():
ec = ECC(512)
while True:
choice = menu()
if choice == '1':
r = randint(ec.p.bit_length() // 3, 2 * ec.p.bit_length() // 3)
print(
json.dumps({
'p': hex(ec.p),
'a': hex(ec.a >> r),
'b': hex(ec.b >> r)
}))
elif choice == '2':
A = ec.gen_random_point()
print(json.dumps({'x': hex(A[0]), 'y': hex(A[1])}))
elif choice == '3':
iv = os.urandom(16)
key = sha256(long_to_bytes(pow(ec.a, ec.b, ec.p))).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = pad(FLAG, 16)
print(
json.dumps({
'iv': iv.hex(),
'enc': cipher.encrypt(flag).hex()
}))
else:
print('Bye.')
exit()
if __name__ == '__main__':
main()
El servidor utiliza criptografía de curva elíptica (ECC), pero solo genera una curva y usa los parámetros de curva para generar una clave AES para cifrar la flag (por lo que ECC no se usa para el cifrado).
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)
Dado que ECC no se usa para cifrar información, dejaré la explicación aquí.
Encontrando los parámetros de la curva
El servidor muestra información sobre los parámetros de la curva con la opción 1:
if choice == '1':
r = randint(ec.p.bit_length() // 3, 2 * ec.p.bit_length() // 3)
print(
json.dumps({
'p': hex(ec.p),
'a': hex(ec.a >> r),
'b': hex(ec.b >> r)
}))
Por ejemplo, ya tenemos el valor de $p$, y también los bits más significativos de $a$ y $b$. La vía intencionada de encontrar $a$ y $b$ y, por lo tanto, resolver el reto es usar esta información. Cubriré la solución intencionada en Elliptic Labyrinth Revenge.
Existe la opción 2, que nos proporciona puntos aleatorios de la curva:
elif choice == '2':
A = ec.gen_random_point()
print(json.dumps({'x': hex(A[0]), 'y': hex(A[1])}))
La opción restante imprime la flag cifrada con AES y la clave $\mathrm{key} = \mathrm{SHA256}\left(a^b \mod{p}\right))$:
elif choice == '3':
iv = os.urandom(16)
key = sha256(long_to_bytes(pow(ec.a, ec.b, ec.p))).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = pad(FLAG, 16)
print(
json.dumps({
'iv': iv.hex(),
'enc': cipher.encrypt(flag).hex()
}))
Solución
Tener la capacidad de solicitar puntos aleatorios de la curva, podemos obtener dos de ellos (digamos $(x_1, y_1)$ y $(x_2, y_2)$) y emplear un sistema de ecuaciones para encontrar $a$ y $b$ porque:
$$ \begin{cases} y_1^2 = x_1^3 + a x_1 + b \mod{p} \\ y_2^2 = x_2^3 + a x_2 + b \mod{p} \\ \end{cases} $$
Restando ambas ecuaciones, tenemos:
$$ y_1^2 - y_2^2 = x_1^3 - x_2^3 + a (x_1 - x_2) \mod{p} $$
Entonces, podemos despejar $a$:
$$ a = (y_1^2 - y_2^2 - x_1^3 + x_2^3) \cdot (x_1 - x_2)^{-1} \mod{p} $$
Y luego es trivial encontrar $b$:
$$ b = y_1^2 - x_1^3 - a x_1 \mod{p} $$
Implementación en Python
El procedimiento anterior se programa en Python de la siguiente manera:
def main():
host, port = sys.argv[1].split(':')
io = remote(host, port)
io.sendlineafter(b'> ', b'1')
data = json.loads(io.recvline().decode())
p = int(data['p'], 16)
io.sendlineafter(b'> ', b'2')
data = json.loads(io.recvline().decode())
x1, y1 = int(data['x'], 16), int(data['y'], 16)
io.sendlineafter(b'> ', b'2')
data = json.loads(io.recvline().decode())
x2, y2 = int(data['x'], 16), int(data['y'], 16)
a = (y1 ** 2 - y2 ** 2 - x1 ** 3 + x2 ** 3) * pow(x1 - x2, -1, p) % p
b = (y1 ** 2 - x1 ** 3 - a * x1) % p
io.sendlineafter(b'> ', b'3')
data = json.loads(io.recvline().decode())
iv, enc = bytes.fromhex(data['iv']), bytes.fromhex(data['enc'])
key = sha256(long_to_bytes(pow(a, b, p))).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, iv)
io.success(unpad(cipher.decrypt(enc), 16).decode())
Flag
Si lo ejecutamos, encontraremos la flag (el mensaje se refiere a la vía intencionada, que está cubierta en Elliptic Labyrinth Revenge):
$ python3 solve.py 167.71.143.44:32580
[+] Opening connection to 167.71.143.44 on port 32580: Done
[+] HTB{d3fund_s4v3s_th3_d4y!}
[*] Closed connection to 167.71.143.44 port 32580
El script completo se puede encontrar aquí: solve.py.