Los retadores criptográficos poscuánticos son eliminados por una PC de un solo núcleo y 1 hora

imágenes falsas

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

El mes pasado, el Instituto Nacional de Estándares y Tecnología del Departamento de Comercio de EE. UU., o NIST, 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 una computadora cuántica.

En el mismo movimiento, NIST presentó cuatro algoritmos más como posibles reemplazos en espera de más pruebas con la esperanza de que uno o más de ellos también puedan ser opciones 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 aceptados, todos los cuales se basan en técnicas matemáticas completamente diferentes a las de SIKE.

Obtener totalmente SIKEd

SIKE: abreviatura de Encapsulación de clave de isogenia supersingular— ahora probablemente esté fuera de servicio gracias a una investigación publicada durante el fin de semana por investigadores del Seguridad informática y criptografía industrial grupo en KU Leuven. El documento, con el título Un ataque de recuperación eficaz en SIDH (versión preliminar), describió 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 solo toma alrededor de una hora.

“La debilidad recién 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 de la criptografía 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 el cifrado. Los usuarios hacen que su clave pública esté disponible públicamente. Mientras su clave privada permanezca en secreto, el sistema 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. A diferencia de los algoritmos de clave simétrica, las computadoras cuánticas rompen fácilmente los importantes mecanismos de encapsulación que se utilizan hoy en día. Se creía que SIKE, antes del nuevo ataque, evitaba tales vulnerabilidades mediante el uso de una construcción matemática compleja conocida como isogenígrafo supersingular.

La piedra angular de SIKE es un protocolo llamado SIDH, abreviatura de Supersingular Isogeny Diffie-Hellman. El artículo 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 las herramientas ideadas por los compañeros matemáticos Everett W. Howe, Franck Lepr´evost, y Bjorn Poonen en 2000. La nueva tecnología se basa en lo que se denomina “ataque adaptativo GPST”, que se describe en un papel 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 obtendrá:

“El ataque aprovecha que el SIDH tiene puntos de ayuda y que se conoce el grado de isogenia encubierta”, steven galbraithun profesor de matemáticas de la Universidad de Auckland y la “G” del ataque GPST adaptativo, explicó en un escritura breve 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 errores, el ataque GPST adaptativo, ataques de punto de torsión, etc.

Él continuó:

Sonido E_0 sea ​​la curva base y sea P_0, Q_0 \en E_0 tener orden 2^a. Sonido E, P, Q se da para que haya una isogenia \fi de grado 3^b con \phi : E_0 \to E, \phi(P_0) = Py \phi(Q_0) = Q

Un aspecto clave del SIDH es que uno no cuenta \fi directamente, sino como una composición de isogenias de grado 3. En otras palabras, hay una secuencia de curvas E_0 \a E_1 \a E_2 \a \cdots \a E conectados por 3-isogenias.

Esencialmente, al igual que en GPST, el ataque determina las curvas intermedias E_i y finalmente determina la clave privada. en pasos en el ataque hace una búsqueda de fuerza bruta de todos los posibles E_i \to E_{i+1}y el ingrediente mágico es un artilugio que muestra cuál tiene razón.

(Lo anterior está demasiado simplificado, las isogenias E_i \to E_{i+1} en el ataque no es de grado 3 sino de grado una pequeña fuerza de 3.)

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

Leave a Comment