Un nuevo ataque eliminó fácilmente un posible algoritmo de cifrado

Apr 14, 2023

Dan Goodin, Ars Technica

En la campaña en curso del gobierno de EE. UU. para proteger los datos en la era de las computadoras cuánticas, un nuevo y poderoso ataque que usó una sola computadora tradicional para romper por completo a un candidato de cuarta ronda destaca los riesgos involucrados en la estandarización de la próxima generación de algoritmos de cifrado.

Esta historia apareció originalmente en Ars Technica, una fuente confiable de noticias tecnológicas, análisis de políticas tecnológicas, reseñas y más. Ars es propiedad de la empresa matriz de WIRED, Condé Nast.

El mes pasado, el Instituto Nacional de Estándares y Tecnología de EE. UU. (NIST, por sus siglas en inglés) seleccionó cuatro algoritmos de cifrado de computación poscuántica para reemplazar algoritmos como RSA, Diffie-Hellman y la curva elíptica Diffie-Hellman, que no pueden resistir los ataques de un sistema cuántico. computadora.

En el mismo movimiento, NIST presentó cuatro algoritmos adicionales como reemplazos potenciales en espera de más pruebas, con la esperanza de que uno o más de ellos también puedan ser alternativas de cifrado adecuadas en un mundo poscuántico. El nuevo ataque rompe SIKE, que es uno de los últimos cuatro algoritmos adicionales. El ataque no tiene impacto en los cuatro algoritmos PQC seleccionados por NIST como estándares aprobados, todos los cuales se basan en técnicas matemáticas completamente diferentes a las de SIKE.

SIKE, abreviatura de encapsulación de clave de isogenia supersingular, ahora probablemente ya no esté disponible, gracias a una investigación publicada durante el fin de semana por investigadores del grupo de seguridad informática y criptografía industrial de KU Leuven. El documento, titulado "An Efficient Key Recovery Attack on SIDH (Versión preliminar)", describía una técnica que utiliza matemáticas complejas y una sola PC tradicional para recuperar las claves de cifrado que protegen las transacciones protegidas por SIKE. Todo el proceso requiere sólo alrededor de una hora. La hazaña hace que los investigadores, Wouter Castryck y Thomas Decru, sean elegibles para una recompensa de $50,000 del NIST.

"La debilidad recientemente descubierta es claramente un gran golpe para SIKE", escribió en un correo electrónico David Jao, profesor de la Universidad de Waterloo y co-inventor de SIKE. "El ataque es realmente inesperado".

El advenimiento del cifrado de clave pública en la década de 1970 fue un gran avance, porque permitió a las partes que nunca se habían conocido intercambiar de forma segura material cifrado que un adversario no podía descifrar. El cifrado de clave pública se basa en claves asimétricas, con una clave privada utilizada para descifrar mensajes y una clave pública separada para cifrar. Los usuarios hacen que su clave pública esté ampliamente disponible. Mientras su clave privada permanezca en secreto, el esquema permanecerá seguro.

En la práctica, la criptografía de clave pública a menudo puede ser difícil de manejar, por lo que muchos sistemas se basan en mecanismos de encapsulación de claves, que permiten a partes que nunca se han conocido antes acordar conjuntamente una clave simétrica en un medio público como Internet. En contraste con los algoritmos de claves simétricas, los mecanismos de encapsulación de claves que se utilizan hoy en día son fácilmente descifrados por las computadoras cuánticas. Se pensaba que SIKE, antes del nuevo ataque, evitaba tales vulnerabilidades mediante el uso de una construcción matemática compleja conocida como gráfico de isogenia supersingular.

La piedra angular de SIKE es un protocolo llamado SIDH, abreviatura de supersingular isogeny Diffie-Hellman. El trabajo de investigación publicado durante el fin de semana muestra cómo SIDH es vulnerable a un teorema conocido como "pegar y dividir" desarrollado por el matemático Ernst Kani en 1997, así como a herramientas ideadas por sus compañeros matemáticos Everett W. Howe, Franck Leprévost y Bjorn. Poonen en 2000. La nueva técnica se basa en lo que se conoce como ataque adaptativo GPST, descrito en un artículo de 2016. Se garantiza que las matemáticas detrás del último ataque serán impenetrables para la mayoría de los no matemáticos. Esto es lo más cerca que vas a estar:

