SIDH e SIKE: design e crittanalisi

Supersingular Isogeny Diffie-Hellman (SIDH), proposto da Jao e De Feo nel 2011, è un protocollo di scambio di chiavi a chiave pubblica analogo a Diffie-Hellman, ma basato sulle isogenie di curve ellittiche supersingolari. Entrambe le parti iniziano dalla stessa curva supersingolare E su Fp2. Alice calcola un'isogenia segreta phi_A: E -> E_A (con nucleo casuale nel sottogruppo di 2^a-torsione), pubblica E_A e le immagini dei generatori di torsione di Bob tramite phi_A. Bob calcola phi_B: E -> E_B (con nucleo casuale nel sottogruppo di 3^b-torsione), pubblica E_B e le immagini dei generatori di torsione di Alice tramite phi_B. Alice usa i dati pubblicati da Bob per calcolare phi_A': E_B -> E_AB; Bob calcola phi_B': E_A -> E_AB. Entrambi ottengono j(E_AB) come segreto condiviso.

La forma speciale del primo di SIDH, p = 2^a * 3^b * f - 1 (f è un piccolo cofattore usato per garantire la primalità), assicura che la curva E su Fp2 abbia la struttura di torsione necessaria. Per SIKEp434 (livello NIST 1, sicurezza post-quantistica di 128 bit): p = 2^216 * 3^137 - 1, a = 216, b = 137. Ciò significa che Alice compie 216 passi di 2-isogenie, mentre Bob ne compie 137 di 3-isogenie. Dimensioni delle chiavi: la chiave pubblica di Alice è costituita da E_A più due punti Fp2 (phi_A(P_B), phi_A(Q_B)) = 3 * 2 * 54 = 324 byte. SIKEp751 mira a una sicurezza di 192 bit classici / 128 bit quantistici e ha chiavi pubbliche di 564 byte. Si tratta delle chiavi pubbliche più piccole tra tutti i candidati PQC di NIST, al costo di una velocità da 100 a 1000 volte inferiore.

SIKE (Supersingular Isogeny Key Encapsulation) è un KEM con sicurezza IND-CCA2 costruito a partire da SIDH mediante la trasformazione di Fujisaki-Okamoto. SIKE.Encaps: scelga un messaggio casuale m, calcoli (c0 = SIDH public key with seed m, c1 = H2(m) XOR pk) e invii (c0, c1). SIKE.Decaps: recuperi m da c0 usando la chiave segreta, verifichi c1, ricalcoli (c0, c1) per controllarne la coerenza e restituisca K = H3(m, c0). La trasformazione FO converte lo scambio SIDH sicuro contro attacchi CPA in un KEM sicuro contro attacchi CCA2. SIKE ha partecipato a tutti e quattro i round della competizione PQC di NIST (2017-2022), superando un'ampia attività di criptoanalisi, fino a quando nel luglio 2022 è comparso un devastante attacco classico.

Dal 2011 al 2022, SIDH ha resistito a notevoli sforzi di criptoanalisi. I migliori attacchi noti contro SIDH erano: (1) algoritmo SSIP generico: O(p^{1/4}) nel modello classico, O(p^{1/6}) nel modello quantistico usando l'algoritmo di Tani; (2) attacco meet-in-the-middle sul percorso di isogenia: O(p^{1/4}) nel modello classico, come SSIP; (3) algoritmi in tempo polinomiale per attacchi strutturali specifici (van Oorschot-Wiener): non applicabili a SIDH. Decine di articoli hanno analizzato la sicurezza di SIDH e in 11 anni non è stato trovato alcun attacco classico o quantistico in tempo polinomiale. Questo storico rendeva SIKE un finalista credibile della competizione NIST. La rottura finale non derivò da un attacco diretto a SSIP, ma dallo sfruttamento delle informazioni sui punti di torsione ausiliari di SIDH.

Il 30 luglio 2022, Wouter Castryck e Thomas Decru pubblicarono un preprint che mostrava un attacco classico in tempo polinomiale contro SIDH. L'attacco utilizza le informazioni aggiuntive contenute nei punti di torsione ausiliari di SIDH phi_A(P_B), phi_A(Q_B): queste informazioni rivelano sostanzialmente l'azione di phi_A sul sottogruppo di 3^b-torsione. In combinazione con la curva immagine E_A, ciò consente di ricostruire il nucleo di phi_A (e quindi phi_A stessa) usando tecniche della teoria delle curve ellittiche con moltiplicazione complessa e delle isogenie di Richelot. L'attacco è stato eseguito in 62 minuti su un computer portatile per SIKEp434, un insieme di parametri che avrebbe dovuto fornire 128 bit di sicurezza post-quantistica. Nel giro di pochi giorni, ricercatori indipendenti hanno confermato ed esteso l'attacco a tutti i parametri SIDH.

La progettazione di SIDH imponeva a entrambe le parti di pubblicare le immagini dei punti della base di torsione dell'altra parte tramite la propria isogenia segreta. Ciò era necessario per il funzionamento del protocollo: senza phi_A(P_B) e phi_A(Q_B), Bob non avrebbe potuto trasferire la propria isogenia sulla curva di Alice per calcolare il segreto condiviso. Tuttavia, queste informazioni aggiuntive, che rivelano l'azione di phi_A ristretta alla 3^b-torsione, si sono rivelate una quantità di informazioni catastroficamente maggiore del previsto. L'attacco di Castryck-Decru usa curve di genere 2 (isogenie di Richelot) per portare il problema a oggetti di genere superiore, nei quali l'azione ristretta determina completamente phi_A. Questa fuga di informazioni è intrinseca alla struttura di SIDH e non può essere corretta senza modificare la progettazione fondamentale del protocollo.

