Se i protocolli di crittografia odierni dovessero fallire, sarebbe impossibile proteggere le connessioni online, inviare messaggi riservati, effettuare transazioni finanziarie sicure o autenticare dati. Chiunque può accedere a qualsiasi cosa; chiunque potrebbe fingere di essere chiunque. L'economia digitale crollerebbe.
Quando (o if) diventa disponibile un computer quantistico completamente funzionante, questo è esattamente ciò che potrebbe accadere. Di conseguenza, nel 2017 il National Institute of Standards and Technology (NIST) del governo degli Stati Uniti ha lanciato un concorso internazionale per trovare i modi migliori per ottenere la crittografia "post-quantistica".
Il mese scorso, l'agenzia ha selezionato il suo primo gruppo di vincitori: quattro protocolli che, con qualche revisione, verranno implementati come scudo quantico. Ha inoltre annunciato quattro candidati aggiuntivi ancora allo studio.
Poi, il 30 luglio, una coppia di ricercatori ha rivelato di averlo fatto rotto uno di quei candidati in un'ora su un laptop. (Da allora, altri hanno reso l'attacco ancora più veloce, infrangendo il protocollo in pochi minuti.) "Un attacco così drammatico e potente... è stato un vero shock", ha detto Steven Galbraith, matematico e informatico presso l'Università di Auckland in Nuova Zelanda. Non solo la matematica alla base dell'attacco è stata sorprendente, ma ha ridotto la (molto necessaria) diversità della crittografia post-quantistica, eliminando un protocollo di crittografia che funzionava in modo molto diverso dalla stragrande maggioranza degli schemi della competizione NIST.
"E 'un po' un peccato", ha detto Cristoforo Peikert, crittografo dell'Università del Michigan.
I risultati hanno lasciato la comunità della crittografia post-quantistica sia scossa che incoraggiata. Scosso, perché questo attacco (e un altro di un precedente round della competizione) ha improvvisamente trasformato quella che sembrava una porta d'acciaio digitale in un giornale bagnato. "È venuto fuori dal nulla", ha detto Dustin Moody, uno dei matematici che guidano lo sforzo di standardizzazione del NIST. Ma se uno schema crittografico sta per rompersi, è meglio che accada ben prima che venga utilizzato in natura. "Ci sono molte emozioni che ti attraversano", ha detto David Jao, un matematico dell'Università di Waterloo in Canada che, insieme al ricercatore IBM Luca De Feo, ha proposto il protocollo nel 2011. Tra queste sicuramente ci sono sorpresa e delusione. "Ma anche", ha aggiunto Jao, "almeno si è rotto ora."
Passeggiate segrete tra le curve
Jao e De Feo avevano visto un'opportunità per un sistema crittografico che fosse allo stesso tempo simile e opportunamente distinto dai protocolli ben noti. Il loro schema, chiamato protocollo Diffie-Hellman supersingular isogeny (SIDH), si occupava di curve ellittiche, gli stessi oggetti matematici utilizzati in uno dei tipi di crittografia più diffusi oggi utilizzati. Ma li ha usati in un modo completamente diverso. Era anche lo schema più compatto che il NIST stesse prendendo in considerazione (con il compromesso che era più lento di molti altri candidati).
E "matematicamente, è davvero elegante", ha detto Jao. "All'epoca, sembrava una bella idea."
Supponiamo che due parti, Alice e Bob, vogliano scambiarsi un messaggio in segreto, anche sotto lo sguardo vigile di un potenziale aggressore. Iniziano con una raccolta di punti collegati da spigoli chiamati grafo. Ogni punto rappresenta una curva ellittica diversa. Se riesci a trasformare una curva in un'altra in un modo particolare (tramite una mappa chiamata isogenia), traccia un bordo tra la coppia di punti. Il grafico risultante è enorme e facile perdersi: se fai una passeggiata relativamente breve lungo i suoi bordi, finirai in un posto che sembra completamente casuale.
I grafici di Alice e Bob hanno tutti gli stessi punti, ma i bordi sono diversi: sono definiti da isogenie diverse. Alice e Bob iniziano dallo stesso punto e ciascuno salta lungo archi casuali sul proprio grafico, tenendo traccia del proprio percorso da un punto all'altro. Ciascuno quindi pubblica la propria posizione finale ma mantiene segreto il proprio percorso.
Ora si scambiano i posti: Alice va all'ultimo punto di Bob e Bob a quello di Alice. Ognuno ripete la propria passeggiata segreta. Lo fanno in modo tale che finiranno entrambi nello stesso punto.
Questa posizione è stata trovata in segreto, quindi Alice e Bob possono usarla come chiave segreta, informazioni che consentono loro di crittografare e decrittografare i messaggi degli altri in modo sicuro. Anche se un attaccante vede i punti intermedi che Alice e Bob si scambiano, non conoscono la passeggiata segreta di Alice o Bob, quindi non riescono a capire quel punto finale.
Ma per far funzionare il SIDH, Alice e Bob hanno anche bisogno di scambiarsi alcune informazioni aggiuntive sulle loro passeggiate. Quelle informazioni extra sono ciò che ha portato alla caduta di SIDH.
Una nuova svolta sulla vecchia matematica
Tommaso Decru non ha deciso di rompere SIDH. Stava cercando di basarsi su di esso, di generalizzare il metodo per migliorare un altro tipo di crittografia. Non ha funzionato, ma ha suscitato un'idea: il suo approccio potrebbe essere utile per attaccare il SIDH. E così si avvicinò Wouter Castrick, suo collega presso l'Università Cattolica di Lovanio in Belgio e uno dei suoi ex consiglieri di dottorato, ei due si sono tuffati nella letteratura pertinente.
Si sono imbattuti in un articolo pubblicato dal matematico Ernest Kani nel 1997. In esso c'era un teorema che "era quasi immediatamente applicabile al SIDH", ha detto Castryck. "Penso che una volta che ci siamo resi conto che... l'attacco è arrivato abbastanza rapidamente, in uno o due giorni".
Alla fine, per recuperare la passeggiata segreta di Alice (e quindi la chiave condivisa), Castryck e Decru hanno esaminato il prodotto di due curve ellittiche: la curva di partenza di Alice e la curva che ha inviato pubblicamente a Bob. Questa combinazione produce un tipo di superficie chiamata superficie abeliana. Hanno quindi utilizzato queste superfici abeliane, il teorema di Kani (che mette in relazione le superfici abeliane con le curve ellittiche) e le informazioni extra che Alice ha fornito a Bob per scoprire ogni passo compiuto da Alice.
"È quasi come un segnale di riferimento che ti consente di agganciare [certe superfici abeliane]", ha detto Jao. "E quel segnale ti dice che questo è il modo in cui dovresti fare il passo successivo per trovare la [passeggiata segreta] corretta". Il che li ha portati direttamente alla chiave condivisa di Alice e Bob.
"È un approccio molto inaspettato, andare su oggetti più complicati per ricavare risultati sull'oggetto più semplice", ha detto Jao.
"Ero molto entusiasta di vedere questa tecnica utilizzata", ha detto Kristin Lauter, matematico e crittografo presso Meta AI Research che non solo ha contribuito a sviluppare la crittografia basata sull'isogenesi, ma ha anche lavorato su superfici abeliane. "Quindi vergognami per non averlo pensato come un modo per romperlo".
L'attacco di Castryck e Decru ha rotto la versione di sicurezza più bassa del protocollo SIDH in 62 minuti e il livello di sicurezza più alto in poco meno di un giorno. Poi, poco dopo, un altro esperto ha modificato l'attacco in modo che ci volessero solo 10 minuti per violare la versione a bassa sicurezza e un paio d'ore per rompere quella ad alta sicurezza. Attacchi più generali postato nelle scorse settimane rendono improbabile che SIDH possa essere salvato.
"È stata una sensazione speciale", ha detto Castryck, anche se agrodolce. "Abbiamo ucciso uno dei nostri sistemi preferiti."
Un momento spartiacque
È impossibile garantire che un sistema sia incondizionatamente sicuro. Invece, i crittografi fanno affidamento sul passare abbastanza tempo e su un numero sufficiente di persone che cercano di risolvere il problema per sentirsi sicuri. "Ciò non significa che non ti sveglierai domani e scoprirai che qualcuno ha trovato un nuovo algoritmo per farlo", ha detto Jeffrey Hoffstein, un matematico alla Brown University.
Ecco perché le competizioni come quelle del NIST sono così importanti. Nel precedente round della competizione NIST, Ward Beullens, un crittografo dell'IBM, ha ideato un attacco che ha rotto uno schema chiamato Rainbow in un fine settimana. Come Castryck e Decru, è stato in grado di mettere in scena il suo attacco solo dopo aver visto il problema matematico sottostante da un'angolazione diversa. E come l'attacco al SIDH, questo ha rotto un sistema che si basava su una matematica diversa rispetto alla maggior parte dei protocolli post-quantistici proposti.
"I recenti attacchi sono stati un momento spartiacque", ha detto Tommaso Perst, un crittografo presso l'avvio PQShield. Evidenziano quanto sia difficile la crittografia post-quantistica e quanta analisi potrebbe essere necessaria per studiare la sicurezza dei vari sistemi. "Un oggetto matematico potrebbe non avere una struttura ovvia in una prospettiva e avere una struttura sfruttabile in un'altra", ha affermato. "La parte difficile è identificare la giusta nuova prospettiva".
