RSA contra las cuerdas: 1.001 razones por las que está cayendo en desgracia (II)

Gonzalo Álvarez Marañón    13 enero, 2020
RSA contra las cuerdas: 1.001 razones por las que está cayendo en desgracia (II)

Muchos medios han anunciado en las últimas semanas que se ha encontrado una vulnerabilidad en RSA que permite atacar uno de cada 172 certificados. Pues no, como explicó nuestro compañero Sergio de los Santos, no ha sido así. Es cierto que RSA está moribundo, pero poco tiene que ver la causa de su muerte con el supuesto ataque. En la primera parte, introdujimos los principales problemas de RSA. En esta seguna parte hablamos de repasaremos los problemas de seguridad y las dificultades de implementación de RSA, que lo convierten en una elección cada día menos recomendable, hasta el extremo de que ha sido abandonado por TLS 1.3 como algoritmo de intercambio de claves.

Los exponentes pequeños causan problemas grandes

Típicamente se escoge uno de los siguientes valores para el exponente público: e = 3 (en binario, 11), e = 17 (en binario, 1 0001) o e = 65537 (en binario, 1 0000 0000 0000 0001), conocidos como primos de Fermat. ¿Por qué? Porque cuantos menos unos (1’s) tenga el exponente, más rápido será luego realizar las operaciones matemáticas de exponenciación, ya que se utiliza el algoritmo de exponenciación binaria.

Un valor pequeño para el exponente implica una alta velocidad de operación, pero, y éste es un GRAN PERO, acarrea graves problemas de seguridad. Es importante recalcar que todos los ataques mencionados a continuación obtienen el mensaje original m a partir del mensaje cifrado c, pero no obtienen la clave privada (d).

  • Ataques de raíz e-ésima: teniendo en cuenta que un valor común para el exponente es e = 3, para mensajes cortos tales que m << n, podría darse el caso de que me < n , por lo que sin más que extraer la raíz e-ésima del cifrado se recupera el mensaje original. De ahí la importancia del relleno (padding) para prevenirlo, como explicaré más adelante.
  • Ataques de broadcast de Håstad: si se cifra el mismo mensaje m con distintas claves públicas (ni, e), que difieren en el valor de n, pero usan e = 3, entonces para i ≥3 y según el teorema chino del resto (CRT), es posible calcular c’ = m3 mod n1n2n3, tal que m = c. Generalizando para cualquier valor de e, se requieren e textos cifrados para obtener el mensaje original m. Para evitarlo, se requiere usar un relleno aleatorizado, no uno fijo.
  • Ataques de Franklin-Reiter: Franklin-Reiter identificó un nuevo ataque contra RSA con e = 3. Si dos mensajes m1 y m2 que difieren sólo en una cierta distancia (no entraremos en los detalles matemáticos de esa distancia) se cifran con el mismo módulo n, entonces es posible recuperar ambos.
  • Ataques de Coppersmith: si se usan dos rellenos aleatorios para el mismo mensaje en dos ocasiones sucesivas (p.e. porque fueron interceptados y el primero no llegó a su destinatario), aunque se desconozca el relleno aleatorio, se puede recuperar el mensaje utilizando el teorema de Coppersmith, siempre que el relleno aleatorio sea corto. Concretamente, cuando e = 3, la longitud del relleno debe ser inferior a la novena parte de la longitud del mensaje.
  • Ataque de Bleichenbacher contra las firmas: recuerda que para verificar una firma hay que exponenciar al exponente e. De nuevo, si e = 3, existe un ataque muy sencillo de implementar debido al criptólogo Daniel Bleichenbacher que permite falsificar firmas RSA basadas en el esquema de relleno definido en el estándar PKCS#1 v1.5.

Es justo mencionar que con el relleno adecuado los ataques anteriores se neutralizan. Si te han picado la curiosidad los entresijos matemáticos de todos estos ataques, puedes leer una descripción muy asequible en este trabajo clásico de David Boneh.

El tamaño del exponente privado también importa

Aunque el proceso habitual para generar las claves de RSA es el descrito al principio de este artículo en tres pasos, algún desarrollador, presionado por la necesidad de velocidad en dispositivos con potencia de cómputo limitada, podría querer fijar primero un valor pequeño para d y calcular e después. Así agilizaría drásticamente la velocidad de exponenciación, hasta por un factor de 10.

El criptólogo Michael Wiener ideó un ataque que permite recuperar d a partir de la clave pública (n, e) siempre que d < ⅓n¼. Para un módulo típico de 2048 bits, significa que la longitud de d debe ser superior a 512 bits, lo que aun así sigue siendo largo para dispositivos muy modestos, como las tarjetas inteligentes.

Si d es pequeño, entonces e es necesariamente grande. Si, contrariamente a la tradición, una clave pública (n, e) presenta un valor de e enorme (e ≫ 65537), puede valer la pena comprobar el ataque de Wiener contra ella.

Sin relleno adecuado no hay seguridad ninguna

El tamaño del mensaje m no puede exceder el tamaño del módulo n. Por consiguiente, habrá que rellenar m (padding). Pero ¿cómo? ¿Tal vez rellenar con 0’s por delante del número hasta llegar a los 2048 bits? ¡Craso error!