Il 5 luglio 2022 (prima di Castryck-Decru), NIST aveva annunciato le proprie scelte iniziali per la standardizzazione PQC: ML-KEM (Kyber), ML-DSA (Dilithium), SLH-DSA (SPHINCS+) e FN-DSA (Falcon); SIKE non era tra queste, poiché si trovava in una seconda tornata di valutazione. L'attacco di Castryck-Decru del luglio 2022 ha portato NIST a escludere formalmente SIKE dalla valutazione. NIST ha dichiarato: "SIKE non è più preso in considerazione per la standardizzazione." Si è trattato dello sviluppo criptoanalitico più clamoroso nella competizione PQC di NIST, a dimostrazione del fatto che anche uno schema sopravvissuto a 11 anni di analisi poteva essere spezzato da un'intuizione matematica fondamentalmente nuova.

Entro una settimana dall'attacco di Castryck-Decru, Thomas Decru e Luciano Maino, indipendentemente, e in seguito Damien Robert pubblicarono ulteriori miglioramenti. La variante di Robert usa la stessa intuizione, ma calcola l'anello degli endomorfismi di E_A invece di calcolare direttamente il nucleo dell'isogenia, ed è forse più semplice da descrivere matematicamente. Queste rapide riscoperte indipendenti hanno confermato che l'attacco di Castryck-Decru aveva individuato una debolezza strutturale fondamentale, non un espediente oscuro. La rapidità degli articoli successivi rifletteva anche il fatto che molti ricercatori studiavano la fuga di informazioni dai punti di torsione di SIDH come possibile vettore d'attacco: erano consapevoli che si trattava di un'esposizione insolita di informazioni, ma non erano riusciti a sfruttarla finché Castryck e Decru non hanno trovato il collegamento con le curve di genere 2.

FESTA (Fast Encryption from Supersingular Torsion Attacks, 2023) è un progetto KEM ispirato a SIDH, ma privo dei dati ausiliari sui punti di torsione. FESTA utilizza una struttura di protocollo diversa: la chiave pubblica non include le immagini della base di torsione della controparte; l'isogenia segreta viene invece impegnata tramite la sola curva immagine (senza punti ausiliari). FESTA cifra usando isogenie in un modo che rivela meno informazioni strutturali. Le prime analisi della sicurezza suggeriscono che FESTA eviti la struttura d'attacco di Castryck-Decru. Tuttavia, FESTA è più recente e ha ricevuto un esame meno approfondito rispetto agli 11 anni di analisi di SIKE; per questo la comunità delle isogenie è cauta nell'adottare nuovi schemi prima di un'analisi estesa.

La rottura di SIKE offre importanti insegnamenti. (1) La divulgazione di informazioni ausiliarie è pericolosa: i dati aggiuntivi sui punti di torsione di SIDH erano necessari per il protocollo, ma hanno causato una fuga di informazioni fatale. Chi progetta protocolli deve analizzare ogni dato pubblico, non soltanto i valori principali. (2) Lo storico non equivale a una dimostrazione di sicurezza: 11 anni senza attacchi noti sono rassicuranti, ma non costituiscono una garanzia. Le dimostrazioni crittografiche, basate sulla riduzione a un problema difficile ben definito, sono più affidabili delle argomentazioni basate sull'autorità o sulla semplice esperienza passata. (3) Gli strumenti matematici innovativi comportano rischi: l'attacco di Castryck-Decru ha usato le isogenie di Richelot di genere 2, uno strumento matematico mai applicato prima alla criptoanalisi delle isogenie. Chi analizza nuove primitive deve prendere in considerazione nuovi ambiti matematici.

Nonostante la rottura di SIKE, la crittografia basata sulle isogenie continua a essere un ambito di ricerca. Le firme SQISign (177 byte al livello 1) restano le firme PQC più compatte conosciute e usano un'assunzione di difficoltà diversa (il problema dell'anello degli endomorfismi), non influenzata dall'attacco contro SIDH. I protocolli basati su CSIDH usano la struttura dell'azione del gruppo delle classi (isogenie commutative) senza fuga di informazioni dai punti di torsione, sebbene CSIDH presenti difficoltà proprie (è più lento di quanto fosse SIDH e l'analisi della sicurezza quantistica è ancora in corso). La comunità delle isogenie considera la rottura di SIKE un'esperienza da cui imparare, che ha affinato la comprensione di quali informazioni debbano restare nascoste nei protocolli basati sulle isogenie: una conoscenza preziosa per progettare gli schemi futuri.

SIDH usa catene alternate di 2^a e 3^b isogenie tra due parti, condividendo le immagini ausiliarie dei punti di torsione per consentire lo scambio di chiavi. SIKE applica la trasformazione di Fujisaki-Okamoto a SIDH per ottenere sicurezza CCA2. SIKE aveva le chiavi più piccole tra tutti i candidati PQC di NIST (374 byte), ma era da 100 a 1000 volte più lento. Dopo 11 anni di analisi della sicurezza, Castryck-Decru ha spezzato SIKE nel luglio 2022 usando isogenie di Richelot di genere 2 per sfruttare la fuga di informazioni dai punti di torsione. NIST ha eliminato SIKE. FESTA evita la divulgazione dei punti di torsione. SQISign continua a basarsi sulla difficoltà del problema dell'anello degli endomorfismi. La rottura di SIKE dimostra che i dati pubblici ausiliari devono essere analizzati con la stessa attenzione dei valori primari del protocollo.