SIDH et SIKE : conception et cryptanalyse

Supersingular Isogeny Diffie-Hellman (SIDH), proposé par Jao et De Feo en 2011, est un protocole d’échange de clés à clé publique analogue à Diffie-Hellman, mais qui utilise des isogénies sur des courbes elliptiques supersingulières. Les deux parties commencent avec la même courbe supersingulière E sur Fp2. Alice calcule une isogénie secrète phi_A: E -> E_A (noyau choisi aléatoirement dans la 2^a-torsion), puis publie E_A et les images des générateurs de torsion de Bob par phi_A. Bob calcule phi_B: E -> E_B (noyau choisi aléatoirement dans la 3^b-torsion), puis publie E_B et les images des générateurs de torsion d’Alice par phi_B. Alice utilise les données publiées par Bob pour calculer phi_A': E_B -> E_AB ; Bob calcule phi_B': E_A -> E_AB. Tous deux obtiennent j(E_AB) comme secret partagé.

La forme spéciale du nombre premier de SIDH p = 2^a * 3^b * f - 1 (f est un petit cofacteur garantissant la primalité) assure que la courbe E sur Fp2 possède la structure de torsion nécessaire. Pour SIKEp434 (niveau 1 de NIST, sécurité post-quantique de 128 bits) : p = 2^216 * 3^137 - 1, a = 216, b = 137. Cela signifie qu’Alice parcourt 216 étapes d’isogénies de degré 2, tandis que Bob en parcourt 137 d’isogénies de degré 3. Tailles des clés : la clé publique d’Alice est constituée de E_A et de deux points Fp2 (phi_A(P_B), phi_A(Q_B)) = 3 * 2 * 54 = 324 octets. SIKEp751 vise une sécurité classique de 192 bits et une sécurité quantique de 128 bits, avec des clés publiques de 564 octets. Ce sont les plus petites clés publiques de tous les candidats PQC de NIST, au prix d’une vitesse 100 à 1 000 fois inférieure.

SIKE (encapsulation de clés par isogénies supersingulières) est un KEM sécurisé contre les attaques IND-CCA2, construit à partir de SIDH au moyen de la transformée de Fujisaki-Okamoto. SIKE.Encaps : choisir un message aléatoire m, calculer (c0 = clé publique SIDH avec m comme graine, c1 = H2(m) XOR pk), puis envoyer (c0, c1). SIKE.Decaps : récupérer m depuis c0 à l’aide de la clé secrète, vérifier c1, recalculer (c0, c1) pour contrôler la cohérence, puis produire K = H3(m, c0). La transformée FO convertit l’échange SIDH sécurisé contre les attaques CPA en un KEM sécurisé contre les attaques CCA2. SIKE a participé aux quatre tours de la compétition PQC de NIST (2017-2022), résistant à une cryptanalyse approfondie, jusqu’à ce qu’une attaque classique dévastatrice apparaisse en juillet 2022.

De 2011 à 2022, SIDH a résisté à d’importants efforts de cryptanalyse. Les meilleures attaques connues contre SIDH étaient les suivantes : (1) algorithme SSIP générique : O(p^{1/4}) sur le plan classique, O(p^{1/6}) sur le plan quantique au moyen de l’algorithme de Tani. (2) Attaque par rencontre au milieu sur le chemin d’isogénies : O(p^{1/4}) sur le plan classique, comme pour SSIP. (3) Algorithmes en temps polynomial pour des attaques structurelles particulières (van Oorschot-Wiener) : ils ne s’appliquent pas à SIDH. Des dizaines d’articles ont analysé la sécurité de SIDH, et aucune attaque classique ou quantique en temps polynomial n’a été trouvée en 11 ans. Ce bilan a fait de SIKE un finaliste crédible de NIST. La rupture finale ne provenait pas d’une attaque directe contre SSIP, mais de l’exploitation des informations auxiliaires sur les points de torsion de SIDH.

Le 30 juillet 2022, Wouter Castryck et Thomas Decru ont publié une prépublication présentant une attaque classique en temps polynomial contre SIDH. L’attaque exploite les informations supplémentaires contenues dans les points de torsion auxiliaires de SIDH phi_A(P_B), phi_A(Q_B) : ces informations révèlent essentiellement l’action de phi_A sur le sous-groupe de 3^b-torsion. Combinées à la courbe image E_A, elles permettent de reconstruire le noyau de phi_A (et donc phi_A elle-même) grâce à des techniques issues de la théorie des courbes elliptiques à multiplication complexe et des isogénies de Richelot. L’attaque a été exécutée en 62 minutes sur un ordinateur portable pour SIKEp434 — un jeu de paramètres censé offrir une sécurité post-quantique de 128 bits. En quelques jours, des chercheurs indépendants ont confirmé l’attaque et l’ont étendue à tous les paramètres de SIDH.

La conception de SIDH exigeait que les deux parties publient les images des points de base de torsion de l’autre partie par leur isogénie secrète. Cela était nécessaire au fonctionnement du protocole : sans phi_A(P_B) et phi_A(Q_B), Bob ne pouvait pas transporter son isogénie sur la courbe d’Alice afin de calculer le secret partagé. Mais ces informations supplémentaires — qui révèlent l’action de phi_A restreinte à la 3^b-torsion — se sont révélées divulguer une quantité d’informations catastrophiquement supérieure à ce qui était prévu. L’attaque de Castryck-Decru utilise des courbes de genre 2 (isogénies de Richelot) pour relever le problème vers des objets de genre supérieur, où l’action restreinte détermine complètement phi_A. Cette fuite est structurelle dans SIDH et ne peut pas être corrigée sans modifier la conception fondamentale du protocole.

