Arranged
5 minutos de lectura
Se nos proporciona el código fuente en SageMath para cifrar la flag:
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import long_to_bytes
from hashlib import sha256
from secret import FLAG, p, b, priv_a, priv_b
F = GF(p)
E = EllipticCurve(F, [726, b])
G = E(926644437000604217447316655857202297402572559368538978912888106419470011487878351667380679323664062362524967242819810112524880301882054682462685841995367, 4856802955780604241403155772782614224057462426619061437325274365157616489963087648882578621484232159439344263863246191729458550632500259702851115715803253)
A = G * priv_a
B = G * priv_b
print(A)
print(B)
C = priv_a * B
assert C == priv_b * A
# now use it as shared secret
secret = C[0]
hash = sha256()
hash.update(long_to_bytes(secret))
key = hash.digest()[16:32]
iv = b'2__\xd9]3k\x94\x893\x1a\x7f\x93\xd5\x14\x05'
cipher = AES.new(key, AES.MODE_CBC, iv)
encrypted = cipher.encrypt(pad(FLAG, 16))
print(encrypted)
Además, tenemos la salida del script:
(6174416269259286934151093673164493189253884617479643341333149124572806980379124586263533252636111274525178176274923169261099721987218035121599399265706997 : 4355483362759117096840903200308104416093873813961514429031587444212486652000030486511593222701883061189598478367449346932543603997532721961479304197729837 : 1)
(5988601072335190267607626269694202717170383512532989213900345448657641222212196937725485374210603546742409649154478860998573202499999124529884522786776964 : 1979660325653723467116529048392433203266542286102635118367760228627475646827461168434739881080159207311102652868018376000583885500682322201011066971591840 : 1)
b'\xe3Nf1\xd4\xf7g\xad\xa6\xa4q\x8e\x85\x99\xa2/>\xb0u\x16\x1f\xc5\x1e\x8a\xf3\xd0t\xf5\xc4F\x9a\xce'
Análisis del código fuente
El servidor usa ECC para implementar un intercambio de claves de Diffie-Hellman (ECDH). Está utilizando una curva elíptica personalizada, con parámetros desconocidos $p$ y $b$ (observe que $a = 726$), por lo que
$$ E(\mathbb{F}_p): y^2 = x^3 + 726 \cdot x + b \mod{p} $$
El servidor toma un punto generador conocido $G$ y usa números privados $\mathrm{priv\_a}$ y $\mathrm{priv\_b}$ para calcular $A = \mathrm{priv\_a} \cdot G$ y $B = \mathrm{priv\_b} \cdot G$. Se nos proporcionan estos puntos $A$ y $B$ (y sabemos $G$ del código fuente).
Después de eso, el secreto compartido es solo la coordenada $\mathrm{x}$ de $C = \mathrm{priv\_a} \cdot B$, que también es igual a $\mathrm{priv\_b} \cdot A$. Así es como funciona ECDH, en términos generales.
Solución
Lo primero que debemos hacer es operar con los puntos de la curva para encontrar los parámetros de la curva $b$ y $p$.
Encontrando los parámetros de la curva
Obsérvese que ya tenemos tres puntos que se encuentran en la curva, por lo que tenemos estas tres ecuaciones:
$$ \begin{cases} (G_\mathrm{y})^2 = (G_\mathrm{x})^3 + 726 \cdot G_\mathrm{x} + b & \mod{p} \\ (A_\mathrm{y})^2 = (A_\mathrm{x})^3 + 726 \cdot A_\mathrm{x} + b & \mod{p} \\ (B_\mathrm{y})^2 = (B_\mathrm{x})^3 + 726 \cdot B_\mathrm{x} + b & \mod{p} \\ \end{cases} $$
Si restamos las tres ecuaciones para eliminar $b$, obtenemos estas dos:
$$ \begin{cases} (G_\mathrm{y})^2 - (A_\mathrm{y})^2 = (G_\mathrm{x})^3 - (A_\mathrm{x})^3 + 726 \cdot (G_\mathrm{x} - A_\mathrm{x}) & \mod{p} \\ (G_\mathrm{y})^2 - (B_\mathrm{y})^2 = (G_\mathrm{x})^3 - (B_\mathrm{x})^3 + 726 \cdot (G_\mathrm{x} - B_\mathrm{x}) & \mod{p} \\ \end{cases} $$
Si organizamos las ecuaciones, tenemos:
$$ \begin{cases} (G_\mathrm{y})^2 - (A_\mathrm{y})^2 - (G_\mathrm{x})^3 + (A_\mathrm{x})^3 - 726 \cdot (G_\mathrm{x} - A_\mathrm{x}) = 0 & \mod{p} \\ (G_\mathrm{y})^2 - (B_\mathrm{y})^2 - (G_\mathrm{x})^3 + (B_\mathrm{x})^3 - 726 \cdot (G_\mathrm{x} - B_\mathrm{x}) = 0 & \mod{p} \\ \end{cases} $$
Lo que vemos aquí es que tenemos dos resultados que son congruentes con $0 \mod{p}$, lo que significa que ambos resultados son divisibles por $p$. Como resultado, ambos resultados comparten un factor común $p$, por lo que podemos encontrar $p$ utilizando el máximo común divisor (GCD). Bueno, siendo más precisos, el GCD devolverá un múltiplo de $p$, pero esta vez es solo $p$:
$ sage -q
sage: Gx, Gy = (9266444370006042174473166558572022974025725593685389789128881064194700114878783516673806793236640623625249672428198101125248803018820546824626
....: 85841995367, 4856802955780604241403155772782614224057462426619061437325274365157616489963087648882578621484232159439344263863246191729458550632500259702
....: 851115715803253)
sage: Ax, Ay = (6174416269259286934151093673164493189253884617479643341333149124572806980379124586263533252636111274525178176274923169261099721987218035121599
....: 399265706997, 435548336275911709684090320030810441609387381396151442903158744421248665200003048651159322270188306118959847836744934693254360399753272196
....: 1479304197729837)
sage: Bx, By = (5988601072335190267607626269694202717170383512532989213900345448657641222212196937725485374210603546742409649154478860998573202499999124529884
....: 522786776964, 197966032565372346711652904839243320326654228610263511836776022862747564682746116843473988108015920731110265286801837600058388550068232220
....: 1011066971591840)
sage:
sage: a = 726
sage:
sage: p = gcd(
....: Gy ** 2 - Ay ** 2 - Gx ** 3 - a * Gx + Ax ** 3 + a * Ax,
....: Gy ** 2 - By ** 2 - Gx ** 3 - a * Gx + Bx ** 3 + a * Bx,
....: )
sage: is_prime(p)
False
Como se puede ver, el valor de p no es primo, pero es un múltiplo pequeño del número primo que estamos buscando:
sage: p
40869841224700244502552707772694043870192866604192451956598992316181984174649795098929076591403964203529570112175651477399141927360387112911853903291825198
sage: factor(p)
2 * 3 * 6811640204116707417092117962115673978365477767365408659433165386030330695774965849821512765233994033921595018695941912899856987893397852151975650548637533
sage: p = 6811640204116707417092117962115673978365477767365408659433165386030330695774965849821512765233994033921595018695941912899856987893397852151975650548
....: 637533
Ahora, es trivial encontrar $b$ con un solo punto:
$$ b = (G_\mathrm{y})^2 - (G_\mathrm{x})^3 - 726 \cdot G_\mathrm{x} \mod{p} $$
sage: b = (Gy ** 2 - Gx ** 3 - a * Gx) % p
Ahora podemos definir la curva elíptica y usar las coordenadas anteriores como puntos en la curva:
sage: E = EllipticCurve(GF(p), [a, b])
sage: G, A, B = E(Gx, Gy), E(Ax, Ay), E(Bx, By)
ECDLP
Ahora, debemos resolver el ECDLP para encontrar uno de los valores de $\mathrm{priv\_a}$ o $\mathrm{priv\_b}$. Lo primero que necesitamos es encontrar el orden de $G$, que determinará si podemos resolver el ECDLP fácilmente o no:
sage: G.order()
11
¡Oh! ¡Ese es un orden muy pequeño! Esto no es bueno para ECDH, porque significa que $11 \cdot G = O$, el “punto en el infinito” (el elemento identidad en el grupo de la curva elíptica).
Como resultado, no importa cómo de grandes sean $\mathrm{priv\_a}$ o $\mathrm{priv\_b}$, porque podemos expresar cualquiera de ellos como $\mathrm{priv\_a} = k \cdot 11 + r$, para ciertos enteros $k$ y $r$ con $0 \leqslant r < 11$.
Así,
$$ \begin{align} A & = \mathrm{priv\_a} \cdot G \\ & = (k \cdot 11 + r) \cdot G \\ & = (k \cdot 11) \cdot G + r \cdot G \\ & = k \cdot (11 \cdot G) + r \cdot G \\ & = k \cdot O + r \cdot G \\ & = O + r \cdot G \\ & = r \cdot G \end{align} $$
Lo mismo sucede con $B$, entonces podemos simplemente probar diferentes valores de $r$ (desde $0$ hasta $10$) y ver si $A$ es igual que $r \cdot G$, y lo mismo con $B$:
sage: for priv_a in range(11):
....: if priv_a * G == A:
....: break
....:
sage: for priv_b in range(11):
....: if priv_b * G == B:
....: break
....:
sage: C = priv_a * B
sage: C == priv_b * A
True
Tenemos el secreto compartido, por lo que podemos descifrar la flag con AES y la clave derivada del secreto compartido.
Flag
Aquí está la flag:
sage: from Crypto.Cipher import AES
sage: from Crypto.Util.Padding import unpad
sage: from Crypto.Util.number import long_to_bytes
sage: from hashlib import sha256
sage:
sage: secret = int(C[0])
sage:
sage: h = sha256()
sage: h.update(long_to_bytes(secret))
sage:
sage: key = h.digest()[16:32]
sage: iv = b'2__\xd9]3k\x94\x893\x1a\x7f\x93\xd5\x14\x05'
sage: cipher = AES.new(key, AES.MODE_CBC, iv)
sage:
sage: encrypted = b'\xe3Nf1\xd4\xf7g\xad\xa6\xa4q\x8e\x85\x99\xa2/>\xb0u\x16\x1f\xc5\x1e\x8a\xf3\xd0t\xf5\xc4F\x9a\xce'
sage:
sage: decrypted = unpad(cipher.decrypt(encrypted), 16)
sage: print(decrypted.decode())
HTB{ORD3R_..._0RD3R_!!!}