Un cifrario post-quantistico è stato rotto da un processore del 2013 in un'ora

Solo poche settimane fa il NIST, l'ente statunitense preposto alla definizione degli standard, annunciava i primi quattro algoritmi per la crittografia post-quantistica. Tali algoritmi promettono di risolvere uno dei problemi più grandi creati dall'avvento dei computer quantistici: la loro capacità di rompere la crittografia a chiave pubblica usata oggi, tra le altre cose, per le comunicazioni su Internet. Quattro ulteriori algoritmi sono in una fase di considerazione per la standardizzazione per avere una maggiore varietà e, dunque, un migliore livello di sicurezza complessivo. Uno di questi, SIKE, è stato però inaspettatamente rotto e non potrà quindi diventare uno standard. Non senza una certa ironia, il cifrario è stato rotto da un computer tradizionale di potenza limitata.

Un aspetto importante da tenere a mente è che questo attacco non influisce in alcun modo sui cifrari già standardizzati: essi sono, infatti, basati su tecniche matematiche completamente differenti e senza alcuna relazione con quella usata per SIKE. I cifrari già approvati, dunque, restano sicuri, almeno fino a prova contraria.

SIKE viene rotto da un computer normale in appena un'ora

La crittografia a chiave pubblica prevede l'uso di complesse tecniche matematiche che consentono di usare due chiavi, una pubblica e una privata, per cifrare un dato: usando la chiave pubblica, solo chi è in possesso di quella privata potrà leggere i dati; dall'altro lato, chiunque può verificare che il dato è stato cifrato dal possessore della chiave privata tramite la chiave pubblica, garantendo così l'autenticità del dato stesso. L'aspetto importante è che, usando la crittografia a chiave pubblica, non è necessario che due parti abbiano già condiviso in anticipo una chiave crittografica "tradizionale": è proprio grazie a questa caratteristica che la crittografia a chiave pubblica è diventata essenziale per le comunicazioni su Internet.

I calcoli necessari per l'uso della crittografia a chiave pubblica sono, però, spesso impegnativi e per questo vengono sovente usati protocolli per lo scambio di chiavi simmetriche. Per fare un esempio pratico, collegandosi al sito della banca, il primo scambio avviene usando le chiavi pubbliche, ma viene poi concordato l'uso di un'altra chiave per cifrare le successive comunicazioni usando un algoritmo a chiave simmetrica come AES. In tal modo si ottiene un elevato livello di sicurezza, accoppiato a prestazioni superiori. Questo processo si chiama "incapsulamento".

SIKE, sigla che sta per Supersingular Isogeny Key Encapsulation (incapsulamento di chiavi tramite isogenie supersingolari), è un algoritmo proposto per la standardizzazione pensato proprio per sostituire quelli attuali, vulnerabili agli attacchi da parte dei computer quantistici. Parte di SIKE è il protocollo SIDH, ovvero Supersingular Isogeny Diffie-Hellman (Diffie-Hellman tramite isogenie supersingolari): di fatto, il protocollo di scambio della chiave simmetrica spiegato più sopra usando un algoritmo di cifratura a prova di attacco da parte dei computer quantistici.

O così si credeva. Durante il fine settimana, infatti, alcuni ricercatori dell'Universita di Leuven, nei Paesi Bassi, hanno pubblicato uno studio preliminare in cui affermano di essere riusciti a rompere il nuovo algoritmo con un computer tradizionale in meno di un'ora. Per essere specifici, i ricercatori hanno usato un singolo core di un processore Intel Xeon E5-2630v2, lanciato nel 2013. I ricercatori riceveranno ora 50.000 dollari, messi in palio dal NIST.

SIKE usa le isogenie: semplificando molto, delle trasformazioni matematiche (morfismi di gruppi algebrici, in gergo tecnico) per effettuare trasformazioni da una curva A a una curva B. L'attacco trovato dai ricercatori si basa sul fatto che tali trasformazioni non vengono compiute direttamente, ma tramite passaggi intermedi: determinando le curve intermedie è possibile risalire alla chiave usata per la cifratura e, di fatto, rompere l'algoritmo.

L'attacco è valido per l'algoritmo pubblicato, che prevede l'uso di un passo per generare la chiave. In teoria, è possibile che l'uso di un algoritmo con due passi non sia suscettibile allo stesso attacco e risulti dunque sicuro. Tuttavia, per il momento SIKE è da considerare fuori dai giochi, quantomeno nell'incarnazione attuale.

Problemi difficili (anche da analizzare in cerca di problemi)

Non è il primo caso in cui algoritmi considerati per la standardizzazione nel concorso indetto dal NIST vengono rotti. A febbraio era stato il turno di Rainbow, che era considerato fra i favoriti ed era già stato adottato, molto prematuramente, anche per alcune blockchain.

Perché però questi attacchi sono venuti alla luce solo ora, dopo anni di scrutinio intenso e continuo? La risposta è che gli algoritmi usati per la crittografia si basano su problemi difficili: tale termine viene impiegato per parlare dell'estrema difficoltà nel risolverli da parte dei computer, con tempi di risoluzione che arrivano ai miliardi di anni, ma in questo caso possiamo dire che siano difficili anche nell'approccio da parte delle persone.

Parlando ad Ars Technica, David Jao, uno degli inventori di SIKE, ha spiegato che "è vero che l'attacco usa concetti matematici che sono stati pubblicati negli anni Novanta e Duemila. In un certo senso, l'attacco non richiede nuova matematica; avrebbe potuto essere notato in qualunque momento. Un aspetto inaspettato dell'attacco è che usa curve di genere 2 per attaccare le curve ellittiche (che sono curve di genere 1). Una connessione tra i due tipi di curve è piuttosto inattesa. Per dare un esempio di ciò che intendo, per decenni si è cercato di attaccare la crittografia basata sulle curve ellittiche, e alcuni hanno cercato di usare approcci basati su curve di genere 2. Nessuno di questi tentativi ha avuto successo, quindi è uno sviluppo inatteso che questo tentativo abbia avuto successo nel campo delle isogenie. In generale c'è molta matematica che è stata pubblicata in letteratura ma che non è ben compresa dai crittografi. Mi metto in questa categoria dei molti ricercatori che lavorano nel campo della crittografia ma non capiscono la matematica come dovrebbero. Talvolta, dunque, tutto ciò che serve è che qualcuno riconosca la possibilità di applicare la matematica teoretica esistente a questi nuovi crittosistemi. È ciò che è avvenuto in questo caso."

È importante notare come questo risultato possa apparire negativo, ma sia in realtà esattamente il motivo per cui gli algoritmi crittografici vengono sottoposti a fasi di critica pubblica. Se non si procedesse in questo modo, il rischio sarebbe che algoritmi deboli venissero standardizzati, magari implementati anche in hardware, solo per scoprire successivamente che esisteva un attacco in grado di romperli. È dunque d'uopo, ancora una volta, rimarcare come la collaborazione attiva e aperta porti ai risultati migliori. Grazie a processi aperti e pubblici è possibile coinvolgere persone con esperienze e conoscenze diverse, così da arrivare ai migliori risultati possibili.