SIDH y SIKE: diseño y criptoanálisis

Supersingular Isogeny Diffie-Hellman (SIDH), propuesto por Jao y De Feo en 2011, es un protocolo de intercambio de claves públicas análogo a Diffie-Hellman, pero que utiliza isogenias sobre curvas elípticas supersingulares. Ambas partes comienzan con la misma curva supersingular E sobre Fp2. Alice calcula una isogenia secreta phi_A: E -> E_A (con un núcleo aleatorio en la torsión 2^a), y publica E_A y las imágenes de los generadores de torsión de Bob mediante phi_A. Bob calcula phi_B: E -> E_B (con un núcleo aleatorio en la torsión 3^b), y publica E_B y las imágenes de los generadores de torsión de Alice mediante phi_B. Alice utiliza los datos publicados por Bob para calcular phi_A': E_B -> E_AB; Bob calcula phi_B': E_A -> E_AB. Ambos obtienen j(E_AB) como secreto compartido.

La forma especial del primo de SIDH, p = 2^a * 3^b * f - 1 (f es un cofactor pequeño para garantizar la primalidad), asegura que la curva E sobre Fp2 tenga la estructura de torsión necesaria. Para SIKEp434 (nivel 1 del NIST, seguridad poscuántica de 128 bits): p = 2^216 * 3^137 - 1, a = 216, b = 137. Esto significa que Alice recorre 216 pasos de 2-isogenias y Bob recorre 137 pasos de 3-isogenias. Tamaños de las claves: la clave pública de Alice consta de E_A más dos puntos de Fp2 (phi_A(P_B), phi_A(Q_B)) = 3 * 2 * 54 = 324 bytes. SIKEp751 está orientado a una seguridad clásica de 192 bits y cuántica de 128 bits, y tiene claves públicas de 564 bytes. Son las claves públicas más pequeñas de cualquier candidato de PQC del NIST, a cambio de ser entre 100 y 1000 veces más lentas.

SIKE (Supersingular Isogeny Key Encapsulation) es un KEM seguro frente a IND-CCA2 construido a partir de SIDH mediante la transformación de Fujisaki-Okamoto. SIKE.Encaps: se elige un mensaje aleatorio m, se calcula (c0 = SIDH public key with seed m, c1 = H2(m) XOR pk) y se envía (c0, c1). SIKE.Decaps: se recupera m a partir de c0 utilizando la clave secreta, se verifica c1, se recalcula (c0, c1) para comprobar la consistencia y se devuelve K = H3(m, c0). La transformación FO convierte el intercambio de SIDH, seguro frente a CPA, en un KEM seguro frente a CCA2. SIKE compitió en las cuatro rondas de PQC del NIST (2017-2022) y superó un extenso criptoanálisis, hasta que en julio de 2022 apareció un devastador ataque clásico.

De 2011 a 2022, SIDH resistió importantes esfuerzos de criptoanálisis. Los mejores ataques conocidos contra SIDH eran: (1) Algoritmo SSIP genérico: O(p^{1/4}) en el ámbito clásico y O(p^{1/6}) en el cuántico mediante el algoritmo de Tani. (2) Búsqueda de encuentro en el medio sobre el camino de isogenias: O(p^{1/4}) en el ámbito clásico, igual que SSIP. (3) Algoritmos en tiempo polinómico para ataques estructurales específicos (van Oorschot-Wiener): no aplicables a SIDH. Decenas de artículos analizaron la seguridad de SIDH, y durante 11 años no se encontró ningún ataque clásico o cuántico en tiempo polinómico. Este historial convirtió a SIKE en un candidato finalista creíble del NIST. La ruptura definitiva no provino de un ataque directo contra SSIP, sino de la explotación de la información auxiliar sobre los puntos de torsión de SIDH.

El 30 de julio de 2022, Wouter Castryck y Thomas Decru publicaron una prepublicación en la que demostraban un ataque clásico en tiempo polinómico contra SIDH. El ataque utiliza la información adicional contenida en los puntos de torsión auxiliares de SIDH, phi_A(P_B), phi_A(Q_B): esta información revela esencialmente la acción de phi_A sobre el subgrupo de torsión 3^b. Combinada con la curva imagen E_A, permite reconstruir el núcleo de phi_A (y, por tanto, la propia phi_A) mediante técnicas de la teoría de las curvas elípticas con multiplicación compleja y de las isogenias de Richelot. El ataque se ejecutó en 62 minutos en un portátil para SIKEp434, un conjunto de parámetros que supuestamente ofrecía una seguridad poscuántica de 128 bits. En cuestión de días, investigadores independientes confirmaron y ampliaron el ataque a todos los parámetros de SIDH.

El diseño de SIDH exigía que ambas partes publicaran las imágenes de los puntos de la base de torsión de la otra parte mediante su isogenia secreta. Esto era necesario para que el protocolo funcionara: sin phi_A(P_B) y phi_A(Q_B), Bob no podía trasladar su isogenia a la curva de Alice para calcular el secreto compartido. Sin embargo, esta información adicional —que revela la acción de phi_A restringida a la torsión 3^b— resultó contener mucha más información de la esperada, con consecuencias catastróficas. El ataque de Castryck-Decru utiliza curvas de género 2 (isogenias de Richelot) para elevar el problema a objetos de género superior, donde la acción restringida determina por completo phi_A. Esta filtración es estructural en SIDH y no puede corregirse sin cambiar el diseño fundamental del protocolo.

