Recuperar RSA private key Desde una session tls

[AlbertoBSD]

Como.me gustaria ver esa platica...

:https://www.blackhat.com/us-16/briefings/schedule/#recover-a-rsa-private-key-from-a-tls-session-with-perfect-forward-secrecy-3046

In certain circumstances it is possible to derive the private key of server regardless of the size of the used modulus. Even RSA keys of 4096 bits can be factored at the cost of a few CPU cycles and computational resources.

¿Alguien sabe algo del tema?

Saludos

[kub0x]

Buenas,

intentaré dar una explicación detallada del por que del problema, además de su aplicación matemática y resolución. A través de los conceptos aquí descritos sereís capaces de poder factorizar el módulo semiprimo RSA.

El paper en cuestión es : https://people.redhat.com/~fweimer/rsa-crt-leaks.pdf

Lo primero, voy a completar la sentencia del problema inicial, puesto que en primera instancia parece simple, pero han de darse unas condiciones de fallo en el sistema para poder realizar la factorización. Completo citando el abstracto del paper:

All that needed is the generation of a faulty digital signature from server, an event that can be observed when occurring certain conditions such as

Como vemos el servidor tiene que generar una firma digital de forma errónea, evento que puede suceder cuando se dan ciertas condiciones como errores de hardware, sobrecarga de módulos, inundación etc. Además la implementación de RSA debe de contar con la optimización CRT.

¿Qué es la optimización CRT?

Una de las aplicaciones del Chinese Remainder Theorem (CRT) es optimizar el coste computacional que conllevan las operaciones en el grupo multiplicativo modulo pq, concretamente las exponenciales modulares. La optimización se realiza computando los residuos sobre los módulos primos (por separado) y aplicando CRT sobre dichos residuos y módulos primos para así obtener el residuo en el módulo principal pq. El taller sobre el CRT lo podeís consultar aquí: https://foro.elhacker.net/criptografia/taller_chinese_remainder_theorem-t452361.0.html

Por lo tanto la optimización por CRT divide las operaciones en dos grupos multiplicativos módulo p y q (por separado) y luego reagrupa en pq mediante CRT. Este concepto se llama Residue Number System https://en.wikipedia.org/wiki/Residue_number_system .

Ahora abordemos la vulnerabilidad planteada en el paper:

Es bien sabido que al hablar de Perfect-Forward Secrecy nos referimos a las suites criptográficas que cuentan con algorítmos ephemeral, es decir, aquellos que en cada negociación TLS utilizan una clave asimétrica distinta, por lo tanto si un atacante rompiera una clave el mismo sólo tendría acceso a la clave simétrica (AES, TDES..) de esa sesión, pero no a las demás claves simétricas de sesiones distintas. En cambio si rompes RSA podrás descifrar todas las claves de sesión capturadas. Esta es el concepto del porque del esfuerzo para migrar a suites que incluyan Perfect-Forward Secrecy.

Hay una gran diferencia entre una sesión TLS negociada sólo con RSA+simétrica o con RSA+ECHDE/DHE+simétrica.

Veamos que sucedería si el servidor malfuncionara a la hora de realizar una sesión TLS utilizando una suite con Perfect-Forward Secrecy:

Con las suites que incluyen Perfect-Forward Secrecy (Ephemeral crypto) sucede un nuevo evento llamado ServerKeyExchange, donde el servidor envía su clave pública y una firma digital sobre la misma, que es un hash firmado por la clave pública RSA del certificado.

Si a la hora de computar la firma digital sobre los dos grupos multiplicativos modulares en p y q, fallará al hacerlo en p y lo hiciera bien en q, tendríamos un escenario con la siguiente información:

y_p = x'^d (mod p)
y_q = x^d (mod q)

Por lo que vemos que x' y x son distintas y deberían de ser iguales (para cumplir el CRT y la firma digital), por lo tanto se ha cometido un error al denotar x'.

Si pasamos mediante CRT y_p e y_q a y_n tendríamos la representación final:

y_n = y_p*q*[q]^-1_p + y_q*p*[p]^-1_q (mod pq)

donde [q]^-1_p es la modular multiplicativa inversa de q en p es decir q^-1 = q^p-2 (mod p)
y [p]^-1_q es la modular multiplicativa inversa de p en q es decir p^-1 = p^q-2 (mod q)

Vease que la modular multiplicativa inversa con módulo primo siempre tendrá exponente p-2 ya que el exponente se obtiene mediante:

phi(p)-1 y como p es primo, phi(p) = p - 1 por lo tanto phi(p) - 1 = p - 2

y_n = x''^d (mod pq)

Notése que x'' no es x, y debería de ser x en un escenario sin fallos (cumpliendo el CRT). Esto quiere decir la verificación de la firma digital nunca será x, ya que hemos utilizado dos x distintas, por lo tanto el destinatario fallará al validarla, pero el atacante (NOSOTROS) tendríamos la siguiente información:

