En este artículo hablaremos del algoritmo de computación post cuántica SIKE, de sus similitudes con el algoritmo de intercambio de llaves Diffie-Hellman y de cómo se logró romper este algoritmo de llave pública.
A lo largo de varios artículos [1],[2],[3] hemos hablado de cómo el surgimiento de la computación cuántica ha implicado una gran cantidad de vulnerabilidades para los algoritmos de criptografía de llave pública; debido a esto, se han desarrollado varios protocolos de criptografía post-cuántica utilizando otros problemas computacionales más complejos que los problemas utilizados en la criptografía clásica como la factorización en primos y el problema del logaritmo discreto. El instituto nacional de estándares y tecnología de Estados Unidos (NIST) ha intentado estandarizar los algoritmos de criptografía post-cuántica y después de 4 rondas de selección se han establecido varios protocolos como los estándares en criptografía resistente a ataques cuánticos. El algoritmo en el que estamos interesados y sobre el que hablaremos en este artículo es el algoritmo SIKE (basado en Supersingular isogeny key exchange Diffie-Hellman SIDH); este algoritmo sería un candidato natural para reemplazar el algoritmo de Diffie-Hellman para intercambio de llaves, sin embargo hace unas semanas el algoritmo fue completamente vulnerado. En este artículo hablaremos del funcionamiento del protocolo SIKE y de lo que supone la vulnerabilidad que logró romper la seguridad de este algoritmo.
Funcionamiento del algoritmo SIKE
Para entender el funcionamiento del algoritmo SIKE, vamos a hablar primero del algoritmo de intercambio de llaves Diffie-Hellman y comparar las propiedades y el uso de ambos. El algoritmo de Diffie-Hellman es un algoritmo que utiliza las propiedades de los primos para poder intercambiar una llave de sesión entre dos personas sin que una persona que intercepte los datos pueda obtener la llave que están compartiendo.
Figura 1: Protocolo de intercambio de llaves Diffie-Hellman [4]
El proceso es el que podemos observar en la figura 1; ejemplifica el proceso en el que 2 personas, en este caso Alice y Bob, quieren intercambiar una llave secreta que un atacante no pueda descubrir. Este proceso consiste de los siguientes pasos:
Ahora Alice y Bob compartirán la llave secreta gabmodp y un atacante no puede deducir esta clave únicamente de A y de B; el problema de encontrar este a dado g y gamodp se conoce como el problema del logaritmo discreto y no se ha encontrado un algoritmo que funcione en un computador clásico que pueda resolver este problema en tiempo polinomial.
Siguiendo esta idea, existe una variación de este algoritmo conocido como el algoritmo de Diffie-Hellman de curva elíptica que utiliza la misma idea del algoritmo anterior pero en lugar de aplicar únicamente las propiedades de los primos emplea las propiedades de las curvas elípticas. Este algoritmo tiene los siguientes pasos:
Vemos que este protocolo funciona de manera similar al algoritmo de Diffie-Hellman clásico, pero utiliza las propiedades de las curvas elípticas.
Ahora, aunque los dos algoritmos mencionados siguen siendo utilizados hoy en día, pertenecen a una familia de algoritmos que se pueden vulnerar fácilmente con el uso de un computador cuántico. Como vemos en este artículo [2], el problema del logaritmo discreto puede romperse en tiempo polinomial con el uso de computación cuántica, por lo que es necesario buscar alternativas para mantener la seguridad ante este nuevo tipo de computación.
Entre los algoritmos propuestos para reemplazar el algoritmo de Diffie-Hellman, encontramos el algoritmo SIKE, que también tiene el objetivo de permitir el intercambio de llaves secretas con la ventaja de que está basado en un problema resistente a ataques de computadores cuánticos.
Observando con mayor profundidad, el algoritmo SIKE está basado en problemas matemáticos, por el momento, más complejos que los utilizados en el algoritmo de Diffie-Hellman y el algoritmo de Diffie-Hellman de curva elíptica. Los conceptos fundamentales del algoritmo son los siguientes:
Aunque no explicaremos en detalle todo el protocolo, mostraremos la siguiente comparación entre Diffie-Hellman de curva elíptica y el protocolo SIKE utilizando como base estas definiciones mencionadas antes:
La tabla 2 refleja las similaridades entre SIKE y DiffieHellman de curva elíptica. Ambos protocolos se basan en la misma idea central, pero cambiando los componentes matemáticos por otros más complejos; cambiamos los puntos de una curva elíptica por clases de isogenias del j-invariante, el cálculo pasa a ser el cálculo de la isogenia en la curva elíptica, el secreto como tal pasa de ser un escalar a una isogenia y el problema difícil pasa de ser el problema del logaritmo discreto al problema de la isogenia supersingular. El problema de la isogenia supersingular se define de la siguiente manera:
Como consecuencia de utilizar objetos más complejos, tenemos un problema al que no se le ha encontrado un algoritmo que encuentre la solución en tiempo polinomial ni siquiera en un computador cuántico; de aquí la utilidad de este nuevo algoritmo de intercambio de llaves.
La vulneración del algoritmo SIKE
Hace unas semanas surgió una nueva noticia de que el algoritmo SIKE había sido vulnerado por un computador clásico de 1 solo procesador. El estándar SIKEp182 se rompió en 4 minutos, el estándar SIKEp217 en 6 y el estándar que se utilizaría en la criptografía post-cuántica SIKEp434 se rompió en poco más de una hora.
Todos los detalles del funcionamiento del ataque se pueden encontrar en [5]. Este algoritmo, dados los parámetros del sistema SIKE puede encontrar la isogenia ϕ tanto para Alice, como para Bob que representaría la llave privada de cada uno que se utilizó para calcular la llave compartida.
Es importante notar, que aunque este algoritmo logra romper la seguridad de SIKE con un computador muy básico, no es un ataque que logre resolver el problema general de la isogenia supersingular, sino que funciona basándose en algunos de los puntos auxiliares y parámetros que usa específicamente el algoritmo de SIKE y hasta el momento no se conoce ninguna técnica similar para resolver el problema general. De hecho, en el mismo artículo [5] se habla de la posibilidad de que con unas modificaciones SIKE siga funcionando aunque la seguridad del protocolo se debe seguir estudiando con mayor profundidad.
Conclusión
La criptografía post-cuántica todavía es una rama muy nueva de la ciencia de la computación y está en constante desarrollo, por lo que es posible que se sigan descubriendo vulnerabilidades para estos algoritmos incluso después de procesos de selección tan estrictos como el de la NIST. Por otro lado, vemos que aunque es importante ir actualizando varias de nuestras primitivas criptográficas a los nuevos estándares resistentes a computadores cuánticos, debemos seguirnos informando de la seguridad de estos algoritmos y de las amenazas que se puedan encontrar para estos.
Sin embargo, aunque el algoritmo de SIKE ha sido vulnerado, el problema principal de la isogenia supersingular sigue siendo un problema difícil de resolver incluso con computadores cuánticos, por lo que existe la posibilidad de que el algoritmo SIKE siga funcionando si encuentran algunas modificaciones al protocolo que les permita evitar este tipo de ataques.
Si deseas tener siempre a la mano el artículo escrito por nuestro ingeniero José Darío Flórez, te invitamos a descargarlo, compartirlo y comentarnos qué opinas al respecto.
Referencias:
[1] Complejidad de problemas de criptografía clásica y post-cuántica
[2] RSA y el algoritmo de Shor
[3] El impacto de la computación cuántica
[4] Diffie-Hellman
[5] AN EFFICIENT KEY RECOVERY ATTACK ON SIDH