Easy DSA: Lovely Little Lane
4 minutos de lectura
Se nos proporciona el código fuente en Python utilizado para cifrar la flag:
from Crypto.Util.Padding import pad
from Crypto.Util.number import isPrime, getPrime, long_to_bytes
from Crypto.Cipher import AES
from hashlib import sha256
from random import randrange
def gen_key():
p = 0
while not isPrime(p):
q = getPrime(300)
p = 2*q + 1
g = randrange(2, p)**2 % p
x = randrange(2, q)
y = pow(g, x, p)
return p, q, g, x, y
def H(msg):
return int.from_bytes(sha256(msg).digest(), 'big')
def sign(m):
k = randrange(2, q >> 100)
r = pow(g, k, p) % q
s = (H(m) + x*r) * pow(k, -1, q) % q
return r, s
def verify(m, r, s):
assert 0 < r < q and 0 < s < q
u = pow(s, -1, q)
v = pow(g, H(m) * u, p) * pow(y, r * u, p) % p % q
return v == r
flag = b"ictf{REDACTED}"
p, q, g, x, y = gen_key()
ms = b"jctf{Puzzler_is_the_best_chall_author}", b"jctf{Wanna_see_you_trying_to_submit_that_flag}", b"jctf{D54_15_345y_4f73r_411}", b"jctf{n0_1d34}", b"jctf{s0_m4ny_fr33_s1g5}"
sigs = [sign(m) for m in ms]
assert all(verify(m, *sig) for m, sig in zip(ms, sigs))
aes = AES.new(long_to_bytes(x)[:16], AES.MODE_CBC, b'\0'*16)
c = aes.encrypt(pad(flag, 16)).hex()
print(f'{p = }\n{g = }\n{y = }\n{ms = }\n{sigs = }\n{c = }')
Y la salida del script anterior:
p = 4069937001870309288805965623396322384563730096882100588604666667233844487430163449354230919
g = 761690225239056989296458587964224591636809672476899126096331568501041989927462775870169890
y = 3856861197249284776013625513455404101895073264721385255129856925979499627575330256789520929
ms = (b'jctf{Puzzler_is_the_best_chall_author}', b'jctf{Wanna_see_you_trying_to_submit_that_flag}', b'jctf{D54_15_345y_4f73r_411}', b'jctf{n0_1d34}', b'jctf{s0_m4ny_fr33_s1g5}')
sigs = [(1234430664392743787630257388031047316821997031330839787382441766516744619882845371726433479, 883478467757628095229081460742191979896216430167019471897971078418352645136586828118018700), (1748400176200042123708476874280571916114895811026970462791925292863342243844069518123907016, 393625149677662932332357187873198135230656251678930039756678249504827719418549587156831030), (1389075138169306899495492856357153773415775002452775291705585460821530722304723598929266862, 781915465391184160994575003284903630852258678840377022165602064887288442417369465674198668), (1958157337340217176576113705810981137211234690293204330010317484823551198693733909083899867, 10566518658730065027243448201854036747278182399783616747373412863391884773803402507423867), (1502061706004805503203955848190130172580944756057566524292292418223793543600715005832239986, 1945316551688445103622226632281070969908748063265509793926846008296447432175736848474050566)]
c = '3c5f1079e0d30abf35d059ffea0ac6b460c1cd372d5622ede50df037f733015f'
Análisis del código fuente
El servidor implementa un algoritmo de firma digital (DSA) y utiliza un parámetro privado x como clave para cifrar la flag con AES:
aes = AES.new(long_to_bytes(x)[:16], AES.MODE_CBC, b'\0'*16)
c = aes.encrypt(pad(flag, 16)).hex()
Por lo tanto, necesitaremos encontrar x a partir de las firmas DSA.
Implementación del DSA
El código para el DSA es correcto (más información aquí):
- Genera números primos
y (tales que ) - Luego valores públicos
e - Y valores privados
y
Para firmar mensajes, utiliza SHA256 como función de hash y calcula lo siguiente:
Y la salida es el par
El problema de seguridad
El problema aquí es que el servidor genera nonces
k = randrange(2, q >> 100)
Dado que
El procedimiento es definir un retículo generado por las columnas de esta matriz
Donde
Una vez que apliquemos LLL, encontraremos un vector en la base reducida del retículo que contiene todos los nonces
Flag
Si reproducimos los cálculos anteriores en Python, encontraremos x y, por lo tanto, podemos descifrar el texto de cifrado con AES para encontrar la flag:
$ python3 solve.py
ictf{W34k_n0nc3,_345y_ch4LLL}
El script completo se puede encontrar aquí: solve.py.