x'' = y_n^e (mod pq)

gcd(x'' - x, n) = q, por lo que q es un múltiplo de x'' - x. Fijaos en la ecuación del CRT para verificar la multiplicidad.

Un ejemplo en C#, el código de abajo selecciona dos primos p,q y computa la clave privada d, el exponente público e y la clave pública n (p*q).

Después selecciona dos valores x y x''. Recordad que para que funcione RSA con la optimización CRT los valores de x han de ser iguales (principio del CRT), por lo tanto mi código se aprovecha de la vulnerabilidad descrita en este post.

Lo siguiente que hará el code es computar el CRT de y_p e y_q y dejarlo en la variable CRT para así factorizar el módulo pq mediante el gcd del módulo pq con el descifrado de CRT menos x. El resto del gcd es el factor primo q del módulo.

En un escenario real el cliente tendría los valores de las variables, CRT, e, x y n, el resto de operaciones las calcula el server, vamos que es 100% aplicable en un escenario real.

Código (csharp) [Seleccionar] Expandir


static void Main()
       {
           using (RSACryptoServiceProvider csp = new RSACryptoServiceProvider(512))
           {
               RSAParameters rsaparams = csp.ExportParameters(true);
               p = FromBigEndian(rsaparams.P);
               BigInteger n = FromBigEndian(rsaparams.Modulus);
               BigInteger d = FromBigEndian(rsaparams.D);
               BigInteger e = FromBigEndian(rsaparams.Exponent);
               BigInteger q = FromBigEndian(rsaparams.Q);
               if (p < q)
               {
                   BigInteger swap = q;
                   q = p;
                   p = swap;
               }
               BigInteger x = BigInteger.Parse("126858358328568235238789");
               BigInteger xpr = BigInteger.Parse("87281629769238657836258");
               BigInteger yp = BigInteger.ModPow(xpr, d, p);
               BigInteger yq = BigInteger.ModPow(x, d, q);
               BigInteger invqp = BigInteger.ModPow(q, p - 2, p);
               BigInteger invpq = BigInteger.ModPow(p, q - 2, q);
               BigInteger CRT = BigInteger.Remainder(yp * q * invqp + yq * p * invpq, n);
               //El cliente dispone del valor CRT, e, n y x pues los entrega el server
               BigInteger gcd = BigInteger.GreatestCommonDivisor(BigInteger.ModPow(CRT,e,n) - x, n);
               Console.WriteLine("q is {0} = " , gcd);
           }
       }


Estaré encantado de responder cualquier pregunta.

Saludos!

[AlbertoBSD]

Excelente la base teorica muy bien explicada y ahorita que llegue a mi casa probare el codigo para testearlo por mi mismo y ahora bien.

Ya sabia que serias tu el que responderia.

Veamos que sucedería si el servidor malfuncionara a la hora de realizar una sesión TLS

¿Que tipi de fallo podria ocasionar esto?

Por que segun yo no es un fallo de programacion.

[kub0x]

Este ataque tiene historia, antes de ser comentado en la BlackHat, nuestro querídismo Lenstra ya lo había propuesto en un paper del año 96 lo único que teorizándolo. Como bien sabemos a los chicos de la BlackHat les encanta el lema de "exploiting everywhere" por lo tanto se trabajaron este nuevo paper y demostraron lo que Lenstra teorizó, explotando unos cuantas sesiones TLS y explicando más o menos en que consisten los fallos.

El paper de la BlackHat está en el post inicial, 3ª línea.
El paper de Lenstra es : https://infoscience.epfl.ch/record/164524/files/nscan20.PDF

Los de BlackHat nos dan las siguientes premisas para que un fallo suceda en la computación del Residue Number System con isomorfismo a Z/nZ:

- La librería de precisión aritmética múltiple utilizada en la implementación de RSA tiene un defecto que produce malos resultados. Revisar CVE-2014-357.
- Puede haber una race condition de acceso a datos entre hilos no sincronizados, por lo tanto ya sabemos que sucede aquí (nefasto).
- Fallos en la unidad aritmético lógica de la CPU de forma determinista en base a http://iacr.org/archive/crypto2008/51570222/51570222.pdf o dependiendo de unas condiciones de entorno.
- http://eprint.iacr.org/2002/076.pdf
- Otros módulos del PC como la cache o la RAM han sido alterados, cambiando los valores del Reduced Number System.

Saludos!

[AlbertoBSD]

Muchas gracias kub0x le dare tiempo a cada paper ahorita estoy leyendo  este

- Fallos en la unidad aritmético lógica de la CPU de forma determinista en base a http://iacr.org/archive/crypto2008/51570222/51570222.pdf o dependiendo de unas condiciones de entorno.

Ya habia escuchado de este tipo de fallos pero no habia visto el alcance que pueden tener.

Tus aporte son Geniales.

Saludos!!