Distanza di unicità

Con distanza di unicità ci si riferisce, in crittografia, alla lunghezza minima necessaria che un testo cifrato deve avere affinché sia possibile violare il cifrario con un attacco a forza bruta riducendo a zero il numero di possibili chiavi spurie.

Considerando un attacco alla stringa di testo cifrato "WNAIW" cifrata con il cifrario di Vigenère ed una chiave di 5 lettere. In teoria, questa stringa potrebbe essere decifrata in qualunque altra stringa — RIVER e WATER sono entrambe soluzioni possibili, per certe chiavi. Questa è una regola generale della crittanalisi: senza ulteriori informazioni, è impossibile decodificare questo messaggio.

Ovviamente, anche in questo caso, sono possibili solo un certo numero di parole di senso compiuto composte da 5 lettere: provando tutte le possibili chiavi non si otterrebbero solo RIVER e WATER ma anche, ad esempio, SXOOS, KHDOP ed altre. Il numero di chiavi "funzionanti" sarà quindi molto minore dell'intero insieme di tutte le possibili chiavi. Il problema è conoscere quale di queste chiavi "funzionanti" è quella giusta, le altre sono solo chiavi spurie.

Relazione con la dimensione della chiave ed i possibili testi in chiaro

In generale, data una particolare ipotesi circa la dimensione della chiave ed il numero di messaggi possibili, c'è una lunghezza media del testo cifrato per la quale c'è (in media) solo una chiave che genererà un messaggio leggibile. Nel precedente esempio abbiamo solo lettere maiuscole dell'alfabeto latino, per cui se ipotizziamo che questo sia l'alfabeto usato allora ci sono 26 possibili lettere per ogni carattere della stringa. Allo stesso modo, se ipotizziamo l'uso di chiavi lunghe 5 caratteri composte solo da lettere maiuscole, allora ci sono K=26⁵ possibili chiavi, la maggior parte delle quali non "funzionerà".

Anche usando questo piccolo insieme di caratteri, si possono generare un numero elevatissimo di messaggi N:

N = 26L

dove L è la lunghezza del messaggio. Come detto, solo una piccola parte di essi sarà un messaggio in chiaro leggibile a causa delle regole del linguaggio, diciamo M di essi, dove M si spera sia molto più piccolo di N. Inoltre M ha una relazione uno-ad-uno con il numero di chiavi che funzionano, per cui dato K essere il numero di chiavi possibili, solo

K × (M/N)

di esse "funzioneranno". Una di queste è la chiave corretta, le altre sono spurie. Dato che N dipende dalla lunghezza del messaggio L, e siccome M dipende dal numero delle chiavi K, ci sono dei valori di L per cui il numero di chiavi spurie è pari a zero: questo L è la distanza di unicità.

Relazione con l'entropia della chiave e la ridondanza del testo in chiaro

La distanza di unicità può essere anche definita come il minimo numero di testi cifrati necessari ad un attaccante dotato di una potenza elaborativa illimitata per recuperare l'unica chiave di cifratura funzionante.

La distanza di unicità che ci si attende è di conseguenza:

$U=H(k)/D$

dove U è la distanza di unicità, H(k) è l'entropia dello spazio delle chiavi (ad esempio 128 per 2¹²⁸ chiavi equamente possibili, un po' di meno se la chiave è una frase memorizzata).

D è definito come la ridondanza del testo in chiaro in bit per carattere.

Ora, un alfabeto di 32 caratteri può portare 5 bit di informazione per carattere (dato che 32 = 2⁵). In generale il numero di bit di informazione è log₂ N, dove N è il numero di caratteri dell'alfabeto. Così, in inglese ogni carattere può trasportare log₂ 26 = 4,7 bit di informazione, in italiano log₂ 21 = 4,39 bit (vedere logaritmo per maggiori informazioni sull'operazione).

Comunque il numero medio di informazione trasportata per carattere da un testo di senso compiuto è solo di circa 1,5 bit per carattere, per cui la ridondanza del testo in chiaro è

D = 4,7 - 1,5 = 3,2.

Solitamente maggiore è la distanza di unicità e più sicuro sarà lo schema. Per uno schema one-time pad, ad esempio, data la sconfinata entropia dello spazio della chiave, si ha

$U=\infty$, 

che è coerente con l'assunto che uno schema one-time-pad sia teoricamente inviolabile.

Per un semplice cifrario a sostituzione il numero di chiavi possibili è 26! = 4,0329 * 10²⁶, il numero di modi in cui l'alfabeto può essere permutato. Ipotizzando che tutte le chiavi siano equamente possibili, si ha la seguente entropia:

H(k) = log2(26!) = 88,4 bit

Come detto sopra, nella lingua inglese D è pari a 3,2, per cui si ha una distanza di unicità

U = 88,4/3,2 = 28

Per cui dati 28 caratteri di testo cifrato sarebbe in teoria possibile ricavare per l'inglese un testo in chiaro di senso compiuto e, conseguentemente, la chiave di cifratura.

Applicazioni pratiche

La distanza di unicità è una misura teoricamente utile ma non dice molto circa la sicurezza di un cifrario a blocchi quando viene attaccato da un avversario con (limitate) risorse reali. Consideriamo un cifrario a blocchi con una distanza di unicità di tre blocchi di testo cifrato: anche se un avversario dotato di potenza elaborativa illimitata ha abbastanza informazioni per recuperare la giusta chiave (con una semplice ricerca esaustiva) l'operazione è in pratica non fattibile.

La distanza di unicità può essere incrementata riducendo la ridondanza del testo in chiaro: un modo per farlo è quello di applicare delle tecniche di compressione dei dati prima di procedere alla cifratura. Questa resta sempre una buona idea, dato che riduce il quantitativo di dati da cifrare. Un altro modo per incrementare la distanza di unicità è quello di incrementare il numero di possibili sequenze valide nei file che vengono letti: se almeno per i primi blocchi di dati qualunque sequenza di bit può effettivamente far parte di un messaggio valido, allora si ha che il valore della distanza di unicità non è stato raggiunto.

Se la ridondanza del testo in chiaro è 0 allora la distanza di unicità è infinita ed il sistema è inviolabile: ciò capita (teoricamente) se il testo in chiaro viene compresso perfettamente. In questo caso è chiaramente impossibile determinare quando è stata trovata la giusta chiave di cifratura.

È possibile considerare i testi cifrati più grandi della distanza di unicità come aventi un'unica decifratura di senso compiuto; i testi in chiaro più piccoli della distanza di unicità possono avere più decifrature plausibili. La distanza di unicità non è una misura di quanto testo cifrato sia richiesto per una crittanalisi ma di quanto testo cifrato sia richiesto affinché ci sia una soluzione accettabile per la sua crittanalisi.

Voci correlate

• Crittanalisi
• Teoria dell'informazione

Collegamenti esterni

• Bruce Schneier: How to Recognize Plaintext (Crypto-Gram Newsletter, 15 dicembre 1998)