El contendiente de cifrado poscuántico es eliminado por una PC de un solo núcleo y 1 hora

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 la cuarta ronda destaca los riesgos involucrados en la estandarización de la próxima generación de algoritmos de cifrado.

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 ataques de una computadora cuántica.

En el mismo movimiento, NIST presentó cuatro algoritmos adicionales como posibles reemplazos 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.

Obtener totalmente SIKEd

SIKE: abreviatura de Encapsulación de clave de isogenia supersingular– es probable que ahora esté fuera de circulación gracias a una investigación que fue publicada durante el fin de semana por investigadores de la Seguridad Informática y Criptografía Industrial grupo en KU Leuven. El documento, titulado Un ataque de recuperación de clave eficiente 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 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 de microsoft

.

“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 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 antes se habían conocido 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 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 herramientas ideadas por sus colegas 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 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 vas a estar:

“El ataque explota el hecho de que SIDH tiene puntos auxiliares y que se conoce el grado de la isogenia secreta”, steven galbraithprofesor de matemáticas de la Universidad de Auckland y la “G” en el ataque adaptativo GPST, explicó en un redacción corta en el nuevo ataque. “Los puntos auxiliares en SIDH siempre han sido una molestia y una potencial debilidad, y han sido explotados para ataques de fallas, el ataque adaptativo GPST, ataques de puntos de torsión, etc.

Él continuó:

Dejar sea ​​la curva base y sea tener orden . Dejar darse tal que exista una isogenia de grado con , y

Un aspecto clave de SIDH es que uno no calcula directamente, sino como una composición de isogenias de grado 3. En otras palabras, hay una secuencia de curvas conectados por 3-isogenias.

Esencialmente, como en GPST, el ataque determina las curvas intermedias y por lo tanto finalmente determina la clave privada. al paso el ataque hace una búsqueda de fuerza bruta de todos los posibles y el ingrediente mágico es un gadget que muestra cuál es el correcto.

(Lo anterior está demasiado simplificado, las isogenias en el ataque no son de grado 3 sino de grado una pequeña potencia de 3.)

Más importante que entender las matemáticas, Jonathan Katz, miembro de IEEE y profesor en el departamento de informática 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”.