Crittografia post-quantistica: nuovo algoritmo "andato in 60 minuti"

Abbiamo scritto di PQC, abbreviazione di crittografia post-quantistica, diverse volte prima.

Nel caso ti sia sfuggito tutto l'entusiasmo mediatico degli ultimi anni sul cosiddetto calcolo quantistico...

…è (se mi perdoni quella che probabilmente alcuni esperti considereranno una sconsiderata semplificazione eccessiva) un modo di costruire dispositivi informatici in grado di tenerne traccia molteplici possibili esiti di un calcolo allo stesso tempo.

Con molta cura, e forse un po' di fortuna, questo significa che puoi riscrivere alcuni tipi di algoritmo per trovare la risposta giusta, o almeno scartare correttamente tutta una serie di risposte sbagliate, senza provare e testare ogni possibile risultato uno per uno.

Sono possibili due interessanti accelerazioni crittoanalitiche utilizzando un dispositivo di calcolo quantistico, supponendo che se ne possa effettivamente costruire uno adeguatamente potente e affidabile:

• Algoritmo di ricerca quantistica di Grover. Di solito, se vuoi cercare una serie di risposte ordinate casualmente per vedere se la tua è nell'elenco, ti aspetteresti di sfogliare l'intero elenco, nel peggiore dei casi, prima di ottenere una risposta definitiva. Ad esempio, se si desidera trovare la chiave di decrittazione AES a 128 bit per decodificare un documento, è necessario cercare nell'elenco di tutte le chiavi possibili, a partire da 000..001, ..2, ..3, e così via, fino a FFF..FFF (16 byte di FF), per essere certi di completare il problema. In altre parole, devi avere un budget per provare tutti e 2¹²⁸ chiavi possibili prima di trovare la chiave giusta o determinare che non ce n'era una. L'algoritmo di Grover, tuttavia, dato un computer quantistico abbastanza grande e potente, afferma di essere in grado di completare la stessa impresa con il radice quadrata del solito sforzo, craccando così il codice, in teoria, in soli 2⁶⁴ invece ci prova.
• Algoritmo di fattorizzazione quantistica di Shor. Diversi algoritmi di crittografia contemporanei si basano sul fatto che la moltiplicazione di due grandi numeri primi insieme può essere eseguita rapidamente, mentre dividere di nuovo il loro prodotto nei due numeri con cui si è iniziato è praticamente impossibile. Per avere un'idea di questo, prova a moltiplicare 59 × 87 usando carta e penna. Potrebbe volerci un minuto o giù di lì per tirarlo fuori (5133 è la risposta), ma non è così difficile. Ora prova dall'altra parte. Dividi, diciamo, 4171 nei suoi due fattori. Molto più difficile! (È 43 × 97.) Ora immagina di farlo con un numero lungo 600 cifre. In parole povere, sei bloccato con il tentativo di dividere il numero di 600 cifre per ogni possibile numero primo di 300 cifre fino a quando non raggiungi il jackpot o scopri che non c'è una risposta. L'algoritmo di Shor, tuttavia, promette di risolvere questo problema con il logaritmo del solito sforzo. Pertanto, la scomposizione di un numero di 2048 cifre binarie dovrebbe richiedere solo il doppio del tempo della scomposizione di un numero a 1024 bit, non il doppio della scomposizione di un numero a 2047 bit, il che rappresenta un enorme aumento di velocità.

Contrastare la minaccia

La minaccia dell'algoritmo di Grover può essere contrastata semplicemente aumentando la dimensione dei numeri che stai utilizzando quadrandoli, il che significa raddoppiare il numero di bit nel tuo hash crittografico o nella tua chiave di crittografia simmetrica. (In altre parole, se pensi che SHA-256 vada bene in questo momento, l'utilizzo di SHA-512 invece fornirebbe un'alternativa resistente al PQC.)

Ma l'algoritmo di Shor non può essere contrastato così facilmente.

Una chiave pubblica di 2048 bit richiederebbe un aumento esponenziale delle sue dimensioni, non semplicemente mediante la quadratura, quindi invece di una chiave di 2 × 2048 = 4096 bit, avresti bisogno di una nuova chiave con la dimensione impossibile di 2²⁰⁴⁸ bit…

...o dovresti adottare un tipo completamente nuovo di sistema di crittografia post-quantistico a cui l'algoritmo di Shor non si applicava.

Bene, l'ente statunitense per gli standard NIST ha gestito a PQC “competizione” dalla fine del 2017.

Il processo è stato aperto a tutti, con tutti i partecipanti benvenuti, tutti gli algoritmi pubblicati apertamente e un controllo pubblico non solo possibile ma attivamente incoraggiato:

Bando per offerte. [Chiuso 2017-11-30]. […] È inteso che i nuovi standard di crittografia a chiave pubblica specificheranno una o più firme digitali aggiuntive non classificate, divulgate pubblicamente, crittografia a chiave pubblica e algoritmi di definizione delle chiavi disponibili in tutto il mondo e in grado di proteggere le informazioni governative sensibili ben nel prossimo futuro, anche dopo l'avvento dei computer quantistici.

Dopo tre cicli di presentazioni e discussioni, ha annunciato il NIST, il 2022-07-05, di aver scelto quattro algoritmi che considerava “standard” con effetto immediato, tutti con nomi dal suono delizioso: CRYSTALS-KYBER, CRYSTALS-Dilithium, FALCONe SPHINCS+.

