Este fin de semana se ha publicado una noticia cuyo subtítulo rezaba así: “Se ha encontrado una vulnerabilidad en los certificados RSA que podría comprometer uno de cada 172 certificados actualmente en uso”. Esto no es cierto, lo que ha ocurrido es que un paper ha recordado que, sin la entropía correcta, los certificados quedan vulnerables, sobre todo en el mundo IoT. Veamos qué ha ocurrido exactamente porque, si bien es interesante el estudio, viene a recordar más que a descubrir.

Un poco de base sobre los certificados

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 pero 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.

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.

1736640013 x 1230300287 = 2136588706409583731 
 ? x ? = 2136588706409583731

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. Pero hay un truco. Si la entropía es baja y durante las generaciones de números primos, alguno se repite… 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 tomamos un buen montón de certificados y 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. 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.
Este "ataque" es un viejo conocido. De hecho, 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.

¿Y qué han hecho los investigadores?

En la First IEEE Conference on Trust, Privacy, and Security in Intelligent Systems and Applications en Los Ángeles presentaron una investigación en la que aseguraban que se podían comprometer las claves RSA con capacidades computacionales reducidas.

Crearon una base de datos de 75 millones de claves RSA. Después analizaron usando un algoritmo (en la optimización de este algoritmo puede estar la gracia de la investigación) y la computación de Azure. Intentaron encontrar factores comunes y encontraron que 1 de cada 172 (435.000) compartía un factor entre sí. A partir de ahí se deduce que es fácil romper esos certificados, etc. Pero esto no es del todo cierto, lo que hicieron fue crear "a propósito" los certificados con baja entropía.

Porque luego matizan que tomaron 100 millones de certificados de los logs de Certificate Transparency. Y que si tenían en cuenta solo estos 100 millones de certificados reales solo 5 compartían factores. Un porcentaje ridículo.

A falta de la publicación de la investigación, ¿qué ha pasado? Bueno, pues que han demostrado que el ataque del mínimo común múltiplo por falta de entropía funciona. No han dado detalles sobre si sus claves eran entrópicamente pobres a conciencia pero luego aclaran que esto es un problema en el mundo del IoT donde los dispositivos pueden no ser lo suficientemente potentes como para crear números primos muy distintos (entrópicos) entre sí.

En resumen, una muestra empírica de un ataque que ya se conoce, que viene a recordar algo que debemos tener en cuenta: si se calculan las claves RSA en dispositivos con una aleatoriedad baja, los certificados derivados pueden compartir algún primo y por tanto su clave pública puede ser más fácilmente deducida. En la vida real, el ataque no es tan sencillo, porque no puede ser “dirigido” (no puedes elegir qué primo puede ser compartido de qué certificado) sino que puede ser más “casual”, aunque esto no le reste importancia. Igualmente, para ponerlo en práctica y por ejemplo sustituir un certificado, también sería necesario redirigir a la víctima.

Fuente: Blogthinkbig