Easy DSA: The beginning
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
k = randrange(2, q)
x = randrange(2, q)
y = pow(g, x, p)
return p, q, g, x, y, k
def H(msg):
return int.from_bytes(sha256(msg).digest(), 'big')
def sign(m):
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, k = gen_key()
ms = b"jctf{powered_by_caffeine}", b"jctf{totally_real_flag}"
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 = 2187927460624367866053138955407692648682473743053236246707558906253741042480006602164664427
g = 375559713231366027661456501312210678588547344177468345614581736759352578046940519482449005
y = 1485107098193369513854775432342726913250546508148678604594096036026212707003506931382110518
ms = (b'jctf{powered_by_caffeine}', b'jctf{totally_real_flag}')
sigs = [(584760320483109456978677291524162809623560744424005784846002481292183647634857441612413242, 43566017108108194938809536454030127793515021629016835721136006757000695802735201944729583), (584760320483109456978677291524162809623560744424005784846002481292183647634857441612413242, 587754055422977160798386807229397695762555861352726788417293238718373985110611538922057038)]
c = '614585db552484e4c81c4168afa8582bd975bfadd5edc8a4d1bf744c29a7d84f30cde5fe4b37f736af3f09480bcb626a'
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 tenemos dos mensajes diferentes firmados con el mismo valor nonce $k$. En DSA, el valor nonce $k$ debe usarse solo una vez. De lo contrario, podemos encontrar el valor privado $x$ y firmar nuestros propios mensajes.
Entonces, tenemos un mensaje $m_1$ con firma $(r_1, s_1)$ y mensaje $m_2$ con firma $(r_2, s_2)$. Obsérvese que $r_1 = r_2$ porque $r = g^k \mod{q}$, y $k$ es el mismo para ambas firmas.
Por lo tanto, tenemos
$$ \begin{cases} s_1 = \left(\mathrm{SHA256}{(m_1)} + x \cdot r\right) \cdot k^{-1} \mod{q} \\ s_2 = \left(\mathrm{SHA256}{(m_2)} + x \cdot r\right) \cdot k^{-1} \mod{q} \end{cases} $$
Si restamos ambas ecuaciones, obtenemos
$$ s_1 - s_2 = \left(\mathrm{SHA256}{(m_1)} - \mathrm{SHA256}{(m_2)}\right) \cdot k^{-1} \mod{q} $$
Y así podemos encontrar $k^{-1}$ como sigue
$$ k^{-1} = (s_1 - s_2) \cdot \left(\mathrm{SHA256}{(m_1)} - \mathrm{SHA256}{(m_2)}\right)^{-1} \mod{q} $$
Luego $k = \left(k^{-1}\right)^{-1} \mod{q}$. Y una vez que tenemos $k$, somos capaces de obtener $x$:
$$ x = \left(s_1 \cdot k - \mathrm{SHA256}{(m_1)}\right) \cdot r^{-1} \mod{q} $$
Flag
Si reproducimos los cálculos anteriores en Python, encontraremos x y, por lo tanto, podemos descifrar el texto cifrado con AES para encontrar la flag:
$ python3 -q
>>> from Crypto.Cipher import AES
>>> from Crypto.Util.number import long_to_bytes
>>> from Crypto.Util.Padding import unpad
>>> from hashlib import sha256
>>>
>>> def H(msg):
... return int.from_bytes(sha256(msg).digest(), 'big')
...
>>>
>>> p = 2187927460624367866053138955407692648682473743053236246707558906253741042480006602164664427
>>> g = 375559713231366027661456501312210678588547344177468345614581736759352578046940519482449005
>>> y = 1485107098193369513854775432342726913250546508148678604594096036026212707003506931382110518
>>> ms = (b'jctf{powered_by_caffeine}', b'jctf{totally_real_flag}')
>>> sigs = [(584760320483109456978677291524162809623560744424005784846002481292183647634857441612413242, 43566017108108194938809536454030127793515021629016835721136006757000695802735201944729583), (584760320483109456978677291524162809623560744424005784846002481292183647634857441612413242, 587754055422977160798386807229397695762555861352726788417293238718373985110611538922057038)]
>>> c = '614585db552484e4c81c4168afa8582bd975bfadd5edc8a4d1bf744c29a7d84f30cde5fe4b37f736af3f09480bcb626a'
>>>
>>> q = (p - 1) // 2
>>> r = sigs[0][0]
>>> s1, s2 = sigs[0][1], sigs[1][1]
>>> H1, H2 = H(ms[0]), H(ms[1])
>>>
>>> k_inv = (s1 - s2) * pow(H1 - H2, -1, q) % q
>>> k = pow(k_inv, -1, q)
>>> x = (s1 * k - H1) * pow(r, -1, q) % q
>>>
>>> aes = AES.new(long_to_bytes(x)[:16], AES.MODE_CBC, b'\0'*16)
>>> unpad(aes.decrypt(bytes.fromhex(c)), 16)
b'ictf{4_n0nc3_5h0u!d_0n!y_b3_u53d_0NC3!!!}'