Il National Institute of Standards and Technology (NIST) del Dipartimento del Commercio degli Stati Uniti a luglio ha scelto il primo gruppo di strumenti di crittografia progettati per resistere all’assalto di un futuro computer quantistico.
Questo risultato arriva dopo un lungo lavoro di selezione che ha motivazioni profonde, derivanti dalle capacità attese dei computer quantistici. Ma per costruire lo standard crittografico della internet del futuro c’è ancora molto da fare.
Perché bisogna ripensare la crittografia nel mondo post-quantum
Per capire la portata del lavoro del NIST occorre fare un breve ripasso di quale sia l’impatto dei computer quantistici sui sistemi crittografici.
Quantum computing: come si costruisce un computer quantistico
La crittografia a chiave pubblica è da svariati anni un elemento vitale per la sicurezza online e viene usata in moltissimi sistemi di uso quotidiano, da quelli bancari alle applicazioni mobili che usiamo tutti i giorni. Quando due o più parti vogliono comunicare, allo stato attuale della tecnologia, la crittografia a chiave pubblica assicura che le informazioni siano riservate e accurate e che le parti corrette stiano comunicando. La sicurezza dei sistemi crittografici si è via via adattata (es. con chiavi sempre più lunghe) alla crescita delle capacità computazionali dei computer classici. Capacità che è cresciuta in modo quasi lineare (i.e., legge di Moore), grazie al crescente numero di transistors per unità di volume su silicio e grazie alla collaborazione di differenti unità computazionali in rete (es. facenti parte di una unica BOTNET di computer distribuiti). L’avvento dei computer quantici scardina la legge di Moore (Figura 1) che metteva in correlazione quasi lineare la crescita anno dopo anno con il numero di transistor nelle CPU e quindi con la potenza di calcolo, scoperchiando la principale ipotesi alla base dei sistemi crittografici moderni: il fatto che il tempo di calcolo necessario per compiere i calcoli necessari a riportare in chiaro i dati sia nettamente superiore alla durata del dato stesso.
Figura 1 – La legge di Moore indica una crescita quasi lineare del numero di transistor (e quindi operazioni/sec) anno dopo anno.
Come riportato in Figura 2, il quantum computing cambia la semi linearità espressa della legge di Moore e dal mondo computazionale “classico”, rendendo esponenziale la capacità di calcolo (v. legge di Rose).
Figura 2 – legge di Moore vs legge di Rose (fonte N.Yoder)
Alla base di ogni schema a chiave pubblica si trova un problema matematico “complesso”, cioè di complessa (ma non impossibile) risoluzione o, con una elevata “complessità numerica”. Se una persona o un computer può risolvere efficacemente questo problema, può bypassare il sistema crittografico. Non tutti i problemi matematici complessi sono adatti all’uso nella crittografia; la caratteristica chiave è che il problema deve essere difficile da risolvere in una direzione, ma facile nella direzione opposta (i.e., funzione difficile da invertire).
La crittografia a chiave pubblica attualmente in uso si basa su problemi che coinvolgono la fattorizzazione in numeri primi (RSA), i logaritmi discreti (Diffie-Hellman) e le curve ellittiche (ECC). Anche se questi sembrano problemi diversi, in realtà sono tutti casi di un problema generale chiamato problema del sottogruppo nascosto abeliano [1] [2], legato alla difficoltà di fattorizzazione in numeri primi. Questo problema è complesso da risolvere, specialmente con algoritmi classici che hanno una complessità cosiddetta (sub)esponenziale. Ci vorrebbero anni per rompere l’attuale crittografia a chiave pubblica anche con il più potente dei computer, supponendo che il sistema sia implementato correttamente.
Come si attaccano i sistemi di cifratura
Dando per scontato che un sistema crittografico sia basato su una struttura teorica matematica corretta, ed escludendo quindi gli attacchi teorico-matematici, uno dei principali metodi di attacco ad un sistema crittografico è quello di usare la forza bruta per decifrare un messaggio, provando tutte le chiavi possibili. Altre forme di attacco (es. side channel, replay e rainbow table, etc) sono da considerare attacchi più rivolti al processo di uso dei sistemi crittografici oppure ai sistemi di hashing (es birthday attack). Con le capacità di calcolo attuali e la crescita semi lineare indicata dalla legge di Moore, gli attacchi a forza bruta tipicamente occupano molto tempo: essendo direttamente dipendenti dalla lunghezza delle chiavi crittografiche usate basta scegliere chiavi sufficientemente lunghe. In questo caso l’unica misura di difesa è quindi il tempo necessario o la potenza di calcolo.
La minaccia quantum ai sistemi di cifratura odierni
I ricercatori sanno da decenni che nel momento in cui sarà possibile costruire un computer quantistico su larga scala, potrebbe svolgere calcoli ad un ritmo tale (legge di Rose) da minacciare i sistemi di crittografia su cui oggi contiamo per la sicurezza. La attuale crittografia a chiave pubblica è bastata per decenni, ma il recente sviluppo dei computer quantistici rappresenta una minaccia concreta. Per completezza rimando al mio articolo su cybersecurity360, ma si può riassumere la situazione attuale dicendo che tutti gli algoritmi di cifratura attualmente in uso (es. RSA, ECC, AES) risultano violabili in un tempo praticamente indipendente dalla lunghezza delle chiavi. Sebbene quindi non esista ancora un computer quantistico adatto, ci sono molte ragioni per cui si debba discutere come far evolvere la crittografia.
- È difficile stimare quando il calcolo quantistico raggiungerà una applicabilità tale da corrompere gli attuali sistemi crittografici. Si tratta di una nuova forma di scienza e tecnologia, con aziende, governi e università che tentano approcci diversi, e le stime vanno da dieci a trent’anni. A meno di scoperte ed accelerazioni ovviamente. Occorre studiare, implementare e testare la nuova crittografia quantistica prima che qualcuno sviluppi un computer quantistico utilizzabile.
- La transizione dei sistemi di crittografia può richiedere molti anni. Questo aspetto è spesso trascurato, ma la transizione di qualsiasi tecnologia, soprattutto in una grande organizzazione, è un processo difficile e può richiedere tempi nell’ordine di grandezza del decennio. Anche un semplice aggiornamento di un algoritmo o di una chiave può richiedere molto tempo. Può richiedere nuove infrastrutture, formazione per gli sviluppatori, riprogettazione di vecchie applicazioni e nuovi standard crittografici, distribuzione della nuova soluzione nella rete. Questo vale per l’intera struttura su cui è basata larga parte della rete Internet oggigiorno.
- Oltre al dato cifrato in transito occorre rendere sicura la memorizzazione dei dati. Le compagnie stanno già memorizzando dati crittografati in ottemperanza anche alle norme legislative (es., GDPR). Seppure oggigiorno il mondo quantum rappresenti un rischio relativamente remoto, e alcuni dati possano non essere così rilevanti tra dieci o trent’anni, la maggior parte dei dati saranno ancora sensibili. Dati come le informazioni personali o sanitarie (personal identifiable information / personal healthcare information PII/PHI) o le informazioni governative, necessitano di crittografia a lungo termine.
- Gli algoritmi di sicurezza quantistica sono più sicuri sia contro gli attacchi quantistici che contro quelli classici e, in alcuni casi, sono anche più efficienti e flessibili.
Il lavoro svolto dal NIST per una nuova crittografia
Il NIST, proprio in relazione a questi criteri guida ha avviato un lavoro di selezione di nuovi standard di cifratura post-quantistici, cioè che possono essere svolti su computer non quantistici ma che siano matematicamente resistenti alle implicazioni della legge di Rose detta sopra. Il risultato di una prima selezione internazionale di quattro algoritmi (al primo round ne erano stati presentati 82, diventati 26 al secondo e infine 4 al quarto) è stata pubblicata proprio qualche giorno fa.
Algoritmi crittografici, dal NIST i primi quattro resistenti ai computer quantistici: i dettagli
La selezione ha richiesto lunghe verifiche di robustezza post-quantum, ad esempio Rainbow, uno dei principali finalisti del terzo round, è stato tolto all’ultimo minuto, poteva essere violato in 53 ore su un normale laptop!. Gli algoritmi proposti sono destinati a rivoluzionare sul lungo termine la sicurezza informatica, ma il lavoro è ancora lungo: per ogni algoritmo occorre fare una verifica formale (qualora possibile) della robustezza crittografica, in particolare rispetto ai computer quantici. In crittografia esiste il concetto di perfect secrecy cioè la capacità di un algoritmo crittografico di resistere, indipendente dalla potenza di calcolo a disposizione dell’attaccante (si veda anche [10]). Al momento, solo l’algoritmo One-time Pad (utilizzato per la Quantum Key Distribution) giova dell’attributo, matematicamente dimostrato, di perfect secrecy. Questo comporta che gli algoritmi selezionati dal NIST saranno sicuri fino ad un certo punto lungo la curva di Rose, oltre il quale dovranno essere cambiati. In particolare, con riferimento allo scenario “hack now, decrypt later”.
In questo momento quindi la selezione del NIST si fonda su una previsione di sicurezza rispetto alle evoluzioni dei computer quantistici ed è basata su considerazioni di algoritmiche, di utilizzo, velocità, dimensione delle chiavi e performance generali. Ad esempio la accoppiata CRYSTALS-Kyber per la crittografia generale e CRYSTALS-Dilithium, FALCON e SPHINCS+ per le firme digitali, in particolare FALCON, essendo molto veloce e poco ingombrante è ideale per sistemi mobili. Un processo di firma, se la cifratura tramite chiave asimmetriche è lenta, necessità di un algoritmo di hashing ed il NIST suggerisce quali sistemi vadano utilizzati. Ad esempio, SPHINCS può essere accompagnato da SHAKE256, SHA-256 o Haraka, mentre per CRYSTALS-Kyber la parte di hashing è già parte integrante del protocollo Kyber.
Da notare che tutti gli algoritmi selezionati partono da un’unica categoria di problemi matematici, legati ai reticoli (lattice in inglese), ritenuti di difficile soluzione anche per computer quantici. Quello che differenzia le varie soluzioni sono i parametri di processo detti poco sopra e il particolare problema matematico di complessità non polimoniale sul quale si basano (es. Shortest Vector Problem, problema del vettoriale più breve oppure i due Short Basis Problem e Closest Vector Problem).
Conclusioni
I quattro algoritmi scelti dal NIST si basano su problemi matematici difficili da risolvere sia sui computer classici che su quelli quantistici, proteggendo così i dati dagli attacchi di critto analisi.
L’agenzia prevede di includere altri quattro algoritmi prima di finalizzare lo standard crittografico post-quantistico, un processo che dovrebbe essere completato in circa due anni.
La Cybersecurity and Infrastructure Security Agency (CISA) degli Stati Uniti, insieme al NIST, raccomanda “fortemente” alle organizzazioni di iniziare a prepararsi per la transizione seguendo una roadmap dedicata. Allo scopo è stato parallelamente annunciato un piano di collaborazione con vendor di soluzioni specifiche.
Ricordo inoltre che quanto annunciato dal NIST non comprende la Fully Homomorphic Encryption (FHE) anch’essa basata sui reticoli (ma sono allo studio varianti nativamente costruite sui qbit) ed anch’essa ritenuta quantum-safe, ma ancora in fase di studio (in particolare i requisiti di calcolo sono onerosi). In generale la Homomorphic Encryption (cifratura omomorfica) è una forma di cifratura che permette di svolgere calcoli direttamente nello spazio dei dati cifrati (es. operazioni artimetiche e logiche) eliminando la necessità di decifrare i dati (l’attributo Fully indica che non c’è limite al numero di operazioni che si possono compiere). Tale schema consente la costruzione di programmi general purpose, che possono essere eseguiti su input crittografati per produrre un output anch’esso crittografato. Poiché un tale programma non ha mai bisogno di decifrare i dati in ingresso per svolgere la propria funzione, può essere eseguito anche in un contesto non fidato, senza dover accedere ai dati in chiaro. I sistemi crittografici completamente omomorfi hanno implicazioni pratiche nell’outsourcing, ad esempio nel contesto del cloud computing (si veda Figura 3). Uno gruppo di lavoro del NIST segue questo tipo di evoluzioni.
Figura 3 – Rappresentazione visiva del flusso di funzionamento della FHE
In generale, come ha recentemente insegnato l’algoritmo Rainbow citato sopra, in tutti gli algoritmi possono esserci problemi che ne minano la robustezza. Questo del NIST è una prima selezione che deve essere affinata e messa alla prova: è una grossa responsabilità suggerire i nuovi standard crittografici che saranno in tutto il mondo. Il concetto che si sta facendo strada in generale è quindi quello della crypto agility, l’idea che qualunque soluzione crittografica venga utilizzata, che sia software o hardware, se gli algoritmi di crittografia coinvolti si “rompono”, possano essere facilmente sostituiti con i successivi algoritmi suggeriti.
