SIDH og SIKE: Design og kryptoanalyse

Supersingular Isogeny Diffie-Hellman (SIDH), som blev foreslået af Jao og De Feo i 2011, er en offentlig nøgleudvekslingsprotokol, der minder om Diffie-Hellman, men bruger isogenier på supersingulære elliptiske kurver. Begge parter starter med den samme supersingulære kurve E over Fp2. Alice beregner en hemmelig isogeni phi_A: E -> E_A (med en tilfældig kerne i 2^a-torsionen) og offentliggør E_A samt billederne af Bobs torsionsgeneratorer under phi_A. Bob beregner phi_B: E -> E_B (med en tilfældig kerne i 3^b-torsionen) og offentliggør E_B samt billederne af Alices torsionsgeneratorer under phi_B. Alice bruger Bobs offentliggjorte data til at beregne phi_A': E_B -> E_AB, mens Bob beregner phi_B': E_A -> E_AB. Begge når frem til j(E_AB) som den fælles hemmelighed.

SIDH's særlige primtalsform p = 2^a * 3^b * f - 1 (f er en lille kofaktor, der sikrer, at p er et primtal) sikrer, at kurven E over Fp2 har den nødvendige torsionsstruktur. For SIKEp434 (NIST-niveau 1, 128-bit postkvantesikkerhed): p = 2^216 * 3^137 - 1, a = 216, b = 137. Det betyder, at Alice går 216 trin ad en kæde af 2-isogenier, mens Bob går 137 trin ad en kæde af 3-isogenier. Nøglestørrelser: Alices offentlige nøgle er E_A plus to Fp2-punkter (phi_A(P_B), phi_A(Q_B)) = 3 * 2 * 54 = 324 byte. SIKEp751 sigter mod 192-bit klassisk sikkerhed / 128-bit kvantesikkerhed og har offentlige nøgler på 564 byte. Det er de mindste offentlige nøgler blandt alle NIST-PQC-kandidater — på bekostning af, at de er 100-1000 gange langsommere.

SIKE (Supersingular Isogeny Key Encapsulation) er en IND-CCA2-sikker KEM, der er bygget fra SIDH ved hjælp af Fujisaki-Okamoto-transformationen. SIKE.Encaps: vælg en tilfældig meddelelse m, beregn (c0 = SIDH public key with seed m, c1 = H2(m) XOR pk), og send (c0, c1). SIKE.Decaps: gendan m fra c0 ved hjælp af den hemmelige nøgle, verificer c1, beregn (c0, c1) igen for at kontrollere konsistensen, og returner K = H3(m, c0). FO-transformationen omdanner den CPA-sikre SIDH-udveksling til en CCA2-sikker KEM. SIKE deltog i alle fire runder af NIST PQC (2017-2022) og modstod omfattende kryptoanalyse — indtil et ødelæggende klassisk angreb dukkede op i juli 2022.

Fra 2011 til 2022 modstod SIDH en betydelig indsats inden for kryptoanalyse. De bedst kendte angreb på SIDH var: (1) Den generiske SSIP-algoritme: O(p^{1/4}) klassisk og O(p^{1/6}) ved hjælp af kvanteberegning med Tanis algoritme. (2) Møde-i-midten på isogeni-stien: O(p^{1/4}) klassisk, det samme som SSIP. (3) Polynomielle algoritmer til specifikke strukturelle angreb (van Oorschot-Wiener): ikke anvendelige på SIDH. Snesevis af artikler analyserede SIDH's sikkerhed, og der blev ikke fundet noget polynomielt klassisk eller kvantebaseret angreb i 11 år. Denne historik gjorde SIKE til en troværdig NIST-finalist. Det endelige brud kom ikke fra et direkte angreb på SSIP, men fra udnyttelse af SIDH's oplysninger om hjælpetorsionspunkter.

Den 30. juli 2022 offentliggjorde Wouter Castryck og Thomas Decru et fortryk, der viste et klassisk angreb på SIDH i polynomiel tid. Angrebet bruger de ekstra oplysninger i SIDH's hjælpetorsionspunkter phi_A(P_B), phi_A(Q_B): Disse oplysninger afslører i praksis phi_A's virkning på 3^b-torsionsundergruppen. Sammen med billedkurven E_A gør det det muligt at rekonstruere kernen i phi_A (og dermed selve phi_A) ved hjælp af teknikker fra teorien om elliptiske kurver med kompleks multiplikation og Richelot-isogenier. Angrebet tog 62 minutter på en bærbar computer for SIKEp434 — et parametersæt, der skulle levere 128-bit postkvantesikkerhed. Inden for få dage bekræftede uafhængige forskere angrebet og udvidede det til alle SIDH-parametre.

SIDH's udformning krævede, at begge parter offentliggjorde billederne af den anden parts torsionsbasispunkter under deres hemmelige isogeni. Det var nødvendigt for, at protokollen kunne fungere: Uden phi_A(P_B) og phi_A(Q_B) kunne Bob ikke transportere sin isogeni til Alices kurve for at beregne den fælles hemmelighed. Men disse ekstra oplysninger — som afslører phi_A's virkning begrænset til 3^b-torsionen — viste sig at indeholde katastrofalt meget mere information end forventet. Castryck-Decru-angrebet bruger genus-2-kurver (Richelot-isogenier) til at løfte problemet til objekter af højere genus, hvor den begrænsede virkning fuldstændigt bestemmer phi_A. Denne informationslækage er strukturelt indbygget i SIDH og kan ikke løses uden at ændre protokollens grundlæggende udformning.

