Easy DSA: Elated once
8 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 H(msg):
return int.from_bytes(sha256(msg).digest(), 'big')
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 gen_nonces():
a = randrange(2, q)
b = randrange(2, q)
k = 0
while 1:
k = (a*k + b) % q
yield k
def sign(m):
k = next(nonces)
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()
nonces = gen_nonces()
ms = b'jctf{f4k3_f!4g_7h3_f1r57}', b'jctf{f4k3_f!4g_7h3_53c0nd}', b'jctf{f4k3_f!4g_7h3_7h1rd}'
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 = 2418412161587048618911490514475907960012278945420538846001723790372197085472346428648374919
g = 2064228484934656182476030526252687681657855524182393204180796682805474532697783234019522938
y = 894978350337386203714743526086207453830598544444498469056621877210054843512079994718204008
ms = (b'jctf{f4k3_f!4g_7h3_f1r57}', b'jctf{f4k3_f!4g_7h3_53c0nd}', b'jctf{f4k3_f!4g_7h3_7h1rd}')
sigs = [(942248975683680318753150798164591935683431794761521087381578596465811760180113404300321118, 342812233069446068155480770741216218496427109436740920046532418711028275917065308430519273), (102001584770818641493080724572692756389337862746330230381962190229233871531362789283064508, 482354383195776716833349859090850583242412163611214463003633128285976770958780493119871011), (187377473811032611481162139226326301755478417757273410261128557099065854699728324076093828, 1171449558094661271371246349171199670184901923277811515634255397001853557943612820379515494)]
c = '4c76bd5dc8d57984526385d696fa0665e4c18f60b8593d42897aff792ec893d826c253646b9cb6875c91f2dfa25eedd4cc2936a3fe3174aa5b677a30ef965a7aa5dbf12c0c8234a73d0c5db5aea76644'
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 emplea un Generador Lineal Congruencial (Linear Conguential Generator, LCG) para generar los nonces $k$ y nos dan tres mensajes distintos con sus firmas y la semilla del LCG.
Entonces, tenemos
$$ \begin{cases} s_1 k_1 - r_1 x = h_1 \mod{q} \\ s_2 k_2 - r_2 x = h_2 \mod{q} \\ s_3 k_3 - r_3 x = h_3 \mod{q} \\ \end{cases} $$
Donde $h_i = \mathrm{SHA256}{(m_i)}$. Y los nonces son:
$$ \begin{cases} k_0 & = 0 \\ k_1 & = a k_0 + b = b & \mod{q} \\ k_2 & = a k_1 + b = ab + b & \mod{q} \\ k_3 & = a k_2 + b = a^2 b + ab + b & \mod{q} \\ \end{cases} $$
Si añadimos estas relaciones al sistema de ecuaciones anterior, obtenemos un sistema de 3 ecuaciones modulares en 3 incógnitas ($x$, $a$, $b$):
$$ \begin{cases} s_1 b & - r_1 x = h_1 \mod{q} \\ s_2 (ab + b) & - r_2 x = h_2 \mod{q} \\ s_3 (a^2 b + ab + b) & - r_3 x = h_3 \mod{q} \\ \end{cases} $$
Hay que tener en cuenta que estamos trabajando en módulo $q$, que es un número primo, por lo que todas las operaciones están dentro de $\mathbb {F}_q$. Como este es un cuerpo, podemos “sumar, restar, multiplicar y dividir”. Por lo tanto, podemos resolver el sistema de ecuaciones utilizando matemáticas simbólicas sin tener en cuenta el módulo y luego aplicar operaciones con módulo $q$.
Usando Maxima, obtenemos estas expresiones:
$ maxima
Maxima 5.46.0 https://maxima.sourceforge.io
usando Lisp SBCL 2.3.0
Distribuido bajo la Licencia Pública GNU. Consulte el fichero de DERECHO DE REPRODUCCIÓN.
Dedicado a la memoria de William Schelter.
La función bug_report() proporciona informes de defectos.
(%i1) solve([s1 * b - r1 * x = h1, s2 * (a * b + b) - r2 * x = h2, s3 * (a^2 * b + a * b + b) - r3 * x = h3], [x, a, b]);
2 2 2 2 2
(%o1) [[x = - (s1 s2 sqrt(((- 3 h1 r2 ) + 6 h1 h2 r1 r2 - 3 h2 r1 ) s3
2 2
+ (((2 h1 r2 - 2 h1 h2 r1) r3 - 2 h1 h3 r1 r2 + 2 h2 h3 r1 ) s2
2 2
+ ((4 h2 r1 - 4 h1 h2 r2) r3 + 4 h1 h3 r2 - 4 h2 h3 r1 r2) s1) s3
2 2 2 2 2
+ (h1 r3 - 2 h1 h3 r1 r3 + h3 r1 ) s2 )
2 2
+ (2 h1 r1 s2 + ((- h1 r2) - h2 r1) s1 s2 + 2 h2 r2 s1 ) s3
2 2 2 2 2
+ ((- h1 r3) - h3 r1) s1 s2 )/((2 r1 s2 - 2 r1 r2 s1 s2 + 2 r2 s1 ) s3
2 2 2 2 2 2
- 2 r1 r3 s1 s2 ), a = - (sqrt(((- 3 h1 r2 ) + 6 h1 h2 r1 r2 - 3 h2 r1 ) s3
2 2
+ (((2 h1 r2 - 2 h1 h2 r1) r3 - 2 h1 h3 r1 r2 + 2 h2 h3 r1 ) s2
2 2
+ ((4 h2 r1 - 4 h1 h2 r2) r3 + 4 h1 h3 r2 - 4 h2 h3 r1 r2) s1) s3
2 2 2 2 2
+ (h1 r3 - 2 h1 h3 r1 r3 + h3 r1 ) s2 ) + (h1 r2 - h2 r1) s3
+ (h3 r1 - h1 r3) s2)/((2 h1 r2 - 2 h2 r1) s3),
2 2 2 2 2
b = - (r1 s2 sqrt(((- 3 h1 r2 ) + 6 h1 h2 r1 r2 - 3 h2 r1 ) s3
2 2
+ (((2 h1 r2 - 2 h1 h2 r1) r3 - 2 h1 h3 r1 r2 + 2 h2 h3 r1 ) s2
2 2
+ ((4 h2 r1 - 4 h1 h2 r2) r3 + 4 h1 h3 r2 - 4 h2 h3 r1 r2) s1) s3
2 2 2 2 2
+ (h1 r3 - 2 h1 h3 r1 r3 + h3 r1 ) s2 )
2 2
+ ((h1 r1 r2 - h2 r1 ) s2 + (2 h2 r1 r2 - 2 h1 r2 ) s1) s3
2 2 2 2 2 2
+ (h1 r1 r3 - h3 r1 ) s2 )/((2 r1 s2 - 2 r1 r2 s1 s2 + 2 r2 s1 ) s3
2 2 2
- 2 r1 r3 s1 s2 )], [x = (s1 s2 sqrt(((- 3 h1 r2 ) + 6 h1 h2 r1 r2
2 2 2 2 2
- 3 h2 r1 ) s3 + (((2 h1 r2 - 2 h1 h2 r1) r3 - 2 h1 h3 r1 r2 + 2 h2 h3 r1 )
2 2
s2 + ((4 h2 r1 - 4 h1 h2 r2) r3 + 4 h1 h3 r2 - 4 h2 h3 r1 r2) s1) s3
2 2 2 2 2
+ (h1 r3 - 2 h1 h3 r1 r3 + h3 r1 ) s2 )
2 2
+ ((- 2 h1 r1 s2 ) + (h1 r2 + h2 r1) s1 s2 - 2 h2 r2 s1 ) s3
2 2 2 2 2
+ (h1 r3 + h3 r1) s1 s2 )/((2 r1 s2 - 2 r1 r2 s1 s2 + 2 r2 s1 ) s3
2 2 2 2 2 2
- 2 r1 r3 s1 s2 ), a = (sqrt(((- 3 h1 r2 ) + 6 h1 h2 r1 r2 - 3 h2 r1 ) s3
2 2
+ (((2 h1 r2 - 2 h1 h2 r1) r3 - 2 h1 h3 r1 r2 + 2 h2 h3 r1 ) s2
2 2
+ ((4 h2 r1 - 4 h1 h2 r2) r3 + 4 h1 h3 r2 - 4 h2 h3 r1 r2) s1) s3
2 2 2 2 2
+ (h1 r3 - 2 h1 h3 r1 r3 + h3 r1 ) s2 ) + (h2 r1 - h1 r2) s3
+ (h1 r3 - h3 r1) s2)/((2 h1 r2 - 2 h2 r1) s3),
2 2 2 2 2
b = (r1 s2 sqrt(((- 3 h1 r2 ) + 6 h1 h2 r1 r2 - 3 h2 r1 ) s3
2 2
+ (((2 h1 r2 - 2 h1 h2 r1) r3 - 2 h1 h3 r1 r2 + 2 h2 h3 r1 ) s2
2 2
+ ((4 h2 r1 - 4 h1 h2 r2) r3 + 4 h1 h3 r2 - 4 h2 h3 r1 r2) s1) s3
2 2 2 2 2
+ (h1 r3 - 2 h1 h3 r1 r3 + h3 r1 ) s2 )
2 2
+ ((h2 r1 - h1 r1 r2) s2 + (2 h1 r2 - 2 h2 r1 r2) s1) s3
2 2 2 2 2 2
+ (h3 r1 - h1 r1 r3) s2 )/((2 r1 s2 - 2 r1 r2 s1 s2 + 2 r2 s1 ) s3
2
- 2 r1 r3 s1 s2 )]]
Traducimos la expresión de $x$ a código Python (no nos importan ni $a$ ni $b$):
x=-(s1*s2*sqrt((-3*pow(h1,2,q)*pow(r2,2,q)+6*h1*h2*r1*r2-3*pow(h2,2,q)*pow(r1,2,q))*pow(s3,2,q)+(((2*pow(h1,2,q)*r2-2*h1*h2*r1)*r3-2*h1*h3*r1*r2+2*h2*h3*pow(r1,2,q))*s2+((4*pow(h2,2,q)*r1-4*h1*h2*r2)*r3+4*h1*h3*pow(r2,2,q)-4*h2*h3*r1*r2)*s1)*s3+(pow(h1,2,q)*pow(r3,2,q)-2*h1*h3*r1*r3+pow(h3,2,q)*pow(r1,2,q))*pow(s2,2,q))+(2*h1*r1*pow(s2,2,q)+(-h1*r2-h2*r1)*s1*s2+2*h2*r2*pow(s1,2,q))*s3+(-h1*r3-h3*r1)*s1*pow(s2,2,q))/((2*pow(r1,2,q)*pow(s2,2,q)-2*r1*r2*s1*s2+2*pow(r2,2,q)*pow(s1,2,q))*s3-2*r1*r3*s1*pow(s2,2,q))
Hemos cambiado todas las potencias a potencia con módulo. Ahora, necesitamos cambiar la división por una multiplicación por el inverso módulo $q$:
x=-(s1*s2*sqrt((-3*pow(h1,2,q)*pow(r2,2,q)+6*h1*h2*r1*r2-3*pow(h2,2,q)*pow(r1,2,q))*pow(s3,2,q)+(((2*pow(h1,2,q)*r2-2*h1*h2*r1)*r3-2*h1*h3*r1*r2+2*h2*h3*pow(r1,2,q))*s2+((4*pow(h2,2,q)*r1-4*h1*h2*r2)*r3+4*h1*h3*pow(r2,2,q)-4*h2*h3*r1*r2)*s1)*s3+(pow(h1,2,q)*pow(r3,2,q)-2*h1*h3*r1*r3+pow(h3,2,q)*pow(r1,2,q))*pow(s2,2,q))+(2*h1*r1*pow(s2,2,q)+(-h1*r2-h2*r1)*s1*s2+2*h2*r2*pow(s1,2,q))*s3+(-h1*r3-h3*r1)*s1*pow(s2,2,q))*pow(((2*pow(r1,2,q)*pow(s2,2,q)-2*r1*r2*s1*s2+2*pow(r2,2,q)*pow(s1,2,q))*s3-2*r1*r3*s1*pow(s2,2,q)),-1,q)
Finalmente, la raíz cuadrada se puede implementar utilizando el Algoritmo de Cipolla, y ya tenemos todo.
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{P!3453_53r10u5!y_570p_u51ng_57r4ng3_w4y5_70_g3n3r473_n0nc35}
El script completo se puede encontrar aquí: solve.py.