Il primo (CRYSTALS-KYBER) è usato come quello che viene chiamato a Meccanismo chiave dell'accordo (KEM), in cui due estremità di un canale di comunicazione pubblico inventano in modo sicuro una chiave di crittografia privata una tantum per lo scambio confidenziale dei dati di una sessione. (In poche parole: i ficcanaso ottengono solo cavoli sminuzzati, quindi non possono origliare la conversazione.)

Gli altri tre algoritmi sono usati per Firme digitali, per cui puoi assicurarti che i dati che hai ricevuto corrispondano esattamente a quelli che il mittente ha inserito nell'altro, prevenendo così manomissioni e assicurando l'integrità. (In poche parole: se qualcuno cerca di corrompere o pasticciare con i dati, lo saprai.)

Servono più algoritmi

Contestualmente all'annuncio dei nuovi standard, il NIST ha anche annunciato a quarto round della concorrenza, proponendo altri quattro algoritmi come possibili KEM alternativi. (Ricorda che, al momento in cui scriviamo, abbiamo già tre algoritmi di firma digitale approvati tra cui scegliere, ma solo un KEM ufficiale.)

Questi erano: BIKE, Classic McEliece, HQC ed SIKE.

Curiosamente, il Algoritmo McEliece è stato inventato negli anni '1970 dal crittografo americano Robert Mc Eliece, morto nel 2019, ben dopo che il concorso del NIST era già in corso.

Tuttavia, non ha mai preso piede, perché richiedeva enormi quantità di materiale chiave rispetto alla popolare alternativa del giorno, l'algoritmo Diffie-Hellman-Merkle (DHM, o talvolta solo DH).

Sfortunatamente, uno dei tre algoritmi del Round Four, vale a dire SIKE, sembra essere stato rotto.

In un articolo sconvolgente intitolato UN EFFICIENTE ATTACCO RECUPERO CHIAVI SU SIDH (VERSIONE PRELIMINARE), i crittografi belgi Wouter Castryk e Thomas Decru sembrano aver inferto un colpo mortale all'algoritmo SIKE

Nel caso ve lo stiate chiedendo, SIKE è l'abbreviazione di Incapsulamento della chiave di isogenia sovrasingolare, e SIDH sta per Isogenia supersingolare Diffie-Hellman, un uso specifico del Algoritmo SIKE per cui due estremità di un canale di comunicazione eseguono una "crittodanza" simile a DHM per scambiare una serie di dati pubblici che consentono a ciascuna estremità di derivare un valore privato da utilizzare come chiave di crittografia segreta una tantum.

Non cercheremo di spiegare l'attacco qui; ripeteremo solo ciò che afferma il documento, ovvero che:

In parole povere, gli input qui includono i dati pubblici forniti da uno dei partecipanti alla criptodanza dell'istituzione chiave, insieme ai parametri predeterminati (e quindi pubblicamente noti) utilizzati nel processo.

Ma l'output estratto (le informazioni denominate l'isogenesi φ sopra) dovrebbe essere la parte mai rivelata del processo, la cosiddetta chiave privata.

In altre parole, solo dalle informazioni pubbliche, come i dati scambiati apertamente durante l'impostazione della chiave, i crittografi affermano di essere in grado di recuperare la chiave privata di uno dei partecipanti.

E una volta che conosci la mia chiave privata, puoi facilmente e in modo impercettibile fingere di essere me, quindi il processo di crittografia è interrotto.

Apparentemente, l'algoritmo di cracking dei tasti impiega circa un'ora per fare il suo lavoro, utilizzando solo un singolo core della CPU con il tipo di potenza di elaborazione che troveresti in un laptop di tutti i giorni.

Questo va contro l'algoritmo SIKE quando configurato per soddisfare il livello 1, il grado di sicurezza della crittografia di base del NIST.

Cosa fare?

Niente!

(Questa è la buona notizia.)

Come suggeriscono gli autori dell'articolo, dopo aver notato che il loro risultato è ancora preliminare, "con lo stato attuale delle cose, SIDH sembra essere completamente rotto per qualsiasi curva di base generata pubblicamente".

(Questa è la cattiva notizia.)

Tuttavia, dato che l'algoritmo SIKE non è ancora ufficialmente approvato, ora può essere adattato per contrastare questo particolare attacco (qualcosa che gli autori ammettono potrebbe essere possibile), o semplicemente abbandonato del tutto.

Qualunque cosa accada alla fine a SIKE, questo è un eccellente promemoria del motivo per cui cercare di inventare i propri algoritmi di crittografia è irto di pericoli.

È anche un chiaro esempio del perché i sistemi di crittografia proprietari che si basano sulla segretezza dell'algoritmo stesso per mantenere la loro sicurezza sono semplicemente inaccettabili nel 2022.

Se un algoritmo PQC come SIKE fosse sopravvissuto per più di cinque anni alla persecuzione e all'indagine da parte di esperti di tutto il mondo, nonostante fosse stato divulgato specificamente in modo che potesse essere sottoposto a controllo pubblico...

…allora non c'è bisogno di chiedersi quanto bene se la caveranno i tuoi algoritmi di crittografia fatti in casa e nascosti alla vista una volta rilasciati in natura!

---