Den 5. juli 2022 (før Castryck-Decru) havde NIST offentliggjort sine indledende valg til PQC-standardisering: ML-KEM (Kyber), ML-DSA (Dilithium), SLH-DSA (SPHINCS+) og FN-DSA (Falcon) — SIKE var ikke blandt dem (den var med i en anden vurderingsrunde). Castryck-Decru-angrebet i juli 2022 fik NIST til formelt at fjerne SIKE helt fra overvejelserne. NIST erklærede: "SIKE overvejes ikke længere med henblik på standardisering." Dette var den mest dramatiske kryptoanalytiske udvikling i NIST's PQC-konkurrence og viste, at selv et kryptografisk system, der havde modstået 11 års analyse, kunne brydes af en grundlæggende ny matematisk indsigt.

Inden for en uge efter Castryck-Decru offentliggjorde Thomas Decru og Luciano Maino uafhængigt af hinanden og senere Damien Robert yderligere forbedringer. Roberts variant af angrebet bruger den samme indsigt, men beregner endomorfi-ringen for E_A i stedet for direkte at beregne isogeniens kerne, og den er muligvis enklere at beskrive matematisk. Disse hurtige, uafhængige genopdagelser bekræftede, at Castryck-Decru-angrebet havde identificeret en grundlæggende strukturel svaghed og ikke en obskur finte. De efterfølgende artiklers hurtige fremkomst afspejlede også, hvor mange forskere der havde studeret SIDH's lækage af torsionspunkter som en mulig angrebsvektor. De var klar over, at der var tale om en usædvanlig offentliggørelse af oplysninger, men kunne ikke udnytte den, før Castryck og Decru fandt broen til genus-2.

FESTA (Fast Encryption from Supersingular Torsion Attacks, 2023) er en KEM-udformning, der er inspireret af SIDH, men undgår hjælpedata om torsionspunkter. FESTA bruger en anden protokolstruktur: Den offentlige nøgle indeholder ikke billeder af modpartens torsionsbasis — i stedet forpligtes den hemmelige isogeni kun gennem billedkurven (ingen hjælpepunkter). FESTA krypterer ved hjælp af isogenier på en måde, der afslører mindre strukturel information. Tidlige sikkerhedsanalyser tyder på, at FESTA undgår Castryck-Decru-angrebets struktur. FESTA er dog nyere og har været underkastet mindre granskning end SIKE's 11-årige historik, og isogeni-miljøet er forsigtigt med at tage nye systemer i brug før omfattende analyser.

SIKE's brud giver vigtige lærdomme. (1) Offentliggørelse af hjælpeoplysninger er farlig: SIDH's ekstra data om torsionspunkter var nødvendige for protokollen, men lækkede oplysninger på fatal vis. Protokoludformere skal analysere hvert eneste offentlige dataelement, ikke kun de primære værdier. (2) En sikkerhedshistorik er ikke et sikkerhedsbevis: 11 år uden et kendt angreb er betryggende, men ingen garanti. Kryptografiske beviser (reduktion til et veldefineret svært problem) er mere pålidelige end argumenter baseret på autoritet eller det forhold, at systemet har modstået granskning. (3) Nye matematiske værktøjer skaber risici: Castryck-Decru-angrebet brugte genus-2-Richelot-isogenier — et værktøj fra matematikken, som ikke tidligere var blevet anvendt i isogeni-kryptoanalyse. Kryptoanalytikere, der undersøger nye primitiver, skal tage nye matematiske områder i betragtning.

Trods SIKE's brud fortsætter isogenibaseret kryptografi som forskningsområde. SQISign-signaturer (177 byte på niveau 1) er fortsat de mest kompakte kendte PQC-signaturer og bruger en anden antagelse om beregningsmæssig sværhedsgrad (problemet med endomorfi-ringen), som ikke påvirkes af SIDH-angrebet. CSIDH-baserede protokoller bruger klassegruppens virkningsstruktur (kommutative isogenier) uden lækage fra torsionspunkter, selv om CSIDH har sine egne udfordringer (langsommere end SIDH var, og analysen af kvantesikkerheden er stadig i gang). Isogeni-miljøet ser SIKE-bruddet som en lærerig erfaring, der har skærpet forståelsen af, hvilke oplysninger der skal holdes skjult i isogeni-protokoller — værdifuld viden til udformningen af fremtidige systemer.

SIDH bruger skiftevis kæder af 2^a- og 3^b-isogenier mellem to parter og deler billeder af hjælpetorsionspunkter for at muliggøre nøgleudvekslingen. SIKE bygger SIDH ind i Fujisaki-Okamoto-transformationen for at opnå CCA2-sikkerhed. SIKE havde de mindste nøgler blandt alle NIST-PQC-kandidater (374 byte), men var 100-1000 gange langsommere. Efter 11 års sikkerhedsanalyse brød Castryck-Decru SIKE i juli 2022 ved hjælp af genus-2-Richelot-isogenier for at udnytte lækagen fra torsionspunkterne. NIST fjernede SIKE. FESTA undgår offentliggørelse af torsionspunkter. SQISign fortsætter med at bruge sværhedsgraden af problemet med endomorfi-ringen. SIKE-bruddet illustrerer, at supplerende offentlige data skal analyseres lige så omhyggeligt som protokollens primære værdier.