La crittografia ha un ruolo fondamentale nella protezione della nostra vita digitale, dai dati privati alle infrastrutture pubbliche. Vediamo allora come la comunità internazionale si sta preparando ad un aggiornamento di massa degli strumenti crittografici attualmente in uso, necessario per difendersi dalla nuova minaccia rappresentata dal quantum computer.
Crittografia e cybersecurity
La crittografia è una disciplina molto antica, che affonda le sue radici nelle pratiche militari usate già all’epoca di Cesare per nascondere i messaggi di guerra alle truppe nemiche, ma che nel tempo ha conosciuto un’evoluzione continua ed una diffusione progressiva.
Questo perché, con l’introduzione delle reti e di Internet, le tecniche ed i protocolli crittografici sono gli unici strumenti a nostra disposizione per garantire la sicurezza dei nostri dati e delle nostre identità digitali online, e nelle infrastrutture digitali in generale.
Per questo, oggi la crittografia riveste un ruolo fondamentale e strategico, sia nella vita privata dei cittadini che nel tessuto economico-produttivo di una nazione, fornendo alcuni strumenti fondamentali per la cybersecurity. Basti pensare che tecnologie come TLS, IPsec e VPN, oltre a molte altre, si fondano sull’uso massiccio della crittografia. Pertanto, pur se spesso inconsapevolmente, tutti noi usiamo quotidianamente moltissimi strumenti crittografici. Ciò avviene ovviamente quando consultiamo il nostro conto corrente online, ma anche quando usiamo la posta elettronica, navighiamo sulla maggior parte dei siti web ed usiamo gran parte delle app del nostro smartphone, fino al bancomat ed alla chiave della nostra auto. Il nostro mondo digitale oggi è quindi permeato di strumenti crittografici.
Dietro a così tanti strumenti e protocolli crittografici si nascondono le cosiddette (e tutto sommato poche) primitive crittografiche, ovvero le funzioni matematiche di base che, partendo da un dato digitale, consentono di ottenerne versioni confidenziali e autenticate, che lo proteggono da tentativi di furto e manipolazione.
Quantum computing: come si costruisce un computer quantistico
Le primitive crittografiche ad oggi consolidate e diffuse sono relativamente poche, e su di esse si regge l’intero impianto della sicurezza di Internet, comprese le moderne tecniche di cybersecurity e cyber defense. Tali primitive possono essere raggruppate in tre principali famiglie:
- Primitive crittografiche simmetriche, basate sull’uso di un una chiave segreta pre-condivisa tra gli utenti, che sono usate per cifrare contenuti digitali confidenziali trasferiti via rete o memorizzati in archivi digitali. Tra queste la più nota si chiama AES.
- Primitive crittografiche asimmetriche, basate sull’uso di una chiave privata per ciascun utente e della corrispondente chiave pubblica, che sono usate per consentire lo scambio di un segreto condiviso tra nuovi interlocutori e per la firma digitale. Tra queste sono molto note RSA, ElGamal e sistemi basati su curve ellittiche (come ECDSA).
- Funzioni hash, capaci di derivare una sorta di impronta digitale di piccole dimensioni a partire da qualsiasi dato, che sono usate per garantire l’integrità e l’autenticazione dei dati. Tra queste sono note le funzioni della famiglia SHA, da SHA1 a SHA3.
Crittografia e crittanalisi
Come abbiamo visto, la crittografia è la disciplina che studia e realizza le primitive crittografiche, cioè le funzioni e gli algoritmi capaci di proteggere i nostri dati. Accanto alla crittografia esiste una disciplina complementare, ed altrettanto importante, chiamata crittanalisi. Quest’ultima è infatti la disciplina che studia come attaccare le primitive crittografiche, cercando di sovvertirle evidenziandone eventuali debolezze.
Queste due discipline sono simbiotiche, e non possono esistere l’una senza l’altra: il progresso della crittografia è infatti sospinto dagli avanzamenti della crittanalisi, che hanno determinato l’obsolescenza di molte delle primitive crittografiche storiche, di conseguenza motivando la progettazione di primitive crittografiche nuove e più resistenti. D’altro canto, ovviamente, la crittanalisi non può esistere senza la crittografia, che definisce continuamente nuove primitive crittografiche da sottoporre a scrutinio.
Un esempio celebre di rapporto tra la crittografia e la crittanalisi, che ha influenzato le sorti della Seconda guerra mondiale ed ispirato numerosi film e romanzi, è quello relativo alla macchina cifrante Enigma usata dall’esercito tedesco ed alla sua crittanalisi eseguita dal gruppo di scienziati inglesi riuniti a Bletchey Park sotto la guida di Alan Turing.
L’importanza della crittanalisi per l’evoluzione della crittografia motiva anche la necessità di disporre di algoritmi crittografici aperti, in cui tutte le fasi dell’algoritmo crittografico siano pubblicamente documentate, al fine di poterli sottoporre ad uno scrutinio crittanalitico più approfondito possibile.
Ciò è evidente ai crittografi sin dai primordi della crittografia, tanto che già nel 1883 il crittografo olandese Auguste Kerckhoffs enunciò il principio che prende il suo nome, secondo il quale un crittosistema deve essere sicuro anche se tutto ciò che riguarda il sistema è di dominio pubblico, fatta ovvia eccezione per la chiave segreta. Questo principio riveste tutt’oggi un’importanza fondamentale, e guida l’operato di crittografi e crittanalisti in contrapposizione all’approccio basato sulla cosiddetta “security by obscurity”, legata alla falsa convinzione di aumentare la sicurezza di un sistema crittografico tenendone segreti i dettagli algoritmici.
Proprio seguendo il principio di Kerckhoffs, la comunità crittografica internazionale condivide pubblicamente i propri progressi, e dà vita a delle pubbliche iniziative per il progetto di nuovi sistemi crittografici ed il miglioramento di quelli esistenti, nelle quali crittografi e crittanalisti si confrontano in modo collaborativo e costruttivo, con l’obiettivo comune del progresso della conoscenza crittografica.
L’impatto del quantum computer
La crittanalisi classica sfrutta algoritmi che possono essere eseguiti sui computer che tutti conosciamo, basati su microprocessori elettronici. Questi elaboratori classici rappresentano i dati sottoforma di bit, ed eseguono calcoli in modo sequenziale.
Immaginiamo di dover calcolare i valori assunti da una funzione f(x) in corrispondenza dei valori di ingresso x = 0 (o 00 in notazione binaria), x = 1 (o 01 in notazione binaria), x = 2 (o 10 in notazione binaria) e x = 3 (o 11 in notazione binaria). Con un computer classico sarà necessario eseguire il calcolo quattro volte, considerando uno alla volta i quattro diversi valori di input.
All’inizio degli anni 80 i fisici Richard Feynman e Yuri Manin teorizzarono la possibilità di costruire un quantum computer, cioè un computer capace di usare gli stati quantistici della materia per rappresentare i dati sottoforma di bit quantistici, o qubit. La principale innovazione che ne deriva è la possibilità di sfruttare il fenomeno di sovrapposizione quantistica per consentire la convivenza di stati diversi all’interno dello stesso qubit. Tornando all’esempio precedente, due qubit possono assumere contemporaneamente tutti i valori possibili, rappresentati con la notazione |00⟩+ |01⟩+ |10⟩+ |11⟩ ed il quantum computer può eseguire in un’unica volta in calcolo di tutti i valori sovrapposti della funzione f, ovvero |f(00)⟩+|f(01)⟩+|f(10)⟩+|f(11)⟩. Questo stato di sovrapposizione dei valori dei qubit può protrarsi nell’esecuzione delle istruzioni di un algoritmo, per poi “ricadere” su uno degli stati classici solo al termine del calcolo, fornendo la soluzione cercata.
Sebbene ciò non sia applicabile a qualsiasi tipo di funzione, quanto sopra spiega come il quantum computer sia capace di accelerare in modo sostanziale l’esecuzione di alcuni calcoli. Tra questi, la ricerca dei fattori primi di un numero intero è un problema notoriamente accelerabile con il quantum computer, usando l’algoritmo introdotto nel 1994 dal matematico americano Peter Shor. Purtroppo, però, proprio sulla difficoltà di fattorizzare grandi numeri interi, e sulla legata difficoltà di calcolare grandi logaritmi discreti, si basa la sicurezza di molti sistemi crittografici asimmetrici oggi molto diffusi, quali RSA, ElGamal ed i crittosistemi basati su curve ellittiche (come ECDSA). Per questo, essi vengono definiti quantum-vulnerable, in quanto l’esistenza del quantum computer mette evidentemente a repentaglio la loro sicurezza.
Se il quantum computer era solo un concetto teorico negli anni 80 e 90, oggi è diventato realtà. Già nel 2017 IBM stava lavorando a “Q System One”, il primo quantum computer per scopi commerciali capace di eseguire operazioni su 20 qubit. Tuttavia, almeno 50 qubit sono considerati necessari per raggiungere la cosiddetta supremazia quantistica, ovvero la capacità di un quantum computer di superare un computer classico. Nello stesso anno, Google stava lavorando ad un quantum computer con 72 qubit, che però si rivelò troppo difficile da controllare. Ad ottobre 2019 Google annunciò che il suo sistema Sycamore con 53 qubit era capace di eseguire in 200 secondi un calcolo che richiederebbe 10’000 anni se eseguito sul più potente computer classico del mondo. Ad ottobre 2020, la startup IonQ ha annunciato il lancio di un quantum computer a 32 qubit con bassi tassi d’errore, necessari affinché la tecnologia sia scalabile.
Nel frattempo, in Cina è stato sviluppato Jiuzhang, il primo quantum computer fotonico a rivendicare la supremazia quantistica. Infatti, Jiuzhang si basa su fotoni anziché su materiali superconduttori come i quantum computer di IBM e Google. Jiuzhang è stato sviluppato da un team dell’Università di Scienza e Tecnologia della Cina (USTC) guidato da Pan Jianwei e Lu Chaoyang, e nel dicembre del 2020 è stato annunciato che era capace di eseguire alcuni compiti in modo drasticamente più veloce del migliore supercomputer classico esistente.
Gli anni più recenti sono stati caratterizzati dal proliferare di startup focalizzate sullo sviluppo di soluzioni tecnologiche per rendere maggiormente scalabile la tecnologia alla base del quantum computer, in modo di poter consentire una crescita progressiva nel tempo del numero di qubit.
A seguito di tale evoluzione del quantum computer, è evidente che tutta la crittografia quantum-vulnerable necessita di essere sostituita al più presto. Con essa molte primitive crittografiche, come RSA e ECDSA, che oggi sorreggono gran parte delle nostre infrastrutture digitali, da Internet alle reti bancarie, fino alle blockchain. Ciò giustifica la crescente attività di ricerca nell’ambito della crittografia post-quantum, ovvero sulla definizione e implementazione di primitive crittografiche che rimangano sicure anche in presenza di attaccanti provvisti di un quantum computer sufficientemente grande.
NIST ed altri enti di standardizzazione
Stante l’emergenza rappresentata dall’avvento del quantum computer e la necessità di sottoporre ogni nuovo sistema crittografico ad un’attenta fase crittanalitica, la comunità internazionale si è mobilitata verso la definizione di nuovi standard comuni per la crittografia post-quantum. Fortunatamente, la comunità scientifica stava già lavorando da anni alla ricerca di primitive crittografiche post-quantum, perciò lo sforzo di standardizzazione ha potuto avvalersi di una comunità esistente, presso università e centri di ricerca di tutto il mondo, ed in parte già pronta a fronteggiare questa nuova sfida.
Già il 20 dicembre 2016 l’ente statunitense NIST (National Institute for Standards and Technology) pubblicò un bando per la selezione di primitive crittografiche post-quantum necessarie ad aggiornare i propri standard crittografici FIPS 186 4, SP 800 56 A Rev 2 e SP 800 56 B. La scadenza per l’invio di candidati da sottoporre allo scrutinio del NIST era fissata per il 30 novembre 2017. Furono 82 le proposte ricevute da gruppi di crittografi di tutto il mondo, raccogliendo 263 ricercatori provenienti da 24 Paesi diversi. Di tali proposte iniziali, solo 69 furono considerate ammissibili alla procedura di selezione. Esse furono analizzate per oltre un anno dal NIST e dalla comunità internazionale, finché il 30 gennaio 2019 furono annunciati i 26 candidati ammessi al secondo round di selezione. A distanza di oltre un altro anno, il 22 luglio 2020, furono annunciati gli ammessi al terzo round di selezione, composti da 7 finalisti e 8 candidati alternativi.
Il 5 luglio 2022 la chiusura del terzo round ha prodotto il primo esito della procedura di selezione del NIST, definendo i candidati che verranno inclusi nel prossimo standard NIST per la crittografia post-quantum, il cui rilascio è previsto per il 2024 dopo una fase di consultazione pubblica. Le due primitive selezionate per essere raccomandate da parte del NIST per la maggior parte delle applicazioni sono CRYSTALS-Kyber per lo scambio di chiavi segrete su canale pubblico e CRYSTALS-Dilithium per le firme digitali. Entrambe queste primitive crittografiche si basano su problemi matematici legati all’algebra dei reticoli. Esse sono state selezionate come soluzioni primarie sulla base del loro elevato livello di sicurezza e delle loro eccellenti prestazioni.
Oltre a queste due primitive principali, il NIST ha selezionato altri due sistemi di firma digitale: Falcon e SPHINCS+. Il primo è pure basato sull’algebra dei reticoli, ed è stato selezionato perché è capace di fornire firme digitali di dimensioni più contenute rispetto a CRYSTALS-Dilithium; pertanto, è consigliato in quelle applicazioni in cui la dimensione della firma digitale è un parametro da contenere. Infine, il NIST ha selezionato il sistema di firma digitale SPHINCS+, basato sulle funzioni hash, per offrire un’alternativa che non si basasse sull’algebra dei reticoli.
Ai quattro algoritmi selezionati, il NIST ne ha affiancati altri quattro che sono stati ammessi ad un quarto round di selezione, alla fine del quale potranno eventualmente essere anch’essi standardizzati. I primi due di tali algoritmi sono BIKE e HQC, si tratta di schemi per lo scambio di chiavi segrete su canale pubblico basati su problemi matematici derivanti dalla teoria dei codici. Essi sono stati considerati interessanti perché offrono buone prestazioni e basano la loro sicurezza sulla difficoltà di risolvere un problema matematico diverso da quelli legati all’algebra dei reticoli. Oltre a questi, è stato ammesso al quarto round il candidato SIKE, che è uno schema per lo scambio di chiavi segrete su canale pubblico basato sulla matematica delle isogenie tra curve ellittiche. Esso è stato selezionato sia perché si basa su un problema matematico diverso dai precedenti sia perché offre dimensioni molto contenute per le chiavi pubbliche ed il testo cifrato. Ultimo candidato ammesso al quarto round è Classic McEliece, che pure si basa su problemi derivanti dalla teoria dei codici. A differenza di BIKE e HQC, però, Classic McEliece usa la formulazione più classica e meglio studiata del problema basato sulla teoria dei codici, e pertanto è considerato fortemente sicuro.
Tuttavia, esso richiede l’uso di chiavi pubbliche di dimensioni significativamente più grandi degli altri candidati, motivo per cui il NIST non lo ha considerato utilizzabile su larga scala.
Per gli algoritmi ammessi al quarto round di selezione, i gruppi proponenti hanno la possibilità di inviare dei miglioramenti, che non costituiscano modifiche sostanziali, entro il 1° ottobre 2022. Dopodiché, il quarto round procederà similmente ai precedenti.
Dal momento che il processo di selezione del NIST non ha ottenuto una sufficiente diversità per quanto riguarda gli schemi di firma digitale, il 6 Settembre 2022 il NIST ha pubblicato un nuovo bando per selezionare altri algoritmi di firma digitale post-quantum. Lo scopo di tale nuovo bando è quello di diversificare il portafoglio di firme digitali, cercando nuovi schemi che non siano basati sull’algebra dei reticoli. Si cercheranno in particolare schemi di firma digitale caratterizzati da firme corte e verifiche rapide. Le proposte in risposta a questo nuovo bando dovranno essere presentate entro il 1° giugno 2023. Il NIST deciderà quali candidati eventualmente accettare tra gli algoritmi di firma presentati e avvierà un nuovo processo di selezione. Il NIST prevede che tale processo sia di portata molto più limitata rispetto a quello iniziato nel 2017, benché si preveda che anch’esso durerà diversi anni.
L’avvento delle nuove primitive selezionate dal NIST ovviamente rivoluzionerà il panorama della crittografia asimmetrica e della firma digitale. Invece, per quanto riguarda la crittografia simmetrica, secondo il NIST le applicazioni attuali possono continuare a utilizzare AES con chiavi di 128, 192 o 256 bit. Anche le attuali funzioni hash possono continuare ad essere usate dopo l’avvento del quantum computer, sebbene con qualche accorgimento. Il NIST pubblicherà delle linee guida relative a eventuali transizioni di algoritmi a chiave simmetrica e funzioni hash per la protezione dalla minaccia quantum quando sarà possibile prevedere una necessità di transizione. Fino ad allora, si raccomanda di non utilizzare algoritmi con meno di 112 bit di sicurezza classica.
Sebbene il NIST sia stato il primo e più importante ente di standardizzazione di tecniche crittografiche ad avviare una procedura di selezione di primitive post-quantum, la necessità di definire strumenti crittografici atti a resistere alla minaccia del quantum computer è percepita anche oltre i confini statunitensi. Lo dimostra la recente dichiarazione del G7, che include le principali nazioni europee. In Europa, inoltre, l’ETSI ha già instaurato da tempo un gruppo di lavoro sulla crittografia post-quantum.
Parallelamente, l’associazione cinese per la ricerca in crittografia ha condotto una sua procedura di standardizzazione di primitive crittografiche post-quantum. Tale processo è avvenuto tra il 2018 e il 2019, ma era aperto solo a proponenti cinesi, che hanno presentato un totale di 36 candidati, analizzati nel corso di un anno. Tre algoritmi si sono aggiudicati il primo posto, quattro il secondo e sei il terzo. Purtroppo, i materiali del concorso sono disponibili solo in lingua cinese, rendendo difficile l’accesso alla comunità internazionale.
L’evoluzione della crittografia è terminata?
Sebbene la procedura di selezione e standardizzazione condotta dal NIST, così come quelle di altri enti di standardizzazione, stiano svolgendo un importante lavoro di sintesi ed incentivando la crittanalisi dei sistemi crittografici post-quantum, esse non possono, e nemmeno intendono, mettere la parola fine all’evoluzione della crittografia e della crittanalisi. Sarebbe infatti illusorio sperare di definire un set di primitive crittografiche che possano andare bene per sempre d’ora in avanti.
Lo dimostrano peraltro gli esiti stessi di queste procedure. Significativo è il caso di SIKE, uno dei candidati selezionati dal NIST lo scorso luglio per essere ammessi al quarto round di selezione. Ebbene, dopo oltre quattro anni di crittanalisi, e solo pochi giorni dopo la sua ammissione al quarto round, un gruppo di ricercatori belgi ha pubblicato un articolo che descrive un nuovo attacco contro tale sistema. L’implementazione di tale attacco è capace di compromettere la prima istanza di SIKE proposta per la standardizzazione del NIST con soltanto un’ora di esecuzione su un computer dotato di un singolo core. Pochi giorni dopo, un ricercatore francese ha confermato l’attacco, mostrando che alcune possibili contromisure in realtà non funzionano.
Qualcosa di analogo era già accaduto al candidato Rainbow, che implementava uno schema di firma digitale basato su sistemi di equazioni multivariate, e che a luglio 2020 era stato ammesso al terzo round di selezione del NIST come uno dei tre schemi finalisti per la firma digitale. Nonostante ciò, a febbraio 2022 un ricercatore della IBM di Zurigo è riuscito a trovare un attacco capace di recuperare la chiave segreta della prima istanza di Rainbow impiegando in media solo 53 ore su un normale computer portatile.
D’altro canto, alcuni dei candidati esclusi dalla procedura di selezione del NIST non appaiono attualmente affetti da vulnerabilità. Questo, ad esempio, è il caso di LEDAcrypt, una suite di algoritmi crittografici post-quantum interamente progettati ed implementati da ricercatori italiani. LEDAcrypt è stato ammesso ai primi due round di selezione del NIST, ma non è stato ammesso al terzo round perché le modifiche resesi necessarie per evitare la presenza di alcune chiavi deboli emerse dal lavoro di crittanalisi sono state considerate dal NIST superiori alle variazioni ammissibili per la permanenza nella competizione.
Tutto questo ci insegna che non si può prevedere l’evoluzione della ricerca nella crittografia, così come nella crittanalisi. Certamente iniziative nazionali ed internazionali di selezione e standardizzazione come quella del NIST hanno il merito di focalizzare l’attenzione della comunità scientifica ed accelerare notevolmente il lavoro di crittanalisi, che altrimenti procederebbe soltanto in modo spontaneo. Pertanto, gli algoritmi crittografici che partecipano a tali iniziative sono sicuramente analizzati in modo più accurato degli altri, nel pieno rispetto del principio di Kerckhoffs. D’altro canto, non è possibile imbrigliare una materia così complessa ed in continua evoluzione all’interno di uno schema prestabilito, e soltanto il progredire della conoscenza e della ricerca può permetterci di continuare a fronteggiare le sfide future per la sicurezza dei nostri dati, a partire da quella rappresentata dal quantum computer.
