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

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ábamos hace poco, 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 esta primera parte del artículo 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.

RSA para dummies

El algoritmo RSA sirve tanto para cifrar usando una clave pública como para firmar digitalmente usando una clave privada. Su funcionamiento resulta sorprendentemente sencillo:

1. Se generan aleatoriamente dos números enteros primos, p y q, cuyo producto es n = p·q.
2. Se elige un número entero e cualquiera que sea coprimo con respecto a ϕ(n) = (p−1)·(q−1). Ambos números, (n, e), constituyen la clave pública.
3. Se calcula d, el inverso multiplicativo de e módulo ϕ(n), tal que e·d = 1. Este número (d) constituye la clave privada.

Y ya está todo listo para empezar a operar. Por ejemplo, para cifrar un mensaje m (consistente en un número entero menor que n):

c = m^e mod n.

La operación de descifrado es tan sencilla como:

m = c^d mod n = (m^e)^d mod n = m^ed mod n = m,

ya que e·d = 1.

Cualquiera que conozca la clave pública (n, e) puede cifrar, pero solamente el legítimo propietario de la clave privada (d) podrá descifrar. En la práctica, los mensajes a cifrar suelen ser claves secretas de sesión, como ocurre por ejemplo en el protocolo criptográfico TLS.

Para firmar se realizan exactamente las mismas operaciones, pero en orden inverso. Solo el legítimo propietario de la clave privada (d) podrá firmar un mensaje m:

s = m^d mod n.

Mientras que cualquiera que conozca la clave pública correspondiente (n, e) podrá verificar la firma, dados m y s:

m = s^e mod n = (m^d)^e mod n = m^de mod n = m,

ya que d·e = 1.

Y así, sobre el papel, todo parece sencillo. ¡Pues no lo es!

Multiplicar es fácil, factorizar es difícil

La seguridad de RSA se basa en la dificultad de factorizar grandes números, es decir, de encontrar sus factores primos. Considerando la potencia de cómputo actual, para que RSA sea seguro en la práctica, se recomiendan longitudes para el módulo n de 2048 bits o más. De hecho, para 2020 ya se prescribe una longitud de 4096 bits.

La penalización de pago es que las operaciones matemáticas con números tan grandes se ralentizan considerablemente, especialmente en dispositivos con potencia limitada. ¡RSA es dolorosamente lento!

Encontrar el número primo de gran tamaño no es tarea fácil

Para una longitud n de 2048 bits se necesitan primos de aproximadamente 1024 bits. El enfoque típico consiste en seleccionar al azar un número impar de unos 1024 bits y pasarle un test de primalidad. En función del tamaño de los números buscados, este proceso puede llegar a ser computacionalmente prohibitivo, lo que impulsa a muchos desarrolladores a buscar atajos con consecuencias devastadoras.

1. El generador de números debe ser aleatorio e impredecible. Si existe algún tipo de sesgo o defecto en el generador, pueden ocurrir todo tipo de desastres. Por ejemplo, podrían ser predecibles, como ocurrió con el error de la distribución de OpenSSL de Debian, que redujo las semillas de inicialización del generador a tan solo 32.768 valores. O podría suceder que en algún momento se repitan dos primos, de modo que dos módulos n compartan el mismo número p o q, en cuyo caso mediante el ataque Batch-GCD se pueden recuperar los primos compartidos calculando el mayor divisor común entre todos los pares de n. En 2012, dos grupos de investigación, constataron independientemente que en torno al 0,75% de certificados TLS de Internet compartía factores primos debido a una entropía insuficiente durante la generación de los primos. En 2016, otro trabajo mostró que el 0,4% continuaba vulnerable. Este es el problema denunciado en 2019 por los autores del estudio sobre la supuesta vulnerabilidad de RSA que tanto ruido ha hecho. No es una vulnerabilidad como tal de RSA, sino un fallo de implementación. En algunos casos, incluso si dos valores de n no tienen exactamente el mismo factor, pero están muy próximos, ambos n pueden factorizarse.
2. p y q deben ser independientes. Si comparten aproximadamente la primera mitad de sus dígitos, podría factorizarse n mediante el método de factorización de Fermat. Algunos programadores buscan atajar generando primos buscando a partir del valor objetivo: por ejemplo, arrancan desde 2¹⁰²⁴ y van iterando de dos en dos comprobando si el número es primo. ¡¡¡Desastre!!!
3. Los tests de primalidad son probabilísticos. Deciden con una probabilidad muy alta que el número es primo, pero no pueden asegurarlo. Para aumentar la seguridad, se pasan repetidas veces. Los más usados son el test de Miller-Rabin y el test de Solovay-Strassen. No es tanto un problema de seguridad, como de eficiencia. Aunque eso sí, sería desastroso que p o q no fueran primos.

Conclusión: no solo RSA es dolorosamente lento, ¡buscar sus claves también lo es!

Puedes encontrar instrucciones, explicaciones, ejemplos y código sobre este asunto en la completísima página de FactHacks.

La versión «libro de texto» de RSA es para la escuela, no para la vida real

Nunca, bajo ningún pretexto, debe utilizarse en aplicaciones reales lo que se conoce como la versión «libro de texto» de RSA, es decir, tal cual la he explicado, ya que sería susceptible a todo tipo de ataques:

• Al ser determinista, dado un mensaje cifrado, podría buscarse exhaustivamente el correspondiente mensaje claro. O se podría construir un diccionario de parejas de textos claro/cifrado.
• Por el mismo motivo, es susceptible a ataques de reinyección: si un atacante intercepta paquetes cifrados con RSA, podría reutilizarlos inyectándolos en otra comunicación.
• Sucumbe a los ataques de encuentro en el medio (a no confundir con ataques de hombre en el medio), que funcionan precalculando listas de mensaje cifrados con (n, e) y mensajes cifrados con (n, e⁻¹) y buscando colisiones entre las listas.

En resumen, para evitar estos problemas, en lugar de usar RSA tal cual resulta crítico utilizar relleno (padding), tal como explicaré algo más adelante.

---

En la segunda parte de este artículo veremos otros problemas de la RSA:

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