El 5 de julio de 2022 (antes de Castryck-Decru), el NIST había anunciado sus decisiones iniciales para la estandarización de PQC: ML-KEM (Kyber), ML-DSA (Dilithium), SLH-DSA (SPHINCS+) y FN-DSA (Falcon); SIKE no estaba entre ellas, ya que se encontraba en una segunda ronda de evaluación. El ataque de Castryck-Decru de julio de 2022 llevó al NIST a eliminar formalmente SIKE de la evaluación por completo. El NIST declaró: "SIKE ya no se considera para la estandarización." Este fue el avance criptoanalítico más drástico de la competición de PQC del NIST y demostró que incluso un esquema que había resistido 11 años de análisis podía romperse mediante una idea matemática fundamentalmente nueva.

En la semana posterior al ataque de Castryck-Decru, Thomas Decru y Luciano Maino, de forma independiente, y posteriormente Damien Robert, publicaron nuevas mejoras. La variante del ataque de Robert utiliza la misma idea, pero calcula el anillo de endomorfismos de E_A en lugar de calcular directamente el núcleo de la isogenia, y posiblemente sea más sencilla de describir matemáticamente. Estos redescubrimientos independientes y rápidos confirmaron que el ataque de Castryck-Decru había identificado una debilidad estructural fundamental, no un truco oscuro. La rapidez de los artículos posteriores también reflejó que muchos investigadores habían estudiado la filtración de los puntos de torsión de SIDH como posible vector de ataque: sabían que se trataba de una divulgación inusual de información, pero no pudieron explotarla hasta que Castryck y Decru encontraron el puente hacia el género 2.

FESTA (Fast Encryption from Supersingular Torsion Attacks, 2023) es un diseño de KEM inspirado en SIDH, pero que evita los datos auxiliares de los puntos de torsión. FESTA utiliza una estructura de protocolo diferente: la clave pública no incluye las imágenes de la base de torsión de la otra parte; en su lugar, la isogenia secreta se compromete mediante la curva imagen únicamente (sin puntos auxiliares). FESTA cifra mediante isogenias de una forma que revela menos información estructural. Los primeros análisis de seguridad indican que FESTA evita la estructura del ataque de Castryck-Decru. Sin embargo, FESTA es más reciente y ha recibido menos escrutinio que el historial de 11 años de SIKE, por lo que la comunidad de las isogenias se muestra cautelosa a la hora de desplegar nuevos esquemas antes de someterlos a un análisis exhaustivo.

La ruptura de SIKE ofrece lecciones importantes. (1) La divulgación de información auxiliar es peligrosa: los datos adicionales de los puntos de torsión de SIDH eran necesarios para el protocolo, pero filtraban información de forma fatal. Los diseñadores de protocolos deben analizar cada dato público, no solo los valores principales. (2) El historial no constituye una prueba de seguridad: 11 años sin un ataque conocido resultan tranquilizadores, pero no ofrecen ninguna garantía. Las pruebas criptográficas (reducciones a un problema difícil bien definido) son más fiables que una apelación a la autoridad o al hecho de haber superado el escrutinio. (3) Las herramientas matemáticas novedosas crean riesgos: el ataque de Castryck-Decru utilizó isogenias de Richelot de género 2, una herramienta matemática que no se había aplicado anteriormente al criptoanálisis de isogenias. Los criptoanalistas que estudien nuevas primitivas deben tener en cuenta nuevos ámbitos matemáticos.

A pesar de la ruptura de SIKE, la criptografía basada en isogenias continúa como disciplina de investigación. Las firmas SQISign (177 bytes en el nivel 1) siguen siendo las firmas de PQC conocidas más compactas y utilizan un supuesto de dificultad diferente (el problema del anillo de endomorfismos) que no se ve afectado por el ataque contra SIDH. Los protocolos basados en CSIDH utilizan la estructura de acción del grupo de clases (isogenias conmutativas) sin filtración de puntos de torsión, aunque CSIDH afronta sus propios desafíos (es más lento que SIDH en su momento y el análisis de su seguridad cuántica continúa). La comunidad de las isogenias considera la ruptura de SIKE una experiencia de aprendizaje que ha permitido comprender mejor qué información debe mantenerse oculta en los protocolos de isogenias, un conocimiento valioso para diseñar esquemas futuros.

¿Qué aspecto del diseño de SIDH permitió el ataque de Castryck-Decru?

SIDH utiliza cadenas alternas de isogenias de 2^a y 3^b entre dos partes, y comparte imágenes auxiliares de puntos de torsión para permitir el intercambio de claves. SIKE incorpora SIDH con la transformación de Fujisaki-Okamoto para proporcionar seguridad CCA2. SIKE tenía las claves más pequeñas de cualquier candidato de PQC del NIST (374 bytes), pero era entre 100 y 1000 veces más lento. Tras 11 años de seguridad, Castryck-Decru rompió SIKE en julio de 2022 mediante isogenias de Richelot de género 2 para explotar la filtración de puntos de torsión. El NIST eliminó SIKE. FESTA evita la divulgación de puntos de torsión. SQISign continúa utilizando la dificultad del problema del anillo de endomorfismos. La ruptura de SIKE demuestra que los datos públicos auxiliares deben analizarse con el mismo cuidado que los valores principales del protocolo.