Converging Visions
9 minutos de lectura
Se nos proporciona el código fuente del servidor en Python:
from secret import FLAG, p, a, b
from sage.all_cmdline import *
class PRNG:
def __init__(self, p, mul1, mul2):
self.mod = p * 6089788258325039501929073418355467714844813056959443481824909430411674443639248386564763122373451773381582660411059922334086996696436657009055324008041039
self.exp = 2
self.mul1 = mul1
self.mul2 = mul2
self.inc = int.from_bytes(b'Coordinates lost in space', 'big')
self.seed = randint(2, self.mod - 1)
def rotate(self):
self.seed = (self.mul1 * pow(self.seed, 3) + self.mul2 * self.seed +
self.inc) % self.mod
return self.seed, pow(self.seed, self.exp, self.mod)
class Relic:
def __init__(self, p, a, b):
self.E = EllipticCurve(GF(p), [a, b])
self.P = None
self.EP = None
self.p = p
self.prng = PRNG(p, a, b)
def setupPoints(self, x):
if x >= self.p:
return 'Coordinate greater than curve modulus'
try:
self.P = self.E.lift_x(Integer(x))
self.EP = self.P
except:
return 'Point not on curve'
return ('Point confirmed on curve', self.P[0], self.P[1])
def nextPoints(self):
seed, enc_seed = self.prng.rotate()
self.P *= seed
self.EP *= enc_seed
return ('New Points', self.EP[0], self.EP[1], self.P[0], self.P[1])
def menu():
print('Options:\n')
print('1. Setup Point')
print('2. Receive new point')
print('3. Find true point')
option = input('> ')
return option
def main():
artifact = Relic(p, a, b)
setup = False
while True:
try:
option = menu()
if option == '1':
print('Enter x coordinate')
x = int(input('x: '))
response = artifact.setupPoints(x)
if response[0] == 'Point confirmed on curve':
setup = True
print(response)
elif option == '2':
if setup:
response = artifact.nextPoints()
print('Response')
print((response[0], response[1], response[2]))
else:
print('Configure origin point first')
elif option == '3':
if setup:
print('Input x,y')
Px = int(input('x: '))
Py = int(input('y: '))
response = artifact.nextPoints()
if response[3] == Px and response[4] == Py:
print(
'You have confirmed the location. It\'s dangerous however to go alone. Take this: ',
FLAG)
else:
print('The vessels will never be found...')
exit()
else:
print('Configure origin point first')
else:
print("Invalid option, sutting down")
exit()
except Exception as e:
response = f'An error occured: {e}'
print(response)
exit()
if __name__ == '__main__':
assert p.bit_length() == 256
main()
El servidor usa Criptografía de Curva Elíptica (ECC) con parámetros secretos (p, a, b). También utiliza un generador de números pseudo-aleatorios (PRNG) personalizado con los mismos parámetros desconocidos y una cierta fórmula.
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$.
Encontrando los parámetros de la curva
En la opción 1, se nos permite ingresar un número $x$ y el servidor intentará darnos el correspondiente valor $y$ para que el punto $(x, y)$ pertenezca a la curva:
if option == '1':
print('Enter x coordinate')
x = int(input('x: '))
response = artifact.setupPoints(x)
if response[0] == 'Point confirmed on curve':
setup = True
print(response)
Sin embargo, echemos un vistazo al método setupPoints:
def setupPoints(self, x):
if x >= self.p:
return 'Coordinate greater than curve modulus'
try:
self.P = self.E.lift_x(Integer(x))
self.EP = self.P
except:
return 'Point not on curve'
return ('Point confirmed on curve', self.P[0], self.P[1])
Aquí tenemos un oráculo para encontrar $p$ usando búsqueda binaria, porque podemos probar valores de $x$ y aproximarnos a $p$ dependiendo de la respuesta ('Coordinate greater than curve modulus' vs. otro mensaje). Este es el código para encontrar $p$:
def main():
io = get_process()
left, right = 2 ** 16, 2 ** 256
m = (left + right) // 2
while left < right - 1:
m = (left + right) // 2
io.sendlineafter(b'> ', b'1')
io.sendlineafter(b'x: ', str(m).encode())
data = io.recvline()
if b'Coordinate greater than curve modulus' in data:
right = m - 1
else:
left = m + 1
p = m - 1
io.info(f'Got modulus {p = }')
Luego podemos encontrar $a$ y $b$ tomando dos puntos aleatorios de la curva (opciones 1 o 2). El proceso es el mismo que en Elliptic Labyrinth: resolver un sistema de dos ecuaciones modulares en $a$ y $b$:
points = []
x = 0
while len(points) < 2:
io.sendlineafter(b'> ', b'1')
io.sendlineafter(b'x: ', str(x).encode())
data = io.recvline()
if b'Point confirmed on curve' in data:
point = tuple(
map(int, data.decode().replace(')', '').split(', ')[1:]))
points.append(point)
x += 1
(x1, y1), (x2, y2) = points
a = (y1 ** 2 - y2 ** 2 - x1 ** 3 + x2 ** 3) * pow(x1 - x2, -1, p) % p
b = (y1 ** 2 - x1 ** 3 - a * x1) % p
io.info(f'Got parameters {a = } and {b = }')
Comprendiendo el reto
Ahora que hemos recuperado los parámetros de la curva, revisemos el reto nuevamente para ver cómo debemos capturar la flag.
En la opción 3, debemos proporcionar las coordenadas de un punto P correctamente para ver la flag (solo tenemos una oportunidad):
elif option == '3':
if setup:
print('Input x,y')
Px = int(input('x: '))
Py = int(input('y: '))
response = artifact.nextPoints()
if response[3] == Px and response[4] == Py:
print(
'You have confirmed the location. It\'s dangerous however to go alone. Take this: ',
FLAG)
else:
print('The vessels will never be found...')
exit()
else:
print('Configure origin point first')
Este punto P proviene de las dos últimas entradas de response, que es una tupla devuelta por nextPoints:
def nextPoints(self):
seed, enc_seed = self.prng.rotate()
self.P *= seed
self.EP *= enc_seed
return ('New Points', self.EP[0], self.EP[1], self.P[0], self.P[1])
Usando la opción 2 descubrimos el punto EP, cuyas coordenadas son las posiciones 1 y 2 de la tupla que devuelve nextPoints:
elif option == '2':
if setup:
response = artifact.nextPoints()
print('Response')
print((response[0], response[1], response[2]))
else:
print('Configure origin point first')
Obsérvese que podemos controlar el valor de P y EP en setupPoints, pero no sabemos los valores de seed y enc_seed. Entonces, dado que conocemos el punto $\mathrm{EP}$ y $\mathrm{enc\_seed} \cdot \mathrm{EP}$, de alguna manera debemos encontrar $\mathrm{enc\_seed}$, esto es, resolver el ECDLP.
Ataque de Smart
La clave para resolver el ECDLP es que el orden de la curva es primo (realmente, $|E(\mathbb{F}_p)| = p$). Por lo tanto, tenemos una curva anómala, que podría ser vulnerable al ataque de Smart para resolver el ECDLP fácilmente.
El ataque de Smart es un método complejo que requiere conocimiento sobre teoría de los números algebraicos, el lema de Hensel y los números $p$-ádicos. Para obtener más información, lea estos recursos (los encontré útiles para comprender el ataque desde una perspectiva de alto nivel):
- The Discrete Logarithm Problem on Elliptic Curves of Trace One
- Weak Curves In Elliptic Curve Cryptography
- Characterization of Smart-proof curves
- Hensel’s Lemma
- Número $p$-ádico
Encontré una implementación del ataque de Smart en SageMath en este write-up de un reto de CryptoHack. Usando esta implementación, podemos encontrar enc_seed:
x2 = 6
io.sendlineafter(b'> ', b'1')
io.sendlineafter(b'x: ', str(x2).encode())
E = EllipticCurve(GF(p), [a, b])
EP = E.gens()[0]
io.sendlineafter(b'> ', b'1')
io.sendlineafter(b'x: ', str(EP[0]).encode())
io.sendlineafter(b'> ', b'2')
io.recvline()
point = tuple(
map(int, io.recvline().decode().replace(')', '').split(', ')[1:]))
enc_seed_EP = E(point[0], point[1])
enc_seed = SmartAttack(EP, enc_seed_EP, p)
io.info(f'Smart Attack -> {enc_seed = }')
Analizando el PRNG
Muy bien, entonces tenemos enc_seed. Echemos un vistazo a la clase PRNG:
class PRNG:
def __init__(self, p, mul1, mul2):
self.mod = p * 6089788258325039501929073418355467714844813056959443481824909430411674443639248386564763122373451773381582660411059922334086996696436657009055324008041039
self.exp = 2
self.mul1 = mul1
self.mul2 = mul2
self.inc = int.from_bytes(b'Coordinates lost in space', 'big')
self.seed = randint(2, self.mod - 1)
def rotate(self):
self.seed = (self.mul1 * pow(self.seed, 3) + self.mul2 * self.seed +
self.inc) % self.mod
return self.seed, pow(self.seed, self.exp, self.mod)
Podemos expresar el método rotate en términos matemáticos (nótese que la clase está instanciada como self.prng = PRNG(p, a, b) en la clase Relic):
$$ s_{j + 1} = a s_j^3 + b s_j + i \mod{p q} $$
Entonces, $\mathrm{enc\_seed} = s_{j + 1}^2 \mod{p q}$. Curiosamente, la fórmula se parece a otra curva elíptica.
Los números pseudo-aleatorios $s_j$ están considerados $\mod{p q}$. Sin embargo, al multiplicar estos números por un punto de la curva elíptica, se reducirán $\mod{p}$, porque la curva está definida sobre $\mathbb{F}_p$. Por lo tanto, la fórmula del PRNG puede considerarse solo $\mod{p}$.
Como sabemos $\mathrm{enc\_seed}$ del ataque de Smart, podemos calcular la raíz cuadrada $\mod{p}$ (no $\mod{p q}$ por la explicación anterior). Una vez que tenemos la semilla $s_{j + 1}$, podremos calcular $s_{j + 2}$ aplicando la fórmula y predecir la salida de nextPoints, de manera que podamos encontrar la flag. Esta es la implementación:
seed = int(GF(p)(enc_seed).nth_root(2))
i = int.from_bytes(b'Coordinates lost in space', 'big')
next_seed = (a * pow(seed, 3) + b * seed + i) % p
curr_P = EP * seed
next_P = curr_P * next_seed
io.info(f'Trying next point {next_P}...')
io.sendlineafter(b'> ', b'3')
io.sendlineafter(b'x: ', str(next_P[0]).encode())
io.sendlineafter(b'y: ', str(next_P[1]).encode())
io.success(io.recv().decode())
Flag
Si ejecutamos el script, veremos la flag:
$ python3 solve.py 209.97.134.50:31201
[+] Opening connection to 209.97.134.50 on port 31201: Done
[*] Got modulus p = 91720173941422125335466921700213991383508377854521057423162397714341988797837
[*] Got parameters a = 57186237363769678415558546920636910250184560730836527033755705455333464722170 and b = 47572366756434660406002599832623767973471965640106574131304711893212728437629
[*] Smart Attack -> enc_seed = 1574017221831123415886137346110982781503978446261518027146689940530621647822
[*] Trying next point (49394339834628750389338231331407606443777974829314059591423185069522974190491 : 36805735502973307035372435592237049388682732097929498134528467141686272904173 : 1)...
[+] You have confirmed the location. It's dangerous however to go alone. Take this: HTB{0Racl3_AS_a_f3A7Ur3_0n_W3aK_CURV3_aND_PRN9??_7H3_s3cur17Y_0F_0uR_CRyP70Sys73M_w1LL_c0LLAp53!!!}
[*] Closed connection to 209.97.134.50 port 31201
El script completo se puede encontrar aquí: solve.py.