Full-Key Recovery and Forgery from One MQOM v2.1 Signature

Immagina di dover inviare un messaggio segreto a un amico, ma vivi in un mondo dove potrebbero un giorno esistere computer super-veloci (chiamati computer quantistici). Queste macchine del futuro potrebbero rompere la maggior parte delle serrature che usiamo oggi per proteggere i nostri segreti. Per prepararsi a questo, gli scienziati stanno costruendo nuovi, super-forti lucchetti digitali chiamati "firme post-quantistiche". Pensali come una speciale sorta di sigillo di cera su una lettera. Anche se un ladro avesse un martello magico capace di frantumare le serrature normali, questo nuovo sigillo di cera è fatto di un materiale che dovrebbe resistere.

Uno dei nuovi lucchetti più promettenti in fase di test è chiamato MQOM. Funziona un po' come un puzzle gigante e complesso. Per firmare una lettera, il mittente usa un "testimone" segreto (una chiave nascosta) per risolvere un problema matematico che coinvolge molte variabili. Per dimostrare di aver risolto il problema senza mostrare il segreto, utilizza un trucco astuto chiamato "MPC-in-the-head". Immagina che il mittente finga di essere un intero team di persone, ognuna con un piccolo pezzo del segreto. Giocano a un gioco in cui rivelano solo il necessario per dimostrare che il team ha risolto il puzzle insieme, ma non abbastanza da rivelare i pezzi segreti effettivi. Se la matematica regge, la firma è valida. Ci interessa perché se questi nuovi lucchetti avessero una crepa nascosta, la nostra sicurezza digitale futura potrebbe crollare prima ancora di arrivarci.

Ora, parliamo della storia in questo articolo. Un ricercatore di nome José Luis Delgado ha esaminato attentamente una versione specifica di questo lucchetto MQOM (versione 2.1) e ha scoperto un modo sorprendentemente semplice per romperlo. L'articolo sostiene che se un attaccante ottiene anche una sola firma valida dal sistema, può scoprire l'intera chiave segreta e falsificare nuove firme per qualsiasi messaggio voglia. È come se un ladro vedesse aprire la porta di casa tua una sola volta, e quel singolo sguardo fosse sufficiente per costruirsi una chiave universale che apre ogni serratura della tua casa.

Ecco come funziona il "trucco magico", spiegato attraverso una storia. Immagina che la chiave segreta sia una lunga mappa del tesoro nascosta. Il sistema MQOM nasconde questa mappa all'interno di un albero gigante fatto di rami. Quando firmi un messaggio, il sistema ti mostra un percorso verso l'alto nell'albero fino a una specifica foglia nascosta (un punto sulla mappa), ma mantiene la foglia stessa coperta. Tuttavia, ti fornisce anche un "percorso fratello" (sibling path) — un elenco dei rami accanto alla foglia nascosta. A causa di come l'albero è costruito, se conosci i rami accanto alla foglia, puoi capire esattamente quale sarebbe la foglia nascosta se conoscessi un piccolo prefisso della mappa segreta.

L'articolo ha scoperto che il sistema lascia anche un "impegno" (commitment), che è come una busta sigillata contenente la foglia nascosta. Il ricercatore si è reso conto che combinando il percorso fratello (i rami) con la busta sigillata, potevano scrivere un'unica, gigantesca equazione. Questa equazione ha un'unica incognita: il piccolo prefisso della mappa segreta. L'attaccante non ha bisogno di indovinare l'intera mappa; deve solo risolvere questa singola equazione per trovare quel piccolo prefisso.

Una volta trovato questo prefisso, la firma che già possiede fornisce un "suffisso di correzione" (correction suffix) — un piccolo appunto che dice: "Ecco il resto della mappa da abbinare al prefisso che hai appena trovato". Unendo il prefisso e la nota, l'attaccante ricostruisce l'intera mappa segreta (la chiave di firma completa). Con questa chiave, può firmare qualsiasi nuovo messaggio e il sistema lo accetterà come reale.

L'articolo non si limita a ipotizzare che questo funzioni; hanno effettivamente fatto i calcoli e il lavoro al computer per dimostrarlo. Hanno calcolato esattamente quanta potenza di calcolo sarebbe necessaria per risolvere questa equazione per i diversi livelli di forza del lucchetto (chiamati Categorie I, III e V). Hanno scoperto che per tutte e tre le categorie, lo sforzo richiesto è inferiore al limite di sicurezza stabilito da NIST per questi lucchetti.

Per il livello più facile (Categoria I), l'attacco richiede circa $2^{142.335112}$ operazioni. Per il livello medio (Categoria III), richiede circa $2^{206.774558}$ o $2^{206.988685}$ operazioni, a seconda di quanta parte della mappa viene scansionata. Per il livello più difficile (Categoria V), richiede circa $2^{271.794162}$ operazioni. In ogni caso, il numero di passaggi che l'attaccante deve compiere è inferiore al numero di passaggi che il lucchetto avrebbe dovuto richiedere per essere sicuro.

I ricercatori non si sono fermati alla matematica. Hanno costruito un programma per computer che ha effettivamente eseguito l'attacco. Hanno preso una firma reale, hanno risolto l'equazione, hanno recuperato l'esatta chiave segreta byte per byte e poi hanno usato quella chiave per firmare un messaggio completamente nuovo. Il verificatore del sistema ha controllato la nuova firma e ha detto: "Sì, è valida!". Questo ha dimostrato che l'attacco funziona nel mondo reale, non solo sulla carta.

L'articolo ha anche esaminato se cambiare alcune impostazioni potesse risolvere il problema. Hanno scoperto che aggiungere semplicemente un "sale" (un numero casuale) al processo cambia i numeri nell'equazione, ma non ferma l'attacco. L'equazione esiste ancora; appare solo leggermente diversa. Per risolvere veramente il problema, i progettatori dovrebbero cambiare il modo in cui il percorso dell'albero si relaziona con il segreto, come la foglia viene impegnata o come viene generato il appunto di correzione.

In breve, questo articolo mostra che l'attuale versione del lucchetto MQOM ha un buco abbastanza grande da poterci camminare attraverso. Trasforma una singola firma in una chiave universale, permettendo a un attaccante di falsificare messaggi con meno sforzo di quanto il lucchetto fosse progettato per resistere. L'autore ha condiviso il proprio codice e i risultati in modo che altri possano controllare il proprio lavoro, e suggerisce che i progettatori di MQOM debbano riparare queste parti specifiche del sistema prima che possa essere considerato sicuro per il futuro.