Questo algoritmo, in linea di principio semplicissimo, venne descritto per la prima volta da Frank Miller nel 1882 e quindi riscoperto da Gilbert Vernam nel 1919. Nella sua forma originale esso veniva applicato alle lettere dell'alfabeto inglese, mentre qui descriveremo la versione moderna applicabile alla codifica binaria dei caratteri.
Il cifrario di Vernam è l'unico sistema crittografico la cui sicurezza sia stata dimostrata matematicamente (da Claude Shannon nel 1949) e per questo viene anche detto "cifrario perfetto". In parole povere, come vedremo fra un attimo, è impossibile violare la sicurezza di questo cifrario, anche ricorrendo alle tecniche più avanzate di crittoanalisi. Pur tuttavia, One Time Pad viene usato molto raramente, almeno nella sua forma originaria. Vediamo perché.
Il punto di partenza dell'algoritmo OTP è un'operazione binaria molto semplice detta Or Esclusivo (o per brevità EX-OR). Supponiamo di avere due bit A e B, ciascuno dei quali può valere o zero o uno. L'operazione EX-OR fra A e B si indica così (si legge A exor B):
La variabile U indica il risultato dell'operazione logica fra A e B e assume i valori indicati dalla tabella seguente (detta tabella di verità):
| A | B | U |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
La tabella precedente dice per esempio che se A vale zero e B vale zero, allora il risultato dell'ex-or fra A e B vale esso pure zero. In modo simile se A vale zero e B vale uno, il risultato è 1 e così via negli altri casi. In modo molto più sintetico si può dire che l'EX-OR vale 1 solo se i due bit sono diversi fra loro (cioè uno vale zero e l'altro vale uno), mentre vale 0 se i due bit hanno lo stesso valore.
L'operazione EX-OR può essere anche calcolata fra gruppi di più bit, calcolando l'EX-OR fra le coppie di bit di uguale posizione. Facciamo un rapido esempio. Supponiamo di avere:
A = 10101100 B = 11011010
Per calcolare l'EX-OR fra A e B dobbiamo fare l'EX-OR fra ogni bit di A e ogni bit di B, come indicato nella tabella seguente:
| A | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 |
| B | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
| U = A exor B | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 0 |
La cosa interessante dell'EX-OR è che facendo di nuovo l'EX-OR fra U e B si riottiene A, come mostra la tabella qui sotto:
| U | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 0 |
| B | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
| A | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 |
Dunque l'operazione EX-OR è in qualche modo reversibile, ovvero è possibile tornare indietro calcolando di nuovo l'EX-OR.
Il cifrario di Vernam o OTP si basa su:
- un messaggio in chiaro scritto in binario (per esempio
usando il codice ASCII di ogni carattere);
- una chiave formata da una sequenza binaria casuale lunga
quanto il messaggio da cifrare (questa chiave viene detta
One Time Pad (spesso abbreviato con OTP),
letteralmente Blocco Monouso, per le ragioni che saranno
chiare più avanti);
- un algoritmo di cifratura che consiste semplicemente nel calcolo dell'EX-OR fra il messaggio e la chiave.
Facciamo subito un semplice esempio. Supponiamo di voler cifrare la parola CIAO. Per prima cosa trasformiamola in binario usando il codice ASCII:
C = 01000011 I = 01001001 A = 01000001 O = 01001111
Il nostro messaggio in chiaro in forma binaria è dunque questo (gli spazi fra un Byte e il seguente sono stati inseriti solo per facilitare la leggibilità):
01000011 01001001 01000001 01001111
Adesso ci serve una chiave binaria lunga quanto il messaggio, cioè composta da 32 bit ovvero da 4 Byte. Per ragioni che spiegheremo dopo, questa chiave dovrebbe essere casuale, cioè formata da bit generati senza seguire nessuna regola o formula. Supponiamo che la nostra chiave sia:
01001110 11101111 00010001 10010110
A questo punto per cifrare il messaggio dobbiamo semplicemente calcolare l'EX-OR bit a bit fra ogni bit del messaggio in chiaro e ogni bit corrispondente nella chiave. Qui sotto è riportata la tabella con i calcoli (M è il messaggio in chiaro, C la chiave di cifratura e R il messaggio cifrato risultante):
|
M |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
|
C |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
|
R |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
Nel nostro caso abbiamo dunque il seguente messaggio cifrato:
00001101 10100110 01010000 11011001
Il messaggio cifrato può essere facilmente decifrato se si dispone della chiave, poiché basta calcolare l'EX-OR fra il messaggio cifrato e la chiave per ottenere di nuovo il testo in chiaro (l'operazione EX-OR infatti è, come detto, reversibile).
Come si è visto One Time Pad è davvero un metodo di cifratura molto semplice. Abbiamo affermato prima che questo metodo è anche assolutamente inattaccabile e che questa inattaccabilità può essere dimostrata matematicamente.
La ragione per cui il metodo è teoricamente inattaccabile è che, se l'attaccante non conosce la chiave, esso è costretto a provare tutte le chiavi possibili col metodo della forza bruta. Ma anche per il breve messaggio (CIAO, solo 4 lettere!) del nostro semplice esempio, il numero di chiavi possibili è pari a 232 cioè a oltre 4 miliardi di possibili combinazioni. E' del tutto evidente che al crescere della lunghezza del messaggio il numero delle chiavi da provare diventa impossibile anche per i calcolatori più potenti.
Ma c'è anche un'altra ragione per cui il metodo della forza bruta non funziona ed è il fatto che, provando tutte le possibili chiavi alla ricerca di quella giusta, l'attaccante si troverebbe di fronte tutti i possibili messaggi di lunghezza uguale a quello da decifrare e sarebbe impossibile sapere a priori qual è la decodifica corretta. Per comprendere meglio quest'ultimo punto, supponiamo di voler provare a decrittare col metodo della forza bruta il nostro breve messaggio cifrato. Come si è detto questo equivale a provare tutte le chiavi da
00000000 00000000 00000000 00000000
fino a
11111111 11111111 11111111 11111111
per un totale di 4.294.967.296 tentativi diversi. Tale numero, sebbene molto alto, è alla portata dei moderni calcolatori e dunque potremmo credere che sia possibile decrittare il nostro messaggio col metodo della forza bruta.
Dunque proviamo con pazienza tutte le chiavi a 32 bit. Supponiamo ora di provare la chiave:
01000000 11100111 00011110 10010000
Calcoliamo l'EX-OR fra la chiave e il messaggio cifrato 00001101 10100110 01010000 11011001 e otteniamo:
01001101 01000001 01001110 01001001
che tradotto in lettere usando il codice ASCII diventa:
01001101 = M 01000001 = A 01001110 = N 01001001 = I
cioè MANI. Come si vede il metodo della forza bruta produce, fra gli altri, anche messaggi che hanno perfettamente senso nella lingua italiana. Anzi, provando tutte le possibili chiavi, vengono prodotti (nel nostro caso) tutti i possibili messaggi composti da 4 lettere, cioè fra gli altri:
CIBO CINA ACNE TOPO NOVE RAPA
eccetera eccetera. Come fa il povero attaccante a sapere qual è il messaggio giusto?
In sintesi One Time Pad è inattaccabile perché, anche ammesso di riuscire a produrre tutte le possibili chiavi, questo non servirebbe a nulla perché si produrrebbero tutti i possibili messaggi e non sarebbe possibile sapere quale, fra i tanti, era il messaggio inviato originariamente.
Abbiamo visto come One Time Pad sia un metodo di cifratura molto semplice e, in teoria, assolutamente sicuro e inattaccabile. Le condizioni per l'assoluta sicurezza del metodo sono però le seguenti:
- la chiave deve essere utilizzata una sola volta (cioè per ogni messaggio deve essere usata una chiave diversa);
- la chiave deve essere perfettamente casuale.
Vediamole entrambe rapidamente. La prima condizione è essenziale perché, se la chiave viene riutilizzata più volte per cifrare messaggi diversi e se l'attaccante riesce in qualche modo a conoscere il testo di uno dei messaggi, automaticamente egli può scoprire la chiave (basta calcolare l'EX-OR) ed essere quindi in grado di decifrare tutti i messaggi successivi.
Anche senza conoscere il testo in chiaro di nessun messaggio, se la chiave venisse riusata più volte, comincerebbero ad apparire ripetizioni e somiglianze fra diversi messaggi cifrati. Usando i moderni metodi di analisi statistica e di crittoanalisi, l'attaccante, disponendo di un numero sufficiente di messaggi da analizzare, sarebbe in grado di risalire alla chiave o almeno a parte di essa e dunque potrebbe violare facilmente la segretezza dell'algoritmo.
Per quanto riguarda l'assoluta casualità della chiave, questo significa che se la chiave viene generata con qualche metodo di calcolo a partire da una chiave più semplice, l'attaccante potrebbe risalire alla chiave più semplice col metodo della forza bruta e da questa generare la chiave di cifratura completa del messaggio. Tanto per fare un esempio, supponiamo che mittente e destinatario si accordino sul fatto che la chiave verrà generata da una serie di ripetizioni del codice ASCII di una certa lettera (es. la X), tante volte quante sono le lettere che compongono il messaggio da cifrare. In questo caso all'attaccante basterebbe indovinare la lettera X per ricostruire immediatamente l'intera chiave.
Inoltre è praticamente molto difficile (se non impossibile) generare una chiave completamente casuale usando i computer, in quanto questi, per definizione, elaborano dati numerici in base a formule, cioè non in modo casuale. In pratica esistono molti algoritmi per produrre numeri pseudocasuali con un computer, ma appunto, come dice il nome, non si tratta di numeri veramente casuali (come quelli che si ottengono, per esempio, lanciando un dado), ma di numeri che assomigliano a numeri casuali pur essendo calcolati per mezzo di formule non casuali. In questi casi tuttavia, se l'attaccante riesce a ricostruire o viene in possesso della formula per la generazione dei numeri pseudocasuali, egli può anche ricostruire la chiave usata.
Si consideri infine anche il fatto che, affinché One Time Pad sia assolutamente inattaccabile, occorre che la chiave sia lunga quanto il messaggio e che venga usata una sola volta. Questo pone problemi praticamente insormontabili, poiché ad ogni messaggio mittente e destinatario dovrebbero scambiarsi una nuova chiave (per giunta una chiave spesso molto lunga). Siccome lo scambio delle chiavi non può avvenire usando la cifratura OTP (altrimenti ci sarebbe di nuovo il problema di come scambiarsi la chiave di cifratura), esso deve avvenire o in chiaro (su un canale ritenuto inattaccabile) oppure usando un altro metodo di cifratura (presumibilmente più debole di OTP). In ogni caso lo scambio della chiave è attaccabile da parte di un decifratore e dunque rende insicuro l'intero metodo.
Per le ragioni qui discusse, OTP riveste un grande interesse teorico ma in pratica non viene quasi mai utilizzato. Esso costituisce tuttavia le basi per lo sviluppo di altri metodi di cifratura più pratici ed inoltre rappresenta un utile termine di paragone per valutare la sicurezza di un qualsiasi metodo di cifratura. Infine le moderne (e in gran parte ancora sperimentali) tecniche di crittografia quantistica, che fanno uso dei fenomeni che avvengono a livello delle particelle subatomiche, hanno dato nuove possibilità di utilizzo a OTP (che però qui non potremo approfondire, essendo argomenti molto complessi e specialistici).
Sito realizzato in base al emplate offerto da
http://www.graphixmania.it