Le 5 juillet 2022 (avant Castryck-Decru), NIST avait annoncé ses choix initiaux pour la standardisation de la PQC : ML-KEM (Kyber), ML-DSA (Dilithium), SLH-DSA (SPHINCS+) et FN-DSA (Falcon) — SIKE n’en faisait pas partie, car il était encore étudié au deuxième tour. L’attaque de Castryck-Decru, en juillet 2022, a conduit NIST à éliminer officiellement SIKE de toute étude ultérieure. NIST a déclaré : « SIKE n’est plus à l’étude pour la standardisation. » Il s’agissait de la découverte cryptanalytique la plus spectaculaire de la compétition PQC de NIST, démontrant que même un schéma ayant résisté à 11 années d’analyse pouvait être brisé par une intuition mathématique fondamentalement nouvelle.

Dans la semaine qui a suivi Castryck-Decru, Thomas Decru et Luciano Maino, indépendamment l’un de l’autre, puis Damien Robert ont publié de nouvelles améliorations. La variante de l’attaque de Robert exploite la même intuition, mais calcule l’anneau des endomorphismes de E_A au lieu de calculer directement le noyau de l’isogénie ; elle est donc sans doute plus simple à décrire mathématiquement. Ces redécouvertes indépendantes et rapides ont confirmé que l’attaque de Castryck-Decru avait mis au jour une faiblesse structurelle fondamentale, et non une astuce obscure. La rapidité des articles ultérieurs reflétait également le nombre de chercheurs qui étudiaient la fuite d’informations par les points de torsion de SIDH comme vecteur d’attaque potentiel : ils savaient qu’il s’agissait d’une divulgation d’informations inhabituelle, mais ne parvenaient pas à l’exploiter jusqu’à ce que Castryck et Decru découvrent le lien avec le genre 2.

FESTA (chiffrement rapide fondé sur des attaques de torsion supersingulière, 2023) est une conception de KEM inspirée de SIDH, mais qui évite les données auxiliaires sur les points de torsion. FESTA utilise une structure de protocole différente : la clé publique ne comprend pas les images des points de base de torsion de l’autre partie ; l’isogénie secrète est au contraire engagée uniquement au moyen de la courbe image, sans points auxiliaires. FESTA chiffre au moyen d’isogénies d’une manière qui révèle moins d’informations structurelles. Les premières analyses de sécurité suggèrent que FESTA évite la structure d’attaque de Castryck-Decru. Cependant, FESTA est plus récent et a fait l’objet de moins d’examens que SIKE au cours de ses 11 années d’existence, et la communauté des isogénies reste prudente quant au déploiement de nouveaux schémas avant une analyse approfondie.

La rupture de SIKE offre d’importantes leçons. (1) La divulgation d’informations auxiliaires est dangereuse : les données supplémentaires sur les points de torsion de SIDH étaient nécessaires au protocole, mais ont divulgué des informations fatales. Les concepteurs de protocoles doivent analyser chaque donnée publique, et pas seulement les valeurs principales. (2) Un historique de sécurité n’est pas une preuve de sécurité : 11 années sans attaque connue sont rassurantes, mais ne constituent pas une garantie. Les preuves cryptographiques (réduction à un problème difficile bien défini) sont plus fiables qu’un argument d’autorité ou que le simple fait d’avoir résisté à un examen approfondi. (3) Les nouveaux outils mathématiques créent des risques : l’attaque de Castryck-Decru a utilisé les isogénies de Richelot de genre 2 — un outil mathématique qui n’avait jamais été appliqué auparavant à la cryptanalyse des isogénies. Les cryptanalystes qui étudient de nouvelles primitives doivent prendre en compte de nouveaux domaines mathématiques.

Malgré la rupture de SIKE, la cryptographie fondée sur les isogénies continue d’être un domaine de recherche. Les signatures SQISign (177 octets au niveau 1) restent les signatures PQC les plus compactes connues et reposent sur une hypothèse de difficulté différente (le problème de l’anneau des endomorphismes), que l’attaque contre SIDH n’affecte pas. Les protocoles fondés sur CSIDH utilisent la structure de l’action du groupe des classes (isogénies commutatives), sans fuite de points de torsion, même si CSIDH rencontre ses propres difficultés (il est plus lent que ne l’était SIDH, et l’analyse de sa sécurité quantique est toujours en cours). La communauté des isogénies considère la rupture de SIKE comme une expérience riche en enseignements, qui a permis de mieux comprendre quelles informations doivent être masquées dans les protocoles fondés sur les isogénies — des connaissances précieuses pour concevoir les futurs schémas.

SIDH utilise des chaînes alternées d’isogénies 2^a et 3^b entre deux parties, qui partagent les images de points de torsion auxiliaires pour permettre l’échange de clés. SIKE enveloppe SIDH avec la transformée de Fujisaki-Okamoto afin d’assurer la sécurité CCA2. SIKE possédait les plus petites clés de tous les candidats PQC de NIST (374 octets), mais était 100 à 1 000 fois plus lent. Après 11 années de sécurité, Castryck-Decru a brisé SIKE en juillet 2022 au moyen d’isogénies de Richelot de genre 2, afin d’exploiter la fuite d’informations par les points de torsion. NIST a éliminé SIKE. FESTA évite la divulgation d’informations sur les points de torsion. SQISign continue de s’appuyer sur la difficulté du problème de l’anneau des endomorphismes. La rupture de SIKE montre que les données publiques auxiliaires doivent être analysées avec autant de soin que les valeurs principales du protocole.