Il rompicapo di Merkle

Gli algoritmi di cifratura a chiavi simmetriche sono sistemi di cifratura dove due interlocutori (Alice e Bob) concordano preventivamente un algoritmo e una chiave con la quale possono sia cifrare che decifrare dei messaggio. Se gli interlocutori sono più di due e utilizzano lo stesso algoritmo, allora ogni coppia dovrà concordare una chiave diversa. Ciò comporta il delicato problema della distribuzione delle chiavi.

Ralph Merkle, uno dei pionieri della crittografia, negli anni 70 propose una tecnica basata su rompicapi(puzzle) facili da risolvere per il ricevente ma non per un eventuale ascoltatore malintenzionato (Eve). La soluzione di tali puzzle è data provando tutte le possibili chiavi di un messaggio fino a che si trova quella effettivamente corretta (attacco a forza bruta).

(1) Bob genera 2²⁰, circa un milione, di messaggi con scritto: “This is puzzle number x. This is the secret key number y“, dove x è un numero a caso ed y una chiave segreta casuale. Sia x che y sono differenti per ogni messaggio. Usando un algoritmo simmetrico Bob cifra ogni messaggio con una chiave di 20 bit e li manda ad Alice.
(2) Alice sceglie a caso uno dei messaggi ed esegue un attacco a forza bruta recuperandono il testo in chiaro.
(3) Alice cifra il suo messaggio segreto con la chiave scoperta e lo invia a Bob insieme ad x.
(4) Bob adesso, basandosi sull’indice x, conosce la chiave y con la quale Alice ha cifrato il messaggio. Può cosi’ decifrarlo.

Eve per decifrare la conversazione dovrà fare molto più lavoro di Alice o Bob. Per decifrare il messaggio inviato da Alice al passo 3 deve effettuare un attacco a forza bruta su tutti i 2²⁰ messaggi inviati in 1. Considerando che una chiave a 20 bit ha 2²⁰ possibili combinazioni, un attacco a forza bruta ha bisogno, al più, di 2²⁰ operazioni per trovare la chiave di un singolo messaggio, 2²⁰ * 2²⁰ = 2⁴⁰ per trovare le chiavi di tutti. Con un calcolatore che può effettuare 2²⁰ in un secondo Alice troverà la propria chiave in un secondo ma Eve, data la mole di messaggi da scandire, impiegherà circa 12 giorni.