El relleno detallado en la especificación PKCS#1 v1.5 resultó ser vulnerable a los ataques de Bleichenbacher. Si un atacante envía a un servidor TLS paquetes cifrados con RSA y el servidor devuelve un mensaje de error si un determinado paquete cifrado ha sido incorrectamente rellenado bajo las reglas de PKCS#1 v1.5, puede necesitar tan sólo 15.000 paquetes para obtener información suficiente para descifrar un texto cifrado con RSA o para falsificar una firma.

Y existen otras muchas versiones de este tipo de ataques contra los esquemas de relleno, como el recientemente célebre ataque ROBOT. De hecho, este tipo de ataques resulta tan insidioso y tan difícil de eliminar, que en la nueva versión de TLS, la 1.3, se ha eliminado a RSA por completo de la ecuación para intercambio de claves, confiando en Diffie-Hellman Efímero (DHE) como único método.

PKCS#1 v1.5 presentó otros problemas. En el protocolo TLS, el cliente genera aleatoriamente una clave de sesión que cifra con la clave pública del servidor (en realidad el proceso es algo más complicado, pero lo dejaremos aquí). Cualquier persona con acceso a la clave privada correspondiente puede recuperar la clave de sesión, comprometiendo la seguridad de la sesión. El ataque no tiene que ocurrir en tiempo real. Un adversario podría almacenar todo el tráfico cifrado y esperar pacientemente hasta que obtenga la clave privada. Por ejemplo, los avances en potencia de cómputo podrían hacer factible un ataque de fuerza bruta en el futuro. O tras la llegada de los ordenadores cuánticos podría factorizarse n. Alternativamente, la clave puede obtenerse utilizando poderes legales, coacción, soborno, irrumpiendo en un servidor que la utiliza o explotando alguna vulnerabilidad en el software TLS, al estilo Heartbleed. Después del compromiso de la clave, es posible descifrar todo el tráfico previamente registrado.

Los otros mecanismos comunes de intercambio de claves usados en TLS no sufren de este problema, por lo que se dice que exhiben secreto perfecto hacia adelante: cada conexión utiliza una clave de sesión independiente. Una clave de servidor comprometida podría utilizarse para hacerse pasar por el servidor, pero no para descifrar retroactivamente el tráfico.

En la actualidad se utiliza el esquema de firma probabilística (RSA-PSS). Combina la firma y la verificación con una codificación del mensaje. Este enfoque, a diferencia de otros esquemas basados en RSA como PKCS#1 v1.5, introduce un proceso de aleatorización que permite demostrar que la seguridad del método está estrechamente relacionada con la seguridad del propio algoritmo RSA. Esto hace que RSA-PSS sea más deseable como opción para la firma digital basada en RSA y haya sido adoptado por TLS 1.3.

Moraleja: ¡nunca, nunca, nunca utilices RSA sin relleno!

No se vayan todavía, que aún hay más

Y eso por no mencionar los ataques contra implementaciones físicas deficientes, derivadas de la exponenciación modular.

Los ataques de temporización: dado que para descifrar hay que exponenciar con la clave privada (d) como exponente, midiendo el tiempo empleado en descifrar se puede estimar el valor de la clave. Los más conocidos son el ataque de Kocher, el ataque de Schindler o el de Brumley-Boneh. Todos ellos pueden contrarrestarse mediante descifrado ciego: para descifrar el texto cifrado c, primero se calcula el valor intermedio y = rec mod n, donde r es un número entero aleatorio. A continuación, y se descifra de la manera usual, seguido por la multiplicación por r−1 mod n:

r−1yd = r−1(rec)d = r−1rcd = cd mod n

Puesto que r es aleatorio, y es aleatorio y la medición del tiempo de descifrado de y no revela ninguna información sobre la clave privada d. No hace falta repetir que debe usarse un número aleatorio r distinto para cada descifrado.

Por otro lado, los ataques de canal lateral obtienen información de un criptosistema a partir de sus parámetros físicos, como temperatura, consumo energético, emisiones electromagnéticas, etc. Después de todo, RSA no existe solo en los libros de matemáticas, debe materializarse en el Mundo RealTM. En el caso de RSA, el consumo de energía cuando está operando con un 1 es distinto que con un 0.

Por último, los ataques de glitch buscan inducir errores (glitches) en las operaciones del dispositivo, como por ejemplo una tarjeta inteligente. Aunque parezca mentira, en algunas implementaciones de RSA ¡un simple error inducido puede permitir a un atacante factorizar n!

¡Aviso para programadores!

A la vista queda la cantidad de pequeños detalles y sutilezas involucrados en la codificación correcta de RSA. ¡Ni lo intentes! Utiliza bibliotecas criptográficas especializadas y evitarás los errores más comunes al introducir criptografía en tus desarrollos.

Y la pregunta que queda en el aire: si no utilizo RSA, ¿con qué cifro y firmo? La respuesta rápida es: con criptografía de curva elíptica (ECC), más eficiente, más segura. La respuesta larga será material para otro artículo.


Si quieres saber más sobre el algoritmo RSA, aquí te dejamos la primera parte de este artículo:

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *