Con crittografia post quantistica si intende l’ambito della crittografia che si occupa dello studio e dello sviluppo di algoritmi crittografici che ad ora sono ritenuti sicuri perfino contro attacchi eseguibili da un computer quantistico.
Introduzione alla crittografia post-quantistica
La crittografia post quantistica sfrutta la matematica pura per creare algoritmi crittografici che siano in grado di essere eseguiti su computer convenzionali attuali e che permettano la trasmissione di un certo messaggio su un canale di trasmissione non sicuro. Tale ambito non deve essere confuso con quello della crittografia quantistica, che invece si basa su proprietà della meccanica quantistica fornite dalla fisica per rendere un certo canale di comunicazione sicuro per uno scambio di messaggi tra due entità.
La crittografia post quantistica (spesso chiamata con l’acronimo PQC, ovvero “Post-Quantum Cryptography”) ha avuto molto interesse e numerosi sviluppi in questi ultimi anni. Infatti, gli studiosi teorici e i programmatori hanno realizzato l’importanza di anticipare il prima possibile l’aggiornamento degli algoritmi crittografici utilizzati per prevenire problemi nel giorno in cui i computer quantistici saranno resi disponibili ai consumatori. Per comprendere bene questa attività di prevenzione, bisogna capire ad alto livello quali tra gli algoritmi tipicamente utilizzati in una comunicazione via Internet sono particolarmente a rischio.
Le categorie della crittografia: un esempio di messaggistica medica
Per permettere a due entità di comunicare in maniera sicura utilizzando un canale di comunicazione non sicuro come l’Internet, varie categorie di algoritmi crittografici sono utilizzati. Tra le categorie più famose, troviamo le firme digitali, lo scambio di chiavi e la crittografia simmetrica. Per dare giusto un’introduzione ad alto livello di queste categorie, consideriamo il seguente scenario.
La firma digitale
Immaginiamo che, dopo il primo controllo medico in un centro specializzato, qualche infermiera del centro voglia inviarci un file PDF contenente alcune nostre informazioni sanitarie tramite un sistema di messaggistica apposito. Tipicamente, ci si può aspettare che il sistema di messaggistica faccia le tre seguenti azioni. Innanzitutto, viene utilizzato un algoritmo di firma digitale sul PDF. Il nome della categoria è indicativo: l’idea è che tale algoritmo crea una firma digitale, ovvero una serie di dati che, inviati insieme al PDF, ci permettono di controllare l’identità dell’infermiera e l’integrità del PDF trasmesso (ovvero, il fatto che nessun attaccante ha modificato le informazioni contenute nel PDF). Inoltre, grazie a una firma digitale, noi siamo anche in grado di dimostrare a terzi, come ad esempio al nostro medico di fiducia, che la firma è davvero stata generata dall’infermiera (questa proprietà è chiamata in gergo non ripudio, visto che l’infermiera non può, in futuro, ripudiare la sua firma, dichiarando di non averla mai effettuata).
Lo scambio di chiavi
A seguire, il sistema di messaggistica esegue un algoritmo di scambio di chiavi. Come suggerisce il nome, l’obiettivo di questo algoritmo è scambiare una chiave tra l’infermiera e noi, dove in questo contesto “chiave” assume il significato di una certa informazione digitale comune tra le due entità, ma nascosta agli esterni. La situazione è meno banale di quella che ci potremmo inizialmente aspettare, visto che questo scambio deve avvenire sfruttando messaggi che passano attraverso un canale di comunicazione non sicuro. Nonostante questa mancanza di sicurezza, esistono algoritmi e procedure che sfruttano una manciata di messaggi e alcune computazioni aggiuntive da far svolgere a entrambe le entità per far avvenire questo scambio di chiavi. Naturalmente, i molteplici messaggi e le computazioni aggiuntive complicano parecchio l’algoritmo di scambio, rendendolo alquanto lento e inefficiente. Per questo gli algoritmi di scambio di chiave sono usati per inviare solo piccole chiavi alla volta.
La crittografia simmetrica
Infine, il sistema di messaggistica sfrutta un algoritmo di crittografia simmetrica. Questi algoritmi sono facili da implementare, piccoli di dimensione e veloci da eseguire, ed è per questo che sono largamente utilizzati per garantire una trasmissione sicura di lunghi messaggi o molteplici messaggi tra due entità. Visto che noi e l’infermiera siamo gli unici possessori della chiave che ci siamo appena scambiati nel punto precedente, l’algoritmo di chiave simmetrica prende la chiave dell’infermiera e critta il PDF contenente informazioni sanitarie e la corrispondente firma. Questa operazione di crittazione può essere paragonata a quella di chiudere a chiave un cofanetto con dentro il PDF e la firma. È proprio tale cofanetto ad essere inviato su Internet. A questo punto, il sistema di messaggistica scelto fa in modo di recapitare a noi il messaggio, di utilizzare la nostra copia della chiave per estrarre il PDF e la firma, e di controllare la firma.
Tenendo a mente questo esempio, vediamo come la sicurezza della categoria di algoritmi appena elencati sarà intaccata dal commercio di computer quantistici.
Impatto dei computer quantistici sulla crittografia attuale
Gli algoritmi di crittografia simmetrica, tutto sommato, resisteranno bene all’avvento dei computer quantistici. Basta pensare ad AES, ovvero all’Advanced Encryption Standard. Questo algoritmo è stato standardizzato dal NIST tramite una competizione pubblica all’inizio degli anni 2000 e dovrà semplicemente essere aggiornato in modo da prendere in considerazione chiave lunghe il doppio di quelle usate attualmente per resistere in modo soddisfacente.
Purtroppo, la situazione per gli algoritmi di firma digitale e di scambio di chiave non è altrettanto rosea. Infatti, queste due categorie di algoritmi sono molto simili in pratica (entrambe sono sotto-categorie della più vasta crittografia asimmetrica) e si basano su uno di tre calcoli matematici che risultano intrattabili da svolgere in un tempo utile in un computer tradizionale. Queste proprietà sono: la fattorizzazione di interi, il logaritmo discreto sui campi finiti e il logaritmo discreto sulle curve ellittiche (su cui, rispettivamente, RSA, ElGamal ed ECDSA sono costruiti).
Senza entrare troppo nel dettaglio matematico, possiamo intuitivamente comprendere la difficoltà di questi calcoli dicendo quanto segue: per un computer tradizionale, è facile moltiplicare tra di loro due quantità, mentre risulta arduo estrarre gli elementi ignoti che sono stati moltiplicati tra di loro per ottenere una certa quantità nota. Questa semplicità di calcolo da un lato contrapposta alla difficoltà di risolvere il calcolo dall’altro sta alla base degli algoritmi della crittografia asimmetrica.
È chiaro che la situazione risulta critica se si pensa che, nel contesto di computer quantistici, è stato già ideato un algoritmo (detto algoritmo di Shor) in grado di risolvere in tempo utile il problema di estrarre gli elementi moltiplicati tra loro. Quest’algoritmo è ancora solo teorico e non è ancora stato implementato su larga scala, ma il fatto che possa esistere una banalizzazione del problema principale su cui abbiamo finora costruito algoritmi di firma digitale è di scambio di chiavi ha giustamente causato una reazione nei vari crittografi del mondo. Sapendo che un aggiornamento degli attuali sistemi di crittografia richiederà molto tempo, è giusto giocare di anticipo e iniziare già da ora a ideare e standardizzare nuovi algoritmi crittografici di crittografia asimmetrica che, almeno in teoria, possano resistere anche ad ogni attacco finora conosciuto lanciabile sia da computer tradizionali sia da quelli quantistici.
Il ruolo del NIST e il processo di standardizzazione
Anche il NIST ha sottolineato la necessità di standardizzare nuovi algoritmi crittografici in grado di resistere a ogni algoritmo quantistico finora creato. L’istituto statunitense NIST (National Institute of Standard and Technology) ha lo scopo di rilasciare generiche linee guide o standard stringenti che devono essere seguiti attentamente da qualsiasi ente governativo USA che si occupa di trattare dati sensibili. Chiaramente, gli standard rilasciati dal NIST sono presi molto in considerazione anche nelle altre parti del mondo, non solo perché i file provenienti dall’istituto sono ottimi punti di riferimenti sia per rendere inter-operabili i sistemi informatici sia per generare altri standard nazionali o internazionali, ma soprattutto perché il processo di selezione dei nuovi standard avviene in modo trasparente e aperto al pubblico.
Per quanto inizialmente possa sembrare controintuitivo, gli studiosi e i programmatori spingono molto su un processo di selezione di nuovi algoritmi che non sia privato. Infatti, i crittografi hanno realizzato che la sicurezza di un sistema crittografico non deve dipendere dal tenere segreto il design di un algoritmo. La storia mostra che algoritmi prodotti in segretezza o senza ascoltare opinioni pubbliche (come gli algoritmi di crittografia simmetrica GOST e DES) sono risultati deboli e sono stati deprecati (ovvero, il loro uso è sconsigliato e sono considerati non sicuri). Ad oggi, si applica il più possibile il cosiddetto principio di Kerckhoffs, che afferma quanto segue: la sicurezza di un algoritmo crittografico deve dipendere dalla scelta e dalla segretezza della chiave, mentre bisogna intendere ogni altro aspetto dell’algoritmo come dominio pubblico.
Considerando quanto detto, è ovvio che il processo di standardizzazione per la crittografia post quantistica aperto dal NIST nel 2016 ha riscosso molto successo e interesse. L’obiettivo di tale processo è stato quello di selezionare algoritmi crittografici asimmetrici resistenti ad attacchi quantistici. All’inizio, 82 algoritmi sono stati canditati e sottomessi allo scrutinio del NIST e della comunità crittografica mondiale. Dopo vari anni di analisi, raffinamento, studio, scoperta di attacchi su alcuni algoritmi proposti e round di selezione sempre più esclusivi, siamo ora giunti di fronte a 4 algoritmi vincitori. Tre di essi sono già diventati standard (FIPS 203, FIPS 204 e FIPS 205 del 13 Agosto 2024), mentre il quarto (FALCON) è un algoritmo di firma digitale che sarà presto rilasciato all’interno di uno standard. Vediamo questi tre nuovi standard crittografici leggermente più in dettaglio.
ML-KEM: il meccanismo di incapsulamento di chiave
FIPS 203 definisce un algoritmo che viene accorciato con la sigla ML-KEM (“Module-Lattice-Based Key-Encapsulation Mechanism”) e che deriva dall’algoritmo vincitore chiamato CRYSTALS-KYBER. Come si può intendere dal nome, ML-KEM ricade nella categoria di algoritmi crittografici chiamata “meccanismo di incapsulamento di chiave”. Insomma, questo standard permette di ricoprire il ruolo di un attuale algoritmo di scambio di chiave tra due entità.
Come funziona un meccanismo di incapsulamento di chiave
Intuiamo ad alto livello come funziona un meccanismo di incapsulamento di chiave. Prendendo spunto dall’esempio riportato in precedenza, immaginiamo che un certo sistema di messaggistica voglia far ottenere solo a un’infermiera e a noi una chiave per un algoritmo di crittografia simmetrica. Definiamo più precisamente questa chiave chiamandola chiave simmetrica. Il meccanismo funziona come segue. Inizialmente, il sistema applica un algoritmo di generazione per far ottenere due informazioni al dispositivo dell’infermiera. In gergo, una di queste informazioni è chiamata chiave privata, mentre l’altra è chiamata chiave pubblica. Come si può intuire dal nome, la chiave privata deve essere conservata in maniera sicura sul dispositivo dell’infermiera, mentre quella pubblica non ha bisogno di questa precauzione.
Anzi, la chiave pubblica deve essere inviata a noi, e può essere letta da una terza entità senza che la sicurezza dell’algoritmo sia compromessa. Una volta che il nostro dispositivo riceve la chiave pubblica, il sistema di messaggistica esegue in locale un cosiddetto algoritmo di incapsulamento. Questo algoritmo produce due risultati. Il primo è la chiave simmetrica, che il nostro dispositivo deve conservare in maniera sicura e protetta. Il secondo risultato è un dato digitale che chiameremo “informazione crittata”.
L’informazione crittata deve essere inviata all’infermiera, e, come la chiave pubblica, degli attaccanti esterni possono leggere questo dato senza compromettere la sicurezza dell’algoritmo. Una volta che l’informazione crittata giunge nel dispositivo dell’infermiera, il sistema di messaggistica applica il cosiddetto algoritmo di decapsulazione. Utilizzando la chiave privata dell’infermiera e l’informazione crittata, questo algoritmo è in grado di produrre come risultato nel dispositivo dell’infermiera la chiave simmetrica che anche noi possediamo.
Si sottolinea l’importanza del fatto che un’attaccante che è solo a conoscenza della chiave pubblica dell’infermiera e della informazione crittata generata da noi non è in grado di ricostruire in tempo utile la chiave simmetrica, a prescindere se questo attaccante utilizza attacchi eseguibili su computer tradizionali o quantistici. L’accesso alla chiave privata dell’infermiera o l’accesso a una delle due copie della chiave simmetrica è necessario per montare ulteriori attacchi.
Questa garanzia di sicurezza deriva dal fatto che, ad oggi, non esistono attacchi efficaci contro ML-KEM. Infatti, come sottolineato nel nome, questo algoritmo si basa su un problema matematico detto “learning with errors” che si svolge su strutture chiamate reticoli modulari (“modular lattices”). Detto in parole poverissime e sfruttando l’esempio di prima, la chiave privata dell’infermiera permette solo al dispositivo dell’infermiera di trovare una soluzione di un complicato problema matematico definito dall’informazione crittata. Un’entità senza chiave privata fallisce nel trovare una soluzione sia perché la cerca su “reticoli modulari” (che sono luoghi difficili in cui calcolare), sia perché non ha accesso diretto al problema matematico dell’infermiera, ma ha accesso solo a un problema in cui sono stati aggiunti numerosi “errori”. Dunque, anche se alcuni attaccanti risolvono con un computer quantistico il problema a cui hanno accesso (e questa operazione è già lenta per colpa dei reticoli), essi non arrivano comunque alla soluzione senza errori che l’infermiera calcola banalmente.
ML-KEM permette quindi di avere un analogo di un algoritmo di scambio di chiavi anche nel contesto di computer quantistici. Gli altri due standard dell’Agosto 2024, invece, definiscono algoritmi di firme digitali resistenti in questo stesso contesto.
ML-DSA e SLH-DSA: firme digitali resistenti a computer quantistici
FIPS 204 e FIPS 205 specificano, rispettivamente, gli algoritmi ML-DSA (Module-Lattice-Based Digital Signature Algorithm) e SLH-DSA (Stateless Hash-Based Digital Signature Algorithm). ML-DSA deriva dall’algoritmo vincitore CRYSTALS-DILITHIUM. Non è una sorpresa che l’acronimo ML e la famiglia di algoritmi CRYSTALS da cui derivano ML-DSA ed ML-KEM coincidano. Infatti, anche ML-DSA basa la sua sicurezza nella difficoltà di trovare una soluzione ad un problema matematico contenente errori e costruito su reticoli modulari. Tra l’altro, l’algoritmo di firma digitale FALCON (il quarto algoritmo vincitore il cui standard è in lavorazione) utilizza un problema matematico che, sebbene diverso da quello di “learning with errors”, si svolge comunque su reticoli.
Più peculiare risulta invece SLH-DSA, che deriva dall’algoritmo vincitore SPHINCS+. Come ha sottolineato il NIST stesso con l’annuncio degli algoritmi vincitori, SLH-DSA è più lento e più costoso in termini di spazio da implementare rispetto a FALCON e a ML-DSA, ma è importante da tenere come riserva perché si basa su approccio matematico distinto da quello dei reticoli. Infatti, come suggerisce il nome, SLH-DSA sfrutta ampiamente specifiche funzioni crittografiche dette hash.
Funzioni hash e SLH-DSA
Dato un messaggio di lunghezza qualsiasi in entrata, una funzione di hash produce in uscita un risultato (detto digest) di una certa lunghezza stabilita. Tale lunghezza può essere sempre uguale (come nel caso delle varianti di SHA3) oppure può essere impostata a un valore idoneo (queste funzioni di hash prendono il nome di eXtendable Output Function, in acronimo XOF). Si richiedono queste tre proprietà per avere una funzione crittografica di hash: dato un certo digest, deve essere arduo risalire a un messaggio in entrata che possa generare tale digest (la cosiddetta resistenza alla preimmagine); dato un certo messaggio in entrata, deve essere arduo trovare un secondo messaggio distinto dal primo tale che i loro digest coincidano (la cosiddetta resistenza alla preimmagine secondaria); dati due messaggi distinti, deve essere difficile che i loro digest coincidano (la cosiddetta resistenza alle collisioni). Per ottenere l’ultima proprietà di resistenza alle collisioni, tipicamente il digest dipende strettamente dal messaggio in entrata e cambia in modo imprevedibile anche se si cambia una virgola nel messaggio in entrata.
Grazie alle proprietà elencate sopra, le funzioni crittografiche di hash sono usate in maniera efficace e sicura in alcuni algoritmi di firme digitali e, in generale, in ogni algoritmo che richiede autenticazione (ovvero, in ogni algoritmo che richiede di confermare la verità di un’informazione sostenuta vera da qualche entità). Inoltre, le proprietà dette sopra e un uso ripetuto e consecutivo di hash permettono di costruire SLH-DSA in maniera da resistere ad attacchi quantistici, visto che un digest visto da un attaccante può sembrare sostanzialmente come “generato casualmente” a partire dal messaggio originale.
Prospettive della crittografia post-quantistica
L’avvento della crittografia post quantistica e algoritmi come quello di Shor minacciano la sicurezza degli attuali algoritmi di firme digitali e di scambio di chiave. Attualmente, i computer quantistici esistenti non hanno ancora potenza computazionale sufficiente per essere considerati pericolosi, e sono particolarmente costosi da produrre. Ma i computer quantistici sono in costante evoluzione, e nell’ultima manciata di anni abbiamo assistito a un costante progresso verso la costruzione di computer quantistici per i consumatori. Se un computer quantistico di larga scala verrà effettivamente venduto, non avremo più garanzie di sicurezza per gli algoritmi di crittografia asimmetrica comunemente utilizzati. Ricordando che un aggiornamento su vasta scala degli algoritmi crittografici richiede sempre molto tempo, bisogna prepararsi adeguatamente all’arrivo di questa nuova tipologia di computer iniziando a modificare i sistemi esistenti già da ora.
Con gli standard FIPS 203, 204 e 205, il NIST offre le prime soluzioni standardizzate, alternative a quelle odierne e resistenti agli attacchi quantistici trovati finora. Questo segna sicuramente un passo nella direzione giusta per essere adeguatamente preparati all’era tecnologica quantistica. Questi standard porteranno molte compagnie ad iniziare la transizione agli algoritmi post quantistici. Ad esempio, Google sta già iniziando ad implementare e testare in pratica il meccanismo di incapsulamento di chiave ML-KEM nel suo famoso browser Chrome.
Certo, stiamo osservando ancora gli albori di una totale transizione ad algoritmi crittografici resistenti ad attacchi eseguibili su computer quantistici. A dir la verità, il NIST tiene ancora aperta una competizione riguardo ad algoritmi post quantistici. Infatti, gli algoritmi selezionati finora, per quanti sicuri e scrutinati a fondo dalla comunità crittografica, hanno alcuni difetti. Sono lenti, l’algoritmo di decapsulazione può fallire, si basano quasi tutti su un unico problema (quello dei reticoli modulari) relativamente complicato da studiare ed analizzare, e sono meno efficienti rispetto agli algoritmi moderni anche dal punto di vista di spazio di archiviazione utilizzato (la dimensioni delle chiavi private e delle firme coincide quasi con quella di un breve messaggio vocale). Per questo motivo, il NIST e la comunità scientifica non sono ancora completamente soddisfatti, e stanno ancora scrutinando sia un quarto round di meccanismi di incapsulamento di chiave che non si basano su reticoli modulari, sia un nuovo insieme di algoritmi di firma digitale.