"El ataque explota el hecho de que SIDH tiene puntos auxiliares y que se conoce el grado de la isogenia secreta", explicó en un breve artículo Steven Galbraith, profesor de matemáticas de la Universidad de Auckland y la "G" en el ataque adaptativo GPST. en el nuevo ataque. "Los puntos auxiliares en SIDH siempre han sido una molestia y una debilidad potencial, y han sido explotados para ataques de fallas, el ataque adaptativo GPST, ataques de puntos de torsión, etc."

lauren goode

lauren goode

julian chokkattu

Will caballero

Más importante que entender las matemáticas, Jonathan Katz, miembro del IEEE y profesor del Departamento de Ciencias de la Computación de la Universidad de Maryland, escribió en un correo electrónico: "El ataque es completamente clásico y no requiere computadoras cuánticas en absoluto".

SIKE es el segundo candidato a PQC designado por el NIST que se invalidará este año. En febrero, el investigador postdoctoral de IBM, Ward Beullens, publicó una investigación que descifró Rainbow, un esquema de firma criptográfica cuya seguridad, según Cryptomathic, "se basa en la dificultad del problema de resolver un gran sistema de ecuaciones cuadráticas multivariadas en un campo finito".

La campaña de reemplazo de PQC de NIST ha estado funcionando durante cinco años. Aquí hay una breve historia:

Rainbow cayó durante la ronda 3. SIKE había llegado hasta la ronda 4.

Katz continuó:

Quizás sea un poco preocupante que este sea el segundo ejemplo en los últimos seis meses de un esquema que llegó a la tercera ronda del proceso de revisión del NIST antes de romperse por completo con un algoritmo clásico. (El ejemplo anterior fue Rainbow, que se rompió en febrero). Tres de los cuatro esquemas de PQC se basan en suposiciones relativamente nuevas cuya dificultad exacta no se comprende bien, por lo que lo que indica el último ataque es que tal vez todavía debemos ser cautelosos/conservadores. con el proceso de estandarización en marcha.

Le pregunté a Jao, el co-inventor de SIKE, por qué la debilidad había salido a la luz solo ahora, en una etapa relativamente posterior de su desarrollo. Su respuesta fue perspicaz. Él dijo:

Es cierto que el ataque usa matemáticas que se publicaron en las décadas de 1990 y 2000. En cierto sentido, el ataque no requiere nuevas matemáticas; se podría haber notado en cualquier momento. Una faceta inesperada del ataque es que utiliza curvas de género 2 para atacar curvas elípticas (que son curvas de género 1). Una conexión entre los dos tipos de curvas es bastante inesperada. Para dar un ejemplo que ilustre lo que quiero decir, durante décadas la gente ha estado tratando de atacar la criptografía de curva elíptica regular, incluidos algunos que han intentado usar enfoques basados ​​en curvas de género 2. Ninguno de estos intentos ha tenido éxito. Entonces, este intento de tener éxito en el ámbito de las isogenias es un desarrollo inesperado.

En general, hay muchas matemáticas profundas que se han publicado en la literatura matemática pero que los criptógrafos no comprenden bien. Me clasifico en la categoría de muchos investigadores que trabajan en criptografía pero que no entienden tantas matemáticas como deberíamos. Entonces, a veces, todo lo que se necesita es alguien que reconozca la aplicabilidad de las matemáticas teóricas existentes a estos nuevos criptosistemas. Eso es lo que sucedío aquí.

La versión de SIKE enviada a NIST usó un solo paso para generar la clave. Una posible variante de SIKE podría construirse en dos pasos. Jao dice que es posible que esta última variante no sea susceptible a las matemáticas que causan esta rotura. Por ahora, sin embargo, SIKE está muerto, al menos en la actualidad. El calendario para los tres candidatos restantes se desconoce actualmente.

Esta historia apareció originalmente en Ars Technica.