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 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 tenemos dos mensajes diferentes firmados con el mismo valor nonce . En DSA, el valor nonce debe usarse solo una vez. De lo contrario, podemos encontrar el valor privado y firmar nuestros propios mensajes.

Entonces, tenemos un mensaje con firma y mensaje con firma . Obsérvese que porque , y es el mismo para ambas firmas.

Por lo tanto, tenemos

Si restamos ambas ecuaciones, obtenemos

Y así podemos encontrar como sigue

Luego . Y una vez que tenemos , somos capaces de obtener :

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!!!}'