Elliptic Labyrinth
6 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 secret import FLAG
class ECC:
def __init__(self, bits):
while True:
self.p = getPrime(bits)
if self.p % 4 == 3:
break
self.a = randint(1, self.p)
self.b = randint(1, self.p)
def gen_random_point(self):
x = randint(2, self.p-2)
return (x, pow(x**3 + self.a*x + self.b, (self.p+1)//4, self.p))
def menu():
print("1. Get path parameters")
print("2. Try to exit the labyrinth")
option = input("> ")
return option
def main():
ec = ECC(512)
A = ec.gen_random_point()
print("This is your lucky point:")
print(json.dumps({'x': hex(A[0]), 'y': hex(A[1])}))
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':
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
Solo tenemos la opción 1, que muestra el número primo $p$ y los bits más significativos de $a$ y $b$:
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)
}))
La opción 2 utiliza $\mathrm{key} = \mathrm{SHA256}\left(a^b \mod{p}\right))$ como clave AES para cifrar la flag:
elif choice == '2':
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()
}))
Entonces, el objetivo es encontrar los parámetros $a$ y $b$ dado un solo punto de la curva, $p$ y los bits más significativos de $a$ y $b$.
Método de Coppersmith
Pongamos la información que tenemos en términos matemáticos. Definimos $a_H$ y $b_H$ como los bits más significativos de $a$ y $b$, respectivamente. Por lo tanto, sabemos que $a = 2^r a_H + a_L$ y $b = 2^r b_H + b_L$ para algunos $170 \leqslant r \leqslant 340$. Si podemos encontrar $r$, $a_L$ y $b_L$, podremos encontrar $a$ y $b$.
La única ecuación que podemos usar es la ecuación de la curva:
$$ y^2 = x^3 + ax + b \mod{p} $$
Sustituyendo $a$ y $b$ obtenemos:
$$ y^2 = x^3 + (2^r a_H + a_L) x + 2^r b_H + b_L \mod{p} $$
Obsérvese que las incógnitas son principalmente $a_L$ y $b_L$ (podemos hacer un ataque de fuerza bruta en $r$ si fuera necesario).
Por lo tanto, podemos definir un polinomio $P(t, z)$ que satisface que $P(a_L, b_L) = 0 \mod{p}$:
$$ P(t, z) = xt + z - (y^2 + x^3 + 2^r a_H + 2^r b_H) $$
Como sucedía en Bank-er-smith, cuando se conocen los bits más significativos de un número, un método típico para aplicar es Coppersmith (que utiliza reducción de retículo mediante LLL por detrás). Esta vez, el problema es que tenemos un polinomio de dos variables. Pero hay implementaciones de métodos de Coppersmith para polinomios de varias variables.
Encontrar una implementación
Las implementaciones más utilizadas son defund y ubuntor. Sin embargo, no logré que funcionaran correctamente.
Al final, encontré este Gist de GitHub con otra implementación del método de Coppersmith para polinomios de dos variables que funcionaba la mayoría de las veces.
Implementación en Python
Luego, solo tenemos que recopilar la información del reto y aplicar el método de Coppersmith tratando de adivinar $r$ (podemos hacer un poco de fuerza bruta):
def main():
io = get_process()
io.recvline()
data = json.loads(io.recvline().decode())
x_p, y_p = int(data['x'], 16), int(data['y'], 16)
io.sendlineafter(b'> ', b'2')
data = json.loads(io.recvline().decode())
iv, enc = bytes.fromhex(data['iv']), bytes.fromhex(data['enc'])
a_highs, b_highs = [], []
for _ in range(50):
io.sendlineafter(b'> ', b'1')
data = json.loads(io.recvline().decode())
p = int(data['p'], 16)
a_highs.append(int(data['a'], 16))
b_highs.append(int(data['b'], 16))
aH, bH = sorted(a_highs)[-1], sorted(b_highs)[-1]
r_mean = 512 - aH.bit_length()
found = False
for r in range(r_mean - 5, r_mean + 5):
PR = PolynomialRing(Zmod(p), names='x,y')
x, y = PR.gens()
S = y_p ** 2 - x_p ** 3 - (aH << r) * x_p - (bH << r)
pol = x_p * x + y - S
try:
aL, bL = bivariate(pol, 2 ** r, 2 ** r)
a, b = int(aL + (aH << r)), int(bL + (bH << r))
if (y_p ** 2 - x_p ** 3 - a * x_p - b) % p == 0:
found = True
break
except IndexError:
pass
if found:
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())
else:
io.failure('Not found')
Observe que recopilo algunos valores por $a_H$ y $b_H$ y elijo los que son más grandes, por lo que es más probable que el método de Coppersmith tenga éxito.
Flag
Al ejecutar el script, fallará algunas veces, pero eventualmente tendrá éxito:
$ python3 solve.py 138.68.166.146:32398
[+] Opening connection to 138.68.166.146 on port 32398: Done
[-] Not found
[*] Closed connection to 138.68.166.146 port 32398
$ python3 solve.py 138.68.166.146:32398
[+] Opening connection to 138.68.166.146 on port 32398: Done
[+] HTB{w3_h0p3_th1s_0n3_h3lp3d_y0u_und3rst4nd_sm411_r00ts}
[*] Closed connection to 138.68.166.146 port 32398
El script completo se puede encontrar aquí: solve.py.