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 $p$ y $q$ (tales que $p = 2q + 1$)
- Luego valores públicos $g$ e $y$
- Y valores privados $k$ y $x$
Para firmar mensajes, utiliza SHA256 como función de hash y calcula lo siguiente:
$$ r = g^k \mod{q} $$
$$ s = \left(\mathrm{SHA256}{(m)} + x \cdot r\right) \cdot k^{-1} \mod{q} $$
Y la salida es el par $(r, s)$.
El problema de seguridad
El problema aquí es que el servidor genera nonces $k$ de una manera extraña:
k = randrange(2, q >> 100)
Dado que $q$ es un número primo de 300 bits y los nonces $k$ son números de 200 bits, podemos usar un ataque basado en retículo (lattice) y LLL para resolver el Hidden Number Problem. Encontré esta técnica en esta página web, que referencia a la sección 4 de este artículo.
El procedimiento es definir un retículo generado por las columnas de esta matriz $M$:
$$ M = \begin{pmatrix} q & 0 & 0 & 0 & 0 & r_1 s_1^{-1} & h_1 s_1^{-1} \\ 0 & q & 0 & 0 & 0 & r_2 s_2^{-1} & h_2 s_2^{-1} \\ 0 & 0 & q & 0 & 0 & r_3 s_3^{-1} & h_3 s_3^{-1} \\ 0 & 0 & 0 & q & 0 & r_4 s_4^{-1} & h_4 s_4^{-1} \\ 0 & 0 & 0 & 0 & q & r_5 s_5^{-1} & h_5 s_5^{-1} \\ 0 & 0 & 0 & 0 & 0 & X / q & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & q \\ \end{pmatrix} $$
Donde $h_i = \mathrm{SHA256}{(m_i)}$ y $X$ es una cota superior para los nonces $k$ (por ejemplo, $2^{200}$).
Una vez que apliquemos LLL, encontraremos un vector en la base reducida del retículo que contiene todos los nonces $k$, por lo que podremos encontrar la clave privada y descifrar la flag.
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.