Recuperar RSA private key Desde una session tls

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:

Citar

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

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!