Criptografía poscuántica: nuevo algoritmo "desaparecido en 60 minutos"

Hemos escrito sobre PQC, abreviatura de criptografía post-cuántica, varias veces antes.

En caso de que te hayas perdido toda la emoción de los medios de los últimos años sobre la llamada computación cuántica...

…es (si me permite lo que algunos expertos probablemente considerarán una simplificación excesiva e imprudente) una forma de construir dispositivos informáticos que puedan realizar un seguimiento de múltiples resultados posibles de un cálculo al mismo tiempo.

Con mucho cuidado, y tal vez un poco de suerte, esto significa que puede reescribir algunos tipos de algoritmos para encontrar la respuesta correcta, o al menos descartar correctamente una gran cantidad de respuestas incorrectas, sin intentar y probar todos los resultados posibles. uno a uno.

Dos interesantes aceleraciones criptoanalíticas son posibles utilizando un dispositivo de computación cuántica, suponiendo que realmente se pueda construir uno adecuadamente potente y confiable:

• Algoritmo de búsqueda cuántica de Grover. Por lo general, si desea buscar un conjunto de respuestas ordenadas al azar para ver si la suya está en la lista, esperaría revisar toda la lista, en el peor de los casos, antes de obtener una respuesta definitiva. Por ejemplo, si quisiera encontrar la clave de descifrado AES de 128 bits para descifrar un documento, tendría que buscar en la lista de todas las claves posibles, comenzando por 000..001, ..2, ..3, y así sucesivamente, hasta llegar a FFF..FFF (16 bytes por valor de FF), para estar seguro de completar el problema. En otras palabras, tienes que presupuestar para probar los 2¹²⁸ posibles claves antes de encontrar la clave correcta o determinar que no había una. El algoritmo de Grover, sin embargo, dado un ordenador cuántico lo suficientemente grande y potente, afirma ser capaz de completar la misma hazaña con el raíz cuadrada del esfuerzo habitual, descifrando así el código, en teoría, en sólo 2⁶⁴ intenta en su lugar.
• Algoritmo de factorización cuántica de Shor. Varios algoritmos de encriptación contemporáneos se basan en el hecho de que la multiplicación de dos números primos grandes se puede hacer rápidamente, mientras que dividir su producto entre los dos números con los que comenzó es casi imposible. Para tener una idea de esto, intente multiplicar 59 × 87 con lápiz y papel. Puede tomar un minuto más o menos sacarlo (5133 es la respuesta), pero no es tan difícil. Ahora intenta de otra manera. Divide, digamos, 4171 en sus dos factores. ¡Mucho más duro! (Es 43×97). Ahora imagina hacer esto con un número que tiene 600 dígitos. Hablando en términos generales, está atascado tratando de dividir el número de 600 dígitos por cada número primo posible de 300 dígitos hasta que gane el premio gordo o descubra que no hay una respuesta. El algoritmo de Shor, sin embargo, promete resolver este problema con la logaritmo del esfuerzo habitual. Por lo tanto, factorizar un número de 2048 dígitos binarios debería llevar solo el doble de tiempo que factorizar un número de 1024 bits, no el doble que factorizar un número de 2047 bits, lo que representa una gran aceleración.

Contrarrestando la amenaza

La amenaza del algoritmo de Grover se puede contrarrestar simplemente aumentando el tamaño de los números que está utilizando al elevarlos al cuadrado, lo que significa duplicar la cantidad de bits en su hash criptográfico o su clave de cifrado simétrica. (En otras palabras, si cree que SHA-256 está bien en este momento, usar SHA-512 en su lugar proporcionaría una alternativa resistente a PQC).

Pero el algoritmo de Shor no se puede contrarrestar tan fácilmente.

Una clave pública de 2048 bits necesitaría aumentar su tamaño exponencialmente, no simplemente al cuadrado, de modo que en lugar de una clave de 2 × 2048 = 4096 bits, necesitaría una nueva clave con el tamaño imposible de 2²⁰⁴⁸ pedacitos…

…o tendría que adoptar un tipo completamente nuevo de sistema de encriptación poscuántica al que no se aplica el algoritmo de Shor.

Bueno, el organismo estadounidense de normalización NIST ha estado ejecutando un PQC “competencia” desde finales de 2017.

El proceso ha estado abierto a todos, con todos los participantes bienvenidos, todos los algoritmos publicados abiertamente y el escrutinio público no solo posible sino también alentado activamente:

Llamar para propuestas. [Cerrado el 2017-11-30]. […] Se pretende que los nuevos estándares de criptografía de clave pública especifiquen uno o más algoritmos de firma digital, cifrado de clave pública y establecimiento de claves adicionales no clasificados y divulgados públicamente que están disponibles en todo el mundo y son capaces de proteger información gubernamental confidencial. bien en el futuro previsible, incluso después de la llegada de las computadoras cuánticas.

Después de tres rondas de presentaciones y debates, NIST anunció, el 2022-07-05, que había elegido cuatro algoritmos que consideraba "estándares" con efecto inmediato, todos con nombres que suenan deliciosos: CRYSTALS-KYBER, CRYSTALS-Dilithium, FALCONy SPHINCS+.

El primero (CRYSTALS-KYBER) se usa como lo que se llama un Mecanismo de acuerdo clave (KEM), donde dos extremos de un canal de comunicación público crean de forma segura una clave de cifrado privada de un solo uso para intercambiar los datos de una sesión de forma confidencial. (Simplemente pon: los fisgones solo obtienen repollo rallado, por lo que no pueden escuchar a escondidas la conversación.)

Los otros tres algoritmos se utilizan para Firmas digitales, por lo que puede asegurarse de que los datos que recibió en su extremo coincidan exactamente con los que el remitente puso en el otro, evitando así la manipulación y asegurando la integridad. (Simplemente pon: si alguien intenta corromper o manipular los datos, lo sabrá.)

Se necesitan más algoritmos

Al mismo tiempo que anunciaba los nuevos estándares, NIST también anunció un cuarta ronda de su competencia, presentando otros cuatro algoritmos como posibles KEM alternativos. (Recuerde que, al momento de escribir este artículo, ya tenemos tres algoritmos de firma digital aprobados para elegir, pero solo un KEM oficial).

Éstas eran: BIKE, Classic McEliece, HQC y SIKE.

Curiosamente, el Algoritmo McEliece fue inventado en la década de 1970 por el criptógrafo estadounidense Robert Mc Eliece, quien murió en 2019, mucho después de que el concurso del NIST ya estuviera en marcha.

Sin embargo, nunca tuvo éxito porque requería grandes cantidades de material clave en comparación con la popular alternativa del momento, el algoritmo Diffie-Hellman-Merkle (DHM, o a veces solo DH).

Desafortunadamente, uno de los tres algoritmos de la cuarta ronda, a saber SIKE, parece haber sido agrietado.

En un artículo que retuerce el cerebro titulado UN ATAQUE EFICIENTE DE RECUPERACIÓN DE CLAVE EN SIDH (VERSIÓN PRELIMINAR), los criptógrafos belgas Wouter Castryk y Thomas Decru parecen haber asestado un golpe mortal al algoritmo SIKE

En caso de que te lo estés preguntando, SIKE es la abreviatura de Encapsulación de clave de isogenia supersingular, y SIDH significa Isogenia supersingular Diffie-Hellman, un uso específico de la Algoritmo SIKE mediante el cual dos extremos de un canal de comunicación realizan una "criptodanza" similar a DHM para intercambiar un montón de datos públicos que permiten que cada extremo obtenga un valor privado para usar como una clave de cifrado secreta de un solo uso.

No vamos a tratar de explicar el ataque aquí; simplemente repetiremos lo que afirma el documento, a saber, que:

En pocas palabras, las entradas aquí incluyen los datos públicos proporcionados por uno de los participantes en el cryptodance de establecimiento clave, junto con los parámetros predeterminados (y por lo tanto conocidos públicamente) utilizados en el proceso.

Pero el resultado que se extrae (la información denominada la isogenia φ arriba) se supone que es la parte nunca revelada del proceso: la llamada clave privada.

En otras palabras, solo a partir de la información pública, como los datos intercambiados abiertamente durante la configuración de la clave, los criptógrafos afirman poder recuperar la clave privada de uno de los participantes.

Y una vez que conoce mi clave privada, puede hacerse pasar por mí de manera fácil e indetectable, por lo que el proceso de encriptación se rompe.

Aparentemente, el algoritmo de descifrado de claves tarda aproximadamente una hora en hacer su trabajo, utilizando solo un núcleo de CPU con el tipo de potencia de procesamiento que encontraría en una computadora portátil común.

Eso va en contra del algoritmo SIKE cuando se configura para cumplir con el Nivel 1, el grado básico de seguridad de cifrado de NIST.

¿Qué hacer?

¡Nada!

(Esas son las buenas noticias.)

Como sugieren los autores del artículo, después de señalar que su resultado aún es preliminar, "con el estado actual de las cosas, SIDH parece estar completamente roto para cualquier curva base generada públicamente".

(Esas son las malas noticias.)

Sin embargo, dado que el algoritmo SIKE aún no está aprobado oficialmente, ahora puede adaptarse para frustrar este ataque en particular (algo que los autores admiten que puede ser posible) o simplemente eliminarse por completo.

Pase lo que pase finalmente con SIKE, este es un excelente recordatorio de por qué intentar inventar sus propios algoritmos de encriptación está lleno de peligros.

También es un claro ejemplo de por qué los sistemas de encriptación patentados que se basan en el secreto del propio algoritmo para mantener su seguridad son simplemente inaceptables en 2022.

Si un algoritmo PQC como SIKE sobrevivió a la persuasión y al sondeo de expertos de todo el mundo durante más de cinco años, a pesar de haber sido divulgado específicamente para que pudiera estar sujeto al escrutinio público...

…entonces no hay necesidad de preguntarse qué tan bien funcionarán sus algoritmos de encriptación hechos en casa y ocultos a la vista cuando se liberen en la naturaleza.

---