La crittografia post-quantistica si basa sull’idea che alcuni problemi matematici siano difficili, ovvero irrisolvibili in tempi ragionevoli, anche per i computer quantistici e possano dunque essere impiegati per proteggere i dati. Un nuovo studio pubblicato in fase preliminare da un ricercatore di Amazon Web Services getta per� le basi teoriche per dimostrare che i computer quantistici sono in grado di risolvere in tempi rapidi anche una classe di problemi impiegati per la crittografia post-quantistica.
Prima di procedere con l’analisi di quanto pubblicato, va specificato che non ci sono attualmente conferme riguardo la bont� della pubblicazione e che non c’� una dimostrazione che sia possibile attaccare i cifrari post-quantistici. Non c’�, dunque, ragione di allarmarsi per il momento.
Un problema difficile
La crittografia si basa sull’idea che un testo possa essere reso illeggibile applicando delle operazioni che sono difficili da invertire se non sono note a priori. Il cifrario di Cesare, ad esempio, spostava le lettere di una quantit� predefinita rendendo il testo incomprensibile: cf gugorkq, kp swguq oqfq, rgt fktg xgpk xkfk xkek. La frase precedente � priva di senso ed � difficile ricostruire cosa possa voler dire, ma sapendo che � stato applicato uno spostamento di due lettere (in gergo C+2, per cui “a” corrisponde a “c”, “b” a “d” e cos� via) � facile ricostruire il testo iniziale. Lasciamo ai lettori il divertimento di applicare il procedimento in senso inverso.
I sistemi di crittografia sono diventati sempre pi� evoluti, in corrispondenza con il progresso nelle tecniche di decifrazione e con quello nelle tecnologie disponibili per cifrare i dati. L’arrivo dei computer quantistici impone di adottare nuovi standard di crittografia, giacch� Peter Shor dimostr� nel 1994 come tali dispositivi siano in grado di abbattere significativamente il livello di complessit� dei problemi su cui si basano i cifrari e i protocolli a chiave pubblica utilizzati oggigiorno, rendendo la loro rottura possibile in un arco di tempo molto ridotto (nell’ordine dei giorni, anzich� delle migliaia di anni).
Nel 2022 il NIST annunci� quattro nuovi cifrari, due dei quali basati sui reticoli ordinati. Tali cifrari sono basati su problemi ritenuti difficili da risolvere anche dai computer quantistici, e pertanto non vulnerabili come la crittografia classica. Il ricercatore Daniel R. Simon di AWS avrebbe per� scoperto che � possibile attaccare anche tali problemi, superando alcuni ostacoli teorici precedentemente ritenuti insormontabili, e ha pubblicato uno studio in fase preliminare. Per un curioso caso del fato, Simon � colui il quale poggi� le basi teoriche per l’algoritmo di Shor.
Va specificato che, allo stadio attuale, non c’� ancora stata una verifica indipendente da parte di altri ricercatori della bont� dello studio, n� � stato prodotto un algoritmo che dimostri come sia possibile rompere alcuni cifrari post-quantistici. Lo studio di Simon porta a un progresso nella teoria della complessit�, dal quale potranno poi derivare attacchi ai cifrari se ci sar� una conferma di quanto scoperto.
Nello specifico, Simon afferma di aver trovato un algoritmo quantistico per risolvere in tempo polinomiale il problema delle classi laterali diedriche (in inglese “dihedral coset problem”, o DHP) a cui � possibile ridurre il problema del vettore pi� corto nei reticoli ordinati, e dunque calcolare in tempo polinomiale un’approssimazione del vettore pi� corto in un reticolo ordinato a N dimensioni. In altri termini, sarebbe possibile trovare in tempi relativamente rapidi una soluzione vicina a quella ottimale ai problemi su cui si basano alcuni cifrari post-quantistici.
Un punto su cui bisogna insistere � quello che lo studio parla di trovare un’approssimazione della soluzione e non la soluzione. Lo stesso avviene per un’altra applicazione, chiamata learning with errors, in cui le informazioni sono nascoste dall’introduzione volontaria di errori all’interno di equazioni matematiche; anche in questo caso sarebbe possibile arrivare a un’approssimazione, ma ci� non sarebbe possibile per tutte le classi del problema.
Trovare un ago in un pagliaio
Immaginate di avere un reticolo di punti su un foglio a quadretti. Trovare il vettore che porta pi� velocemente da un punto a un altro � un problema banale. Immaginate per� ora che sia necessario eseguire la stessa operazione in uno spazio a N dimensioni: in tal caso diventa molto pi� complesso, al punto che anche i supercomputer pi� potenti al mondo e i computer quantistici non riescono a farlo in tempi ragionevoli. � il proverbiale ago in un pagliaio.
Il metodo scoperto da Simon si basa su studi precedenti che avevano dimostrato come fosse possibile ridurre la complessit� dei problemi basati sui reticoli ordinati, ma richiedevano l’uso di un oracolo, ovvero un ente astratto in grado di fornire una risposta a un sotto-problema per il quale non sono noti metodi efficienti di risoluzione. La novit� sta nel fatto che Simon avrebbe scoperto un modo per risolvere tali problemi realmente e non passando per un oracolo.
Tale modo divide un insieme di grandi dimensioni di campioni quantistici in gruppi, in modo tale che sia possibile usare alcuni gruppi senza introdurre fasi indesiderate, e misurando altri gruppi in maniera separata cos� da mantenere lo stato quantistico bilanciato. Trasferendo, un bit alla volta, la codifica della fase del valore nascosto verso un qubit ausiliario, � possibile ricostruire il valore completo. Una spiegazione pi� tecnica � disponibile su Postquantum.
Il metodo di Simon rimuoverebbe dunque l’ostacolo che rendeva i precedenti attacchi infattibili e aprirebbe le porte ad attacchi verso i cifrari post-quantistici.
La possibilit� che non funzioni e il ruolo della “critto-agilit�”
Daniel Apon, direttore della crittografia presso Anduril Industries, ha pubblicato uno studio di risposta intitolato “The Search for Simon” (citazione del film “Star Trek: The Search for Spock”) in cui smonta una parte del teorema su cui si basa la pubblicazione di Simon. Nel messaggio su LinkedIn in cui lo annuncia, Apon si spinge ad affermare che “non credo che l’algoritmo DCP-LWE di Simon sia corretto. Il Lemma 3 � chiaramente falso. Dopo molti sforzi, non vedo come riparare l’analisi.” Ci� farebbe intendere che i risultati di Simon non siano validi o che richiedano quantomeno del lavoro per poter funzionare.
Attualmente molti esponenti di spicco nel mondo della crittografia e della matematica dei reticoli ordinati stanno lavorando per determinare se lo studio di Simon sia veritiero. Non c’� ancora consenso da parte degli esperti e si arriver� a delle conclusioni pi� certe solo nel corso delle prossime settimane.
Nel frattempo, per�, resta confermato un fatto, ovvero che la cosiddetta critto-agilit� � una necessit� incontrovertibile. Con ci� s’intende il fatto che � necessario progettare il software affinch� non sia basato su uno specifico cifrario, ma sia modulare e possa gestire cifrari differenti cos� da adattarsi a uno scenario in continua evoluzione, in cui � possibile che vengano scoperti attacchi a soluzioni considerate non vulnerabili.
Questo � proprio lo scenario attuale: un’intera classe di problemi sarebbe diventata inaffidabile come base su cui poggiare la crittografia, il che richiederebbe di rivedere tutto l’impianto crittografico attuale basato su ML-KEM e ML-DSA. Usando un approccio tradizionale, in cui il supporto a tali cifrari � “hardcoded” all’interno del software, sarebbe necessario ricostruire tutto; con un approccio “critto-agile”, invece, sarebbe sufficiente sostituire i cifrari.
Quello della critto-agilit� � un tema su cui gli esperti insistono da anni e questo caso dimostra come sia l’approccio corretto, indipendentemente dal fatto che lo studio di Simon venga confermato oppure smentito. Le aziende e le organizzazioni che ancora non abbiano adottato questo approccio non possono continuare a ignorarlo e devono iniziare ad adottarlo adesso.
Dall’altro lato, � necessario che le aziende che stanno effettuando delle migrazioni le continuino e che quelle che non le hanno ancora avviate lo facciano. Se anche lo studio di Simon venisse confermato come buono, si parla di un risultato che vedr� realisticamente delle applicazioni pratiche fra qualche decennio, a meno di cambiamenti drammatici nel frattempo. Nel frattempo, la vulnerabilit� dei cifrari classici ai computer quantistici resta indipendentemente da questi ultimi sviluppi e richiede dunque che si agisca ora. Il fatto che Cloudflare, Google e Microsoft abbiano tutte imposto il passaggio ai cifrari post-quantistici entro il 2029 fa capire come sia necessario effettuare questa migrazione il pi� presto possibile.
Rimane ora l’attesa per capire se i risultati di Simon reggeranno l’analisi degli esperti e se si troveranno delle alternative a eventuali falle. In ogni caso, non c’� ragione di non usare ML-KEM e ML-DSA al momento e le migrazioni verso tali cifrari, effettuate usando l’approccio critto-agile, devono continuare: il vero vantaggio � proprio il cambiamento di approccio; che si usi ML-KEM e ML-DSA o altri cifrari, poco importa, perch� si sar� pronti per un’eventuale sostituzione.
#Adessonews seleziona nella rete articoli di particolare interesse.
Se vuoi leggere l’articolo completo clicca sul seguente link
