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
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 emplea un Generador Lineal Congruencial (Linear Conguential Generator, LCG) para generar los nonces
Entonces, tenemos
Donde
Si añadimos estas relaciones al sistema de ecuaciones anterior, obtenemos un sistema de 3 ecuaciones modulares en 3 incógnitas (
Hay que tener en cuenta que estamos trabajando en módulo
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=-(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
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.