La crittografia post-quantistica è arrivata: capiamo come funziona

I computer quantistici oggi disponibili non sono sufficientemente potenti da costituire una minaccia per gli attuali sistemi crittografici, ma tutte le previsioni dicono che quelli del futuro lo saranno. Per questo nel 2016 il NIST, il National Institute for Standards and Technology statunitense, ha indetto una gara per definire un nuovo standard sugli algoritmi crittografici da usare in futuro, affinché questi siano a prova di attacchi da parte dei computer quantistici. Il risultato di questa competizione è una serie di quattro algoritmi: CRYSTALS-Kyber, CRYSTALS-Dilithium, FALCON e SPHINCS+. Tali algoritmi fonderanno le basi della crittografia futura.

Perché servono nuovi algoritmi resistenti ai computer quantistici?

Le attuali comunicazioni elettroniche si basano su variazioni dello stesso concetto: quello della cosiddetta crittografia a chiave pubblica. Semplificando, tale forma di crittografia sfrutta il fatto che per i computer classici è molto difficile (nel senso che è estremamente dispendioso in termini di tempo) effettuare alcuni calcoli. Ci sono diversi problemi difficili su cui si basano i cifrari a chiave pubblica, come le curve ellittiche, i logaritmi discreti o la fattorizzazione di un numero nelle sue componenti prime.

Prendendo quest'ultimo esempio, è facile prendere due numeri primi e moltiplicarli per ottenere un risultato, ma è molto difficile da tale risultato risalire ai due numeri primi originari. Tale difficoltà cresce significativamente al crescere della dimensione dei numeri, al punto che anche il più potente supercomputer al mondo necessiterebbe di migliaia di anni per effettuare i calcoli necessari.

La crittografia a chiave pubblica è così chiamata perché ci sono due chiavi: una privata e una, per l'appunto, pubblica, prodotte usando proprio numeri primi molto grandi. È particolarmente utile per scambiare dati senza concordare prima una chiave condivisa: ecco dunque che, se devo collegarmi al sito della banca, questa mi fornisce una chiave pubblica con la quale posso cifrare le informazioni da inviare, e solo la banca stessa, con la chiave privata in suo possesso, potrà poi decifrare le informazioni che ho inviato.

L'utilità della chiave pubblica sta proprio nel fatto che chiunque può inviare informazioni usando tale chiave, ma la decifrazione può avvenire solo quando si è in possesso della chiave privata: ciò assicura che la comunicazione sia protetta. Tipicamente questo processo viene usato per l'invio di una chiave di un cifrario simmetrico, come ad esempio AES: un algoritmo, dunque, che richiede una singola chiave per decifrare i dati, e che dev'essere quindi condivisa tra più parti, perché senza di essa non è possibile procedere con la decifrazione.

Il problema di questo processo è che si basa sull'assunto che i computer classici non siano in grado di risalire alla chiave privata in tempi ragionevoli. Tale assunto non è però più vero nel caso dei computer quantistici, come dimostrato nel 1994 da Peter Shor, che pubblicò un algoritmo (noto come "algoritmo di Shor" in suo onore) col quale mostrava come un computer quantistico fosse in grado di calcolare i fattori primi di un numero in tempi relativamente brevi. Usando termini più tecnicamente corretti, Shor dimostrò come con il suo algoritmo fosse possibile effettuare la fattorizzazione in numeri primi in tempo polinomiale anziché esponenziale; una simile dimostrazione fu data anche per il problema dei logaritmi discreti, usati anch'essi in alcuni cifrari a chiave pubblica per le stesse ragioni di intrattabilità con i computer classici.

Alessandro Curioni, direttore della ricerca in Europa per IBM, spiega: "la teoria dell'informazione quantistica è completamente diversa rispetto a quella classica e ha delle peculiarità per cui certi problemi che sono molto difficili da trattare con i computer classici, sono trattati in modo molto efficiente dai computer quantistici. Ciò significa che con un computer quantistico la complessità computazionale di questi problemi viene ridotta, quindi non è più esponenziale, ma polinomiale o lineare. Un problema che non era trattabile, quindi, diventa trattabile.

"La cosa interessante è che i problemi che hanno queste caratteristiche non sono problemi qualsiasi: sono problemi connessi, ad esempio, con la simulazione del mondo fisico reale (molecole, atomi e quindi farmaci e materiali), che al giorno d'oggi sono simulabili in maniera molto approssimativa. Un'altra classe di problemi è quella dell'ottimizzazione: l'ottimizzazione globale scala in modo combinatoriale, per cui ottimizzare un problema con molte variabili non è possibile in modo accurato con i computer classici. C'è anche la classe dei problemi algebrici collegati, ad esempio, al machine learning: con i computer quantistici sarà possibile creare algoritmi di machine learning più accurati con meno dati.

"Come tutte le tecnologie trasformative, però, i computer quantistici possono avere sia un impatto positivo, sia uno negativo, a seconda di come vengono usati: i computer quantistici, a causa delle loro caratteristiche, fanno passare il problema della fattorizzazione in numeri primi da uno a complessità molto alta a uno a complessità molto bassa, per cui renderanno possibile la rottura delle chiavi di crittografia usate oggi, ad esempio per trasmettere i dati o per le firme digitali. Ed è interessante notare che questo è stato proprio il primo ambito in cui si è dimostrato che i computer quantistici sono in grado di abbattere la complessità computazionale di un problema rispetto ai modelli classici."

In altre parole, è stato dimostrato come i computer quantistici siano in grado di eseguire in maniera estremamente efficiente quelle operazioni che minano alla base la sicurezza dell'infrastruttura di comunicazione su cui si fonda la società di oggi.

Nonostante quest'affermazione sia molto forte, non c'è, però, motivo di farsi prendere dal panico. I computer quantistici attuali (come quello nell'immagine qui sopra) sono infatti ben lontani dal poter violare i sistemi crittografici che usiamo tutti i giorni. In prospettiva, però, ci si attende che computer quantistici sufficientemente potenti arrivino nel corso del prossimo decennio o poco più, e qui sta il problema: dato che la crittografia è impiegata in quasi ogni aspetto della tecnologia odierna, ci vorrà del tempo per andare a implementare nuovi algoritmi crittografici che risultino resistenti agli attacchi dei computer quantistici e bisogna, dunque, cominciare ad agire ora per non farsi trovare impreparati.

"È un problema gigantesco", continua Curioni, "perché se riesco a rompere la crittografia classica posso entrare in qualunque computer e in qualunque conto bancario, posso rompere la blockchain, posso cambiare le firme digitali. Quando potremo fare questo, l'IT che conosciamo oggi non esisterà più. Quello che facciamo come azienda, quando avviamo lo sviluppo di queste tecnologie trasformative, è vedere quali sono i possibili problemi e capire se è possibile creare qualcosa a livello infrastrutturale o algoritmico che possa mitigare i possibili problemi. In questo caso, sapendo che la crittografia poteva essere rotta, abbiamo cominciato a fare ricerca (come tante altre istituzioni nel mondo) su algoritmi crittografici alternativi che, essendo fatti in modo diverso, hanno una struttura tale che è difficile da attaccare con i computer classici, ma è anche molto difficile da attaccare con i computer quantistici."

Il problema non è presente nel caso dei cifrari a chiave simmetrica. "Per questi sistemi un attacco di un computer quantistico fa calare la forza del cifrario del 50%", ci spiega Andrea Visconti, professore associato di Crittografia presso l'Università degli Studi di Milano. "Questo vuol dire che, ad esempio, usando AES a 128 bit, con un computer quantistico la sua forza è ridotta a 64 bit; la soluzione è usare AES a 256 bit, cosa che fa calare la forza a 128 bit che è più che sufficiente. Lo stesso ragionamento si può fare con gli altri cifrari a chiave simmetrica. Il trucco dunque è allungare la chiave, senza dover cambiare lo standard internazionale."

Come funzionano i nuovi algoritmi approvati dal NIST

"È molto più facile creare algoritmi a chiave simmetrica che a chiave pubblica e questo è il motivo per cui il NIST ha voluto indire questa grande competizione: perché volevano molte idee che potessero poi essere messe alla prova e ridotte di numero, fino a ottenere qualcosa che sia utilizzabile nell'era quantistica", ci dice Michael Osborne, uno dei ricercatori di IBM Research che si è occupato dello sviluppo dei nuovi algoritmi."Si tratta, dunque, di scegliere degli algoritmi con una prospettiva di una trentina d'anni per la sicurezza dei dati."

Pseudocodice per la generazione di chiavi con CRYSTALS-Kyber

Con questo obiettivo, i nuovi algoritmi sono stati sviluppati usando due tipi di approcci: CRYSTALS-Kyber, CRYSTALS-Dilithium e FALCON sono basati sui reticoli ordinati, mentre SPHINCS+ usa le funzioni di hash. Quattro algoritmi ulteriori sono in fase di valutazione e si basano su altri problemi. CRYSTALS-Kyber è l'unico algoritmo per la cifratura generale, ed è pertanto assimilabile a un sostituto di algoritmi attuali come RSA, usati ad esempio per il collegamento sicuro ai siti Web.

Ma come funzionano gli algoritmi basati sui reticoli ordinati? "Immaginiamo di avere uno schema bidimensionale in cui mettiamo molti punti; trovare il vettore più piccolo per andare da un punto A a un punto B in una rete bidimensionale è facile, ma su uno schema a N dimensioni cercare il vettore più corto (o uno tra quelli corti) è un problema assai difficile e neanche la potenza di un computer quantistico consente di farlo [efficientemente]", ci dice Visconti, che specifica come questo sia un esempio del tipo di difficoltà computazionale posta dai problemi basati sui reticoli ordinati. "I reticoli sono stati usati parecchio all'interno della gara sui cifrari post quantum per questo."

Osborne ci spiega che ci vogliono diversi anni per sviluppare un nuovo cifrario e che il processo è iterativo (si parte da una base e si apportano miglioramenti in nuove versioni del cifrario), con numerose squadre di lavoro che vengono coinvolte per assicurarsi che i vari requisiti necessari alla standardizzazione vengano soddisfatti: tra questi, ad esempio, il fatto che l'algoritmo funzioni su diverse piattaforme hardware, oppure che non sia vulnerabile ad attacchi di tipo side channel noti.

"Ci sono tanti algoritmi che si possono sviluppare ma, in fin dei conti, bisogna dimostrare: che l'algoritmo funziona, che effettivamente non può essere attaccato facilmente, ma anche che dal punto di vista dell'utilizzo è sostenibile (che non richiede quindi troppa memoria o troppa potenza di calcolo), che è abbastanza generale da rimanere valido anche se cambia l'hardware sottostante... C'è tanta ricerca", dice Curioni. "La cosa interessante dei nuovi algoritmi è che non sono più costosi dal punto di vista computazionale: sono risultati essere, anzi, ancora meglio rispetto a quelli passati. Per diventare quantum safe non abbiamo ora qualcosa che è più difficile da trattare di prima: alcuni dei nuovi algoritmi sono più veloci e più efficienti, quindi non c'è nessuna ragione per non fare questo passaggio dal vecchio al nuovo il prima possibile e prima che sia disponibile un computer quantistico in grado di rompere i cifrari attuali."

"Quando c'è una sfida per trovare qualcosa di diverso," continua Curioni, "quando stai cercando di guardare fuori dal tuo orto, allora hai l'opportunità di diventare migliore anche per i casi standard, semplicemente perché in passato sei arrivato a un punto in cui ti sei accontentato, ma è quando fai un passo in più che allarghi gli orizzonti del campo anche per le applicazioni standard."

Questo passaggio è, poi, interessante anche per un altro motivo. All'inizio del 2021 IBM aveva annunciato che avrebbe commercializzato per la prima volta la sua tecnologia legata alla crittografia omomorfica, che permette di effettuare operazioni sui dati senza decifrarli. Tale tecnologia si basa sugli stessi concetti matematici alla base degli algoritmi CRYSTAL e di FALCON. Ciò è particolarmente interessante perché, secondo Curioni, "decisamente arriveremo al punto in cui non solo avremo cifrari quantum safe, ma saranno anche completamente omomorfici. Dall'altro lato, la cifratura completamente omomorfica era già resistente ai computer quantistici." Tale tecnologia è già usata, ad esempio, sui mainframe IBM z16 (in foto sopra).

Come sarà il passaggio alla cifratura resistente ai computer quantistici?

Nonostante la pubblicazione dei primi quattro algoritmi considerati resistenti ai computer quantistici, ci vorrà comunque del tempo prima che questi vengano implementati all'interno dei vari dispositivi che fanno uso della crittografia.

"Prima di arrivare ad avere tutto quantum safe, ci sarà un momento in cui se hai un'infrastruttura IT, dovrai fare un'analisi per vedere dove i rischi sono maggiori, dove ha senso fare un cambiamento dei cifrari, per cui ci sarà molto lavoro di consulenza per fare quest'analisi. Una delle cose più difficili all'inizio, anche se non sembra, sarà trovare nell'infrastruttura tutti i posti dove è usata la crittografia", spiega Curioni. "Sembra una cosa facile, ma non lo è per niente, perché ogni pezzo di software ha la sua interfaccia crittografica e, con un'infrastruttura grande, si possono averne decine di migliaia o più di questi pezzi di software. È per questo motivo che il Governo americano ha emanato un ordine esecutivo per chiedere a tutte le agenzie nazionali di fare un inventario di tutti i posti dove è usata la crittografia, e queste richieste arriveranno dappertutto. Arriveremo a una situazione simile a quella che abbiamo avuto per il Millennium Bug, dove si sapeva che avrebbero potuto esserci problemi e si è intervenuti."

Il periodo in cui vedremo l'adozione dei nuovi standard sarà di qualche anno, ma già ora è possibile adottare i nuovi algoritmie implementarli all'interno dei propri software. La difficoltà maggiore sarà implementarli nei vari dispositivi come router, switch e altre componenti hardware collocate a volte in luoghi non facilmente accessibili. Ci sarà però anche un momento in cui il fatto di offrire i nuovi cifrari sarà motivo di distinzione dei prodotti offerti che darà un vantaggio a chi sarà più rapido ad adottare le nuove tecniche.

Resta, comunque, il fatto che il processo sarà relativamente veloce e sarà compiuto ben prima che siano disponibili commercialmente computer quantistici con sufficiente potenza da costituire una minaccia. Non c'è, dunque, alcuna ragione di avere timore che i dati, personali e aziendali, siano a rischio nel breve termine. "L'impatto iniziale [di computer quantistici sufficientemente potenti], in ogni caso, sarà sulle infrastrutture più sensibili, non certo sui nostri conti in banca", afferma, ridendo, Curioni.

Anche se i nuovi algoritmi sono ritenuti resistenti agli attacchi, rimane un fondo di incertezza come sempre avviene nel mondo della crittografia: è necessario infatti ricordare che molti algoritmi che hanno fatto la storia, come DES, si sono poi rivelati deboli in almeno una versione (o in quasi tutte, come appunto nel caso di DES). È dunque possibile che in futuro gli algoritmi appena diventati standard si rivelino deboli ad attacchi di qualche tipo: o computazionali, grazie a computer quantistici in grado di eseguire operazioni più velocemente o in maniera differente rispetto a quanto previsto, o algoritmici, per via di debolezze intrinseche nel modo in cui funzionano i cifrari che li espongono ad attacchi vari.

"Abbiamo un modello di come funzionano i computer quantistici e di ciò che possono elaborare, quindi possiamo creare modelli che tengano conto di ciò esattamente come facciamo con i computer classici. Ciò non preclude che ci possano essere sviluppi significativi in futuro che cambieranno tutto, ma questo è il motivo per cui al NIST sono stati proposti algoritmi basati su diversi problemi difficili [nel senso che richiedono tempi estremamente lunghi per essere risolti, NdR]", dice Osborne. "E ciò ci porta al fatto che sarà importante, in futuro, non solo sostituire i cifrari che usiamo ora, ma cambiare il modo in cui usiamo la crittografia così che possiamo adattarci ai cambiamenti futuri: il mondo dei computer quantistici è in evoluzione repentina e possiamo fare solo delle stime di come saranno le cose in futuro, dunque bisogna far sì che le applicazioni possano essere cambiate velocemente per rispondere a queste evoluzioni."

"Non c'è una dimostrazione matematica che i nuovi cifrari non possano essere rotti da futuri computer quantistici", conferma Curioni. "Quando facciamo questo passaggio ai cifrari quantum safe, al posto che semplicemente adottarli dovremmo passare al concetto che noi chiamiamo 'crypto agility', ovvero un nuovo sistema che permette di usare i nuovi cifrari ma, se in futuro sarà necessario cambiarli nuovamente, non impone di dover rifare tutto dall'inizio. Si tratta dunque di creare un'infrastruttura di cifratura che permetta di passare molto più facilmente da un cifrario a un altro senza dover intervenire nuovamente nel sistema. Questa è la strategia che cercheremo di mettere in piedi."

Gli algoritmi approvati non sono comunque gli unici: ce ne sono altri quattro che sono ancora al vaglio del NIST e che potrebbero diventare standard in futuro. Si basano su problemi diversi, come diceva Osborne, proprio per evitare di mettere tutte le uova in un solo paniere.

"Sono stati scelti tre algoritmi per la firma digitale, di cui due basati sui reticoli e uno sulle funzioni di hash, mentre per la componente asimmetrica ce n'è uno solo ed è basato sui reticoli. Questo non va bene, perché se i reticoli si riveleranno deboli per qualche ragione, anche solo perché qualcuno trova un'idea per 'bucarli', ci troveremo in ginocchio: non è possibile avere una soluzione che si basa solo ed esclusivamente sui reticoli", dice Visconti. "Il NIST sta procedendo dunque con altri algoritmi, che affronteranno una 'fase quattro' [dopo le tre che hanno portato a standardizzare i quattro algoritmi già citati, NdR] e che sono basati su problemi diversi per dare un'alternativa plausibile e un 'piano B'. In questo caso gli algoritmi sono stati esclusi dalla standardizzazione durante la 'fase tre', per affrontare la standardizzazione nella 'fase quattro' non per problemi di sicurezza, ma magari per problemi di prestazioni o di implementazione.

"È la prima volta che il NIST dà un paniere di vincitori al posto di uno solo. Nei casi passati, basti pensare a SHA3 o AES, arrivavano in finale 5 candidati, di cui uno solo vinceva. L'algoritmo 'principe' è quello che viene poi implementato da tutti e che viene considerato per le implementazioni spinte dall'hardware, e presumo che ciò accadrà per CRYSTALS-Kyber, ma gli altri rimarranno comunque nel paniere anche se non saranno la prima scelta."

C'è poi da fare un ultimo appunto. Per quanto lo standard sia approvato dal NIST, è in realtà il frutto di un lavoro corale da parte di più organizzazioni internazionali e l'Europa ha avuto (e continua ad avere) un ruolo chiave. In questo caso il ruolo è stato sia nella ricerca, dato che gli algoritmi sono stati sviluppati in larga parte presso i laboratori di IBM a Zurigo, sia nella definizione stessa degli standard, con l'ETSI, l'ente europeo degli standard, che ha avuto un ruolo primario.

Non è da dimenticare nemmeno il contributo dato dalle università europee e italiane. "Il ruolo delle università è prendere i cifrari e analizzarli, verificando sia gli aspetti di sicurezza che di prestazioni. Come Università degli Studi di Milano abbiamo scelto alcuni cifrari, sperando che arrivassero il più avanti possibile nella gara [tra questi ci sono SPHINCS+, che è risultato vincitore, e Classic McEliece, che è arrivato alla 'fase quattro', NdR], e li abbiamo analizzati e abbiamo fatto anche delle pubblicazioni in questa direzione. Il lavoro da fare è stato tantissimo; di fatto diventa il primo lavoro per molti anni, per cui bisogna accantonare il resto durante questo processo", afferma Visconti.

"Siamo molto fieri del lavoro che abbiamo fatto", conclude Curioni, "perché abbiamo aiutato a definire la crittografia del futuro. Non ci sono molte cose nell'informatica che sono così pervasive come la crittografia: nemmeno la CPU è così pervasiva, perché non ce n'è una sola. La crittografia, invece, è dappertutto, e senza di essa non c'è sicurezza. Non c'è informatica."