Algoritmo crittografico post-quantistico sconfitto con un vecchio processore Xeon

Gli attuali computer quantistici sono ancora ben lontani dall’essere utilizzabili per risolvere problemi reali. Dietro al concetto di supremazia quantistica c’è tanto marketing tanto che, ad esempio, IBM ha criticato duramente Google nella loro sfida per la creazione del computer quantistico più potente ed efficace al mondo.

Un giorno però i computer quantistici risolveranno problemi reali e troveranno soluzioni che con la potenza computazionale offerta dai sistemi tradizionali, basati sui bit 0 e 1, sono impraticabili da individuare.

Parlando di crittografia un computer quantistico potrebbe in futuro fattorizzare grandi numeri riuscendo a violare gli algoritmi a chiave pubblica RSA e Diffie-Hellman con tutte le dimensioni di chiave utili. Per spiegare la sicurezza di un algoritmo crittografico abbiamo visto proprio il caso RSA.

Quando si ha a che fare con la crittografia e quindi con algoritmi che permettono di proteggere dati personali, informazioni sensibili e materiale riservato in molteplici ambiti (e che sono quindi utilizzati anche in ambito governativo e militare), è fondamentale non farsi trovare impreparati. Cosa succederebbe se un algoritmo crittografico venisse “rotto” da un Paese che fosse riuscito, prima di tutti gli altri, a sviluppare un quantum computer sufficientemente potente e affidabile?

Prima che possa configurarsi tale scenario è necessario essere passati ad algoritmi che offrano sufficienti misure di sicurezza post-quantum ovvero che siano in grado di resistere agli attacchi lanciati usando i futuri computer quantistici.
Nel 2016 il NIST (National Institute of Standards and Technology) ha lanciato un programma con l’intento di individuare algoritmi adatti a proteggere le informazioni nell’era del quantum computing.
Si tratta di una vera e propria gara che coinvolge Paesi e crittografi di tutto il mondo. Qualcosa di molto simile era stato già fatto in passato dal NIST: ad esempio di un algoritmo a chiave simmetrica come AES (nel 2001) e della funzione hash SHA-3 (nel 2015).

SIKE, un algoritmo per la cifratura dei dati post-quantistica sconfitto con un semplice Xeon

A fine luglio 2022 abbiamo pubblicato la lista degli algoritmi per la cifratura post-quantistica approvati dal NIST.
Si tratta dei primi quattro “papabili” ai quali potrebbero aggiungersene altri nel prossimo futuro.

Come mette in evidenza il noto crittografo Bruce Schneier uno degli algoritmi sulla carta più apprezzati, Rainbow, è risultato violabile senza grossi problemi mentre tre dei finalisti, approvati dal NIST, ovvero Kyber, Saber e Dilithium sono stati indeboliti con nuove tecniche che probabilmente funzioneranno anche contro alcuni degli altri algoritmi.

Schneier racconta che questi tre nuovi algoritmi sono stati violati dal Center of Encryption and Information Security, parte delle forze di difesa israeliane. È la prima volta che un’organizzazione di intelligence nazionale ha pubblicato un risultato di crittoanalisi in letteratura. Tra l’altro ci sono stati non pochi problemi in fase di pubblicazione dello studio perché i suoi autori volevano rimanere anonimi. Alla fine la ricerca è stata condivisa online a questo indirizzo.

Rainbow teoricamente avrebbe resistito a un attacco sferrato con un computer quantistico ma è stato dimostrato che può essere aggredito con un laptop standard in poco più di due giorni di lavoro.

Oggi tocca a SIKE (Supersingular Isogeny Key Encapsulation), uno degli altri quattro algoritmi che il NIST sta prendendo in considerazione.
Microsoft, il cui team di ricerca ha svolto un ruolo importante nello sviluppo dell’algoritmo insieme a diverse università, Amazon, Infosec Global e Texas Instruments, aveva promesso un premio di 50.000 dollari a favore di chiunque fosse stato in grado di violare SIKE.

Un po’ come avvenuto con Rainbow, i belgi Wouter Castryck e Thomas Decru sono riusciti nell’intento sconfiggendo SIKE non usando un computer quantistico bensì un sistema basato su un vecchio processore Intel Xeon E5-2630v2 a 2,60 GHz, quindi su architettura x86.

Microsoft ha descritto SIKE spiegando che usa operazioni aritmetiche su curve ellittiche definite su campi finiti e mappe di calcolo, dette anche isogenie. I ricercatori ritenevano che il livello di sicurezza fornito da questa soluzione fosse davvero notevole; valutazioni che sono state smentite dal lavoro di due esperti che hanno usato un processore vecchio ormai di 9 anni (l’Intel Xeon del quale si sono serviti risale al 2013 ed è basato su architettura Ivy Bridge a 22 nm).

Ian Cassels, matematico britannico e crittoanalista della seconda guerra mondiale, una volta disse che “la crittografia è un misto di matematica e confusione, e senza la confusione la matematica può essere usata contro di te“.
Come osserva Schneier, “questa combinazione è particolarmente difficile da ottenere con gli algoritmi a chiave pubblica che si basano sulla matematica per la loro sicurezza in un modo diverso da quanto fanno gli algoritmi simmetrici. Siamo stati fortunati con RSA e relativi algoritmi: la loro matematica è imperniata sul problema della fattorizzazione che si è rivelato estremamente difficile (da risolvere per i computer tradizionali, n.d.r.). “Gli algoritmi post-quantistici si basano su altre discipline e problemi matematici – crittografia basata su codice, crittografia basata su hash, crittografia basata su reticolo, crittografia multivariata e così via –“.

Secondo Schneier è necessario guardare all’agilità crittografica: “non è sufficiente implementare un unico standard; è fondamentale che i nostri sistemi siano in grado di passare facilmente a nuovi algoritmi quando necessario. Abbiamo imparato come gli algoritmi possano radicarsi così tanto nei sistemi da richiedere molti anni per aggiornarli: lo abbiamo visto nel passaggio da DES ad AES, da MD4 a MD5, da SHA a SHA-1 e quindi a SHA-3“.

Quando e se l’informatica quantistica diventerà una realtà pratica, impareremo molto sui suoi punti di forza e sui suoi limiti. Ci sono voluti un paio di decenni per comprendere appieno l’architettura di von Neumann: Schneier aggiunge che è lecito aspettarsi la stessa curva di apprendimento nel caso del calcolo quantistico. “La nostra attuale comprensione dell’architettura del calcolo quantistico cambierà e ciò potrebbe facilmente portare a nuove tecniche di crittoanalisi. La seconda incertezza è negli algoritmi stessi. Come dimostrano i nuovi risultati della crittoanalisi, stiamo ancora imparando molto su come trasformare difficili problemi matematici in crittosistemi a chiave pubblica. Abbiamo troppa matematica e allo stesso tempo siamo incapaci di aggiungere più confusione: ciò si traduce in algoritmi che sono vulnerabili ai progressi in ambito matematico“.