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
El servidor toma un punto generador conocido
Después de eso, el secreto compartido es solo la coordenada
Solución
Lo primero que debemos hacer es operar con los puntos de la curva para encontrar los parámetros de la curva
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:
Si restamos las tres ecuaciones para eliminar
Si organizamos las ecuaciones, tenemos:
Lo que vemos aquí es que tenemos dos resultados que son congruentes con
$ 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
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
sage: G.order()
11
¡Oh! ¡Ese es un orden muy pequeño! Esto no es bueno para ECDH, porque significa que
Como resultado, no importa cómo de grandes sean
Así,
Lo mismo sucede con
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_!!!}