Solución a #EquinoxRoom111: ¿Te atreves a descifrar estos archivos secuestrados?

lunes, 8 de abril de 2019

Por fin nos han ayudado a recuperar nuestros ficheros. Vamos a explicar qué hemos hecho y cómo ha sido solucionado (desde diferentes perspectivas). La seguridad en la criptografía asimétrica ,usando claves RSA, se basa en la premisa de que es muy difícil computacionalmente factorizar los dos factores primos de un número. Multiplicar dos números primos p y q para obtener n es una operación sencilla y su complejidad no aumenta drásticamente cuando los números crecen:

1736640013 x 1230300287 = 2136588706409583731

En cambio, la operación inversa, dado un número n obtener sus dos factores primos es una operación que se vuelve computacionalmente inviable cuando los números involucrados son lo suficientemente grandes.

? x ? = 2136588706409583731

Para generar la pareja de claves, el algoritmo RSA crea una clave pública y privada usando este concepto. Simplificando la generación de las claves, los números primos elegidos aleatoriamente p y q se multiplican para crear el módulo n que se usará tanto en la clave privada como en la pública. Este módulo n es público pero los factores primos p y q no.

Del certificado incluido en los ficheros, podemos leer la clave pública y
obtener el módulo y exponente:
openssl x509 -in Certificate1 -text > Certificate1.info
openssl x509 -in Certificate2 -text > Certificate2.info

Se obtiene fácil el exponente (e) 65537 y el módulo (n) en hexadecimal. También así:


Intentar obtener la clave privada a partir de estos datos requeriría factorizar el módulo obtenido y así obtener los primos p y q usados para generar ambas claves. Esta operación, con un número tan grande, no es viable computacionalmente en un periodo de tiempo razonable. En este caso, tenemos una pista que nos puede ayudar a intentar encontrar esos dos números. Sabemos que el ransomware se ha ejecutado en máquinas cuyo generador de números aleatorios estaba configurado al mínimo lo que puede haber dado a repeticiones de números primos durante distintas generaciones. Por lo tanto se podría haber dado el caso en el que dos módulos compartan el mismo número p o q.

n1 = p1 x q1
n2 = p1 x q2

Si este caso se produce, ambos módulos n1 y n2 compartirían un divisor común p1. Para probar esta hipótesis se puede realizar una operación matemática muy sencilla, el cálculo del máximo común divisor usando el algoritmo de Euclides. El resultado de calcular el MCD sobre los dos módulos obtenidos de las claves públicas revela que ambos números comparten un divisor distinto de 1. Con este cálculo sencillo se consigue uno de los dos primos usados para la generación de ambas claves, conseguir los otros dos primos desconocidos es trivial (mucho ojo a la necesidad de utilizar doble barra para división de números grandes). En Python es sencillo así:


Para el cálculo del MCD se pueden usar herramientas como RSACtfTool, o Sanity Cheker, basado en SageMath, y en general, para cálculos rápidos con números enormes, existen diferentes páginas que se pueden consultar, como este ejemplo. Siguiendo cualquier manual de RSA, sacamos todos los datos se debe construir la clave privada a partir de dos primos y el exponente.


Tenemos la opción de hacerlo a través de openssl. Primero creamos un archivo con la información:

asn1=SEQUENCE:rsa_key
[rsa_key]
version=INTEGER:0
modulus=INTEGER:0xD1F50CC7F…
pubExp=INTEGER:0x10001
privExp=INTEGER:0x2396DB3CC6CB….
p=INTEGER:0x00e95df998acf149cae5d….
q=INTEGER:0x00e651db2d769829da0…
e1=INTEGER:0x6E2FD10A259E481965….
e2=INTEGER:0x782436DA8E446D80669…
coeff=INTEGER:0xA70D92326A2813D9F….

Y luego se ejecuta el comando para construir la clave, por ejemplo: openssl asn1parse -genconf asn_002.txt -out private_key_002.der Aunque también se puede hacer con Python de varias formas. Aquí la usada por el ganador.


En general, otra fórmula más visible es:


Una vez con la clave privada de los certificados, solo queda descifrar las claves simétricas:

DecryptedKey1
base64 -d EncryptedKey2.b64 | openssl rsautl -decrypt -inkey Cert2_priv.key > DecryptedKey2

Y copiar el contenido de los EncryptedFile en los ficheros EncryptedFile1.b64 y EncryptedFile2.b64 y descifrar los ficheros con la clave que hemos descifrado y usando aes-256-cbc como pone en el tag FileEncryptionAlg

base64 -d EncryptedFile1.b64 > EncryptedFile1
openssl aes-256-cbc -d -in EncryptedFile1 -kfile DecryptedKey1 > DecryptedFile1
base64 -d EncryptedFile2.b64 > EncryptedFile2
openssl aes-256-cbc -d -in EncryptedFile2 -kfile DecryptedKey2 > DecryptedFile2

Finalmente, se obtienen los mensajes que se encontraban originalmente en los ficheros secuestrados:


Nuestro ganador, Javier Junquera, ha sido sin duda el más rápido, ha necesitado apenas 24 horas, ¡enhorabuena! También han participado con respuestas correctas Oscar Fajardo y Sergio Besada.

Recordemos que, con ficheros diferentes, este concurso fue presentado en el Equinox, nuestro evento interno. Ahí, en cuestión de horas lo resolvieron Pablo Bartolomé (de Tuenti), Ángel Javier Alonso (también de Tuenti), Iván Izaguirre (de Tuenti, una vez más) y Ramiro Rodríguez (sorpresa, de Tuenti). Impresionante trabajo. Ellos usaron desde scripts en bash hasta implementaciones en Go de la solución, pasando por ¡la construcción de un Docker!. Nuestro CTO, Palako, también se animó a concursar oficiosamente, y ha publicados su solución en GitHub.

Por si os ha picado la curiosidad, aquí tenéis documentado un caso real donde se produjo este error criptográfico.

Gracias a todos los participantes.

Innovación y laboratorio en Elevenpaths.

No hay comentarios:

Publicar un comentario