Si los protocolos criptográficos actuales fallaran, sería imposible proteger las conexiones en línea: enviar mensajes confidenciales, realizar transacciones financieras seguras o autenticar datos. Cualquiera podía acceder a cualquier cosa; cualquiera podía pretender ser cualquiera. La economía digital colapsaría.
cuando (o if) una computadora cuántica completamente funcional esté disponible, eso es precisamente lo que podría suceder. Como resultado, en 2017, el Instituto Nacional de Estándares y Tecnología (NIST) del gobierno de EE. UU. lanzó una competencia internacional para encontrar las mejores formas de lograr la criptografía "poscuántica".
El mes pasado, la agencia seleccionó su primer grupo de ganadores: cuatro protocolos que, con alguna revisión, se implementarán como un escudo cuántico. También anunció cuatro candidatos adicionales que aún están bajo consideración.
Luego, el 30 de julio, un par de investigadores revelaron que habían roto uno de esos candidatos en una hora en una computadora portátil. (Desde entonces, otros han hecho que el ataque sea aún más rápido, rompiendo el protocolo en cuestión de minutos). "Un ataque que es tan dramático y poderoso... fue todo un shock", dijo. steven galbraith, matemático e informático de la Universidad de Auckland en Nueva Zelanda. Las matemáticas subyacentes al ataque no solo fueron sorprendentes, sino que redujeron la diversidad (muy necesaria) de la criptografía poscuántica, eliminando un protocolo de cifrado que funcionaba de manera muy diferente a la gran mayoría de los esquemas de la competencia NIST.
"Es un poco fastidioso", dijo cristobal peikert, un criptógrafo de la Universidad de Michigan.
Los resultados han dejado a la comunidad de criptografía poscuántica conmocionada y alentada. Conmocionado, porque este ataque (y otro de una ronda anterior de la competencia) de repente convirtió lo que parecía una puerta de acero digital en un periódico húmedo. “Salió de la nada”, dijo Dustin Malhumorado, uno de los matemáticos que lidera el esfuerzo de estandarización del NIST. Pero si un esquema criptográfico se va a romper, es mejor si sucede mucho antes de que se use en la naturaleza. “Hay muchas emociones que te atraviesan”, dijo david jao, un matemático de la Universidad de Waterloo en Canadá que, junto con el investigador de IBM luca de feo, propuso el protocolo en 2011. Ciertamente la sorpresa y la decepción están entre ellas. “Pero también”, agregó Jao, “al menos se rompió ahora”.
Paseos secretos entre curvas
Jao y De Feo habían visto la oportunidad de crear un sistema criptográfico que fuera a la vez similar y convenientemente distinto de los protocolos conocidos. Su esquema, llamado protocolo Diffie-Hellman de isogenia supersingular (SIDH), se ocupaba de curvas elípticas, los mismos objetos matemáticos utilizados en uno de los tipos de criptografía más extendidos que se implementan en la actualidad. Pero los usó de una manera completamente diferente. También era el esquema más compacto que estaba considerando NIST (con la contrapartida de que era más lento que muchos de los otros candidatos).
Y “matemáticamente, es realmente elegante”, dijo Jao. “En ese momento, me pareció una idea hermosa”.
Digamos que dos partes, Alice y Bob, quieren intercambiar un mensaje en secreto, incluso bajo la atenta mirada de un posible atacante. Comienzan con una colección de puntos conectados por aristas llamado gráfico. Cada punto representa una curva elíptica diferente. Si puede transformar una curva en otra de una manera particular (a través de un mapa llamado isogenia), dibuje un borde entre el par de puntos. El gráfico resultante es enorme y es fácil perderse en él: si da un paseo relativamente corto por sus bordes, terminará en un lugar que parece completamente aleatorio.
Los gráficos de Alice y Bob tienen todos los mismos puntos, pero los bordes son diferentes: están definidos por diferentes isogenias. Alice y Bob comienzan en el mismo punto, y cada uno salta a lo largo de bordes aleatorios en su propio gráfico, siguiendo su camino de un punto a otro. Luego, cada uno publica su ubicación final, pero mantiene su ruta en secreto.
Ahora intercambian lugares: Alice va al punto final de Bob y Bob al de Alice. Cada uno repite su paseo secreto. Lo hacen de tal manera que ambos terminarán en el mismo punto.
Esta ubicación se ha encontrado en secreto, por lo que Alice y Bob pueden usarla como su clave secreta, información que les permite cifrar y descifrar los mensajes de los demás de forma segura. Incluso si un atacante ve los puntos intermedios que Alice y Bob se envían entre sí, no conocen el camino secreto de Alice o Bob, por lo que no pueden descifrar ese punto final final.
Pero para que SIDH funcione, Alice y Bob también necesitan intercambiar información adicional sobre sus caminatas. Esa información adicional es lo que condujo a la caída de SIDH.
Un nuevo giro en las viejas matemáticas
Tomas Decru no se propuso violar el SIDH. Estaba tratando de desarrollarlo, generalizar el método para mejorar otro tipo de criptografía. Eso no funcionó, pero generó una idea: su enfoque podría ser útil para atacar al SIDH. Y así se acercó Wouter Castryck, su colega en la Universidad Católica de Lovaina en Bélgica y uno de sus ex asesores de doctorado, y los dos se sumergieron en la literatura relevante.
Tropezaron con un artículo publicado por el matemático Ernst Kani en 1997. En él había un teorema que “era casi inmediatamente aplicable a SIDH”, dijo Castryck. “Creo que una vez que nos dimos cuenta de eso… el ataque llegó bastante rápido, en uno o dos días”.
En última instancia, para recuperar el camino secreto de Alice (y, por lo tanto, la clave compartida), Castryck y Decru examinaron el producto de dos curvas elípticas: la curva inicial de Alice y la curva que le envió públicamente a Bob. Esa combinación produce un tipo de superficie llamada superficie abeliana. Luego usaron estas superficies abelianas, el teorema de Kani (que relaciona las superficies abelianas con las curvas elípticas) y la información adicional que Alice le dio a Bob para descubrir cada paso que dio Alice.
“Es casi como una señal de búsqueda que te permite fijarte en [ciertas superficies abelianas]”, dijo Jao. “Y esa señal te dice que este es el camino que debes tomar para dar el siguiente paso para encontrar la [caminata secreta] correcta”. Lo que los llevó directamente a la clave compartida de Alice y Bob.
“Es un enfoque muy inesperado, ir a objetos más complicados para obtener resultados sobre el objeto más simple”, dijo Jao.
“Estaba muy emocionado de ver que se usaba esta técnica”, dijo kristin lauter, un matemático y criptógrafo de Meta AI Research que no solo ayudó a desarrollar la criptografía basada en isogenia, sino que también trabajó en superficies abelianas. “Así que me avergüenzo por no pensar en ello como una forma de romperlo”.
El ataque de Castryck y Decru rompió la versión de seguridad más baja del protocolo SIDH en 62 minutos y el nivel de seguridad más alto en poco menos de un día. Luego, poco después, otro experto modificó el ataque para que solo tomara 10 minutos romper la versión de baja seguridad y un par de horas romper la de alta seguridad. Ataques más generales publicado en las últimas semanas hacen que sea poco probable que SIDH pueda salvarse.
“Fue un sentimiento especial”, dijo Castryck, aunque agridulce. “Matamos uno de nuestros sistemas favoritos”.
Un momento de cuenca
Es imposible garantizar que un sistema sea incondicionalmente seguro. En cambio, los criptógrafos confían en que pasa suficiente tiempo y suficientes personas que intentan resolver el problema para sentirse seguros. “Eso no significa que no te despertarás mañana y descubrirás que alguien ha encontrado un nuevo algoritmo para hacerlo”, dijo. jeffrey hoffstein, un matemático de la Universidad de Brown.
De ahí que las competencias como la del NIST sean tan importantes. En la ronda anterior de la competencia NIST, Ward Beullens, criptógrafo de IBM, ideó un ataque que rompió un esquema llamado Rainbow en un fin de semana Al igual que Castryck y Decru, solo pudo organizar su ataque después de ver el problema matemático subyacente desde un ángulo diferente. Y al igual que el ataque al SIDH, este rompió un sistema que se basaba en matemáticas diferentes a las de la mayoría de los protocolos poscuánticos propuestos.
“Los ataques recientes fueron un momento decisivo”, dijo Tomas Prest, criptógrafo de la startup PQShield. Destacan lo difícil que es la criptografía poscuántica y cuánto análisis podría ser necesario para estudiar la seguridad de varios sistemas. “Un objeto matemático puede no tener una estructura obvia en una perspectiva y tener una estructura explotable en otra”, dijo. “La parte difícil es identificar la nueva perspectiva correcta”.
