Criptosistemi simmetrici

Nel caso di algoritmi di cifratura simmetrici, Alice e Bob sono in possesso della stessa chiave di cifratura $k$ che condividono: questa chiave permette loro di comunicare attraverso un canale insicuro. Il problema principale di questo approccio è la distribuzione della chiave: come fanno Alice e Bob a mettersi d'accordo su che chiave usare?

Quando la chiave $k$ è identica sia per la cifratura $E$ che la decifratura $D$, allora si dice che $E_{k}$ è una biiezione,

$E_{k}:[0,2^{b}-1]\in m\rightarrow [0,2^{b}-1]\in c$

dove $k$ è l'indice della biiezione in un insieme vasto di possibili biiezioni la cui probabilità di essere scelte dipende dalla probabilità di scegliere una particolare chiave.

Cifratura a blocchi

Scopi principali della cifratura a blocchi sono:

• Fare in modo che ciascun bit di $c$ dipenda da tutti i bit di $m$ e di $k$:
• Rendere il più difficile possibile trovare una qualsiasi relazione statistica tra $c$ ed $m$ senza conoscere $k$;
• Cambiare un singolo bit di $m$ dovrebbe significare che ogni singolo bit di $c$ ha il 50% di probabilità di essere cambiato;
• Cambiare un singolo bit di $c$ dovrebbe significare un cambiamento radicale di $D_{k}(c)={\bar {m}}\neq m$.

Algoritmi a sostituzione casuale

Sono una sottoclasse semplice degli algoritmi a blocchi. Si usa la chiave $k$ come indice delle possibili permutazioni su $M$. Imponendo i messaggi di lunghezza

$|M|=2^{b}$

Ogni chiave sarà lunga $l$ bit,

$l=\log _{2}(2^{b}!)\simeq b\cdot 2^{b}$

$K$ è il keyspace, lo spazio delle chiavi, ed ha dimensione

$|K|=2^{b}!$

che è il numero di possibili chiavi tra cui si può scegliere. Un algoritmo a sostituzione perfettamente casuale è un algoritmo a sostituzione che usa lo spazio delle chiavi $b\cdot 2^{b}$, scegliendovi all'interno una chiave perfettamente casuale.

Si noti che questo tipo di algoritmo è ben lontano dall'offrire la sicurezza perfetta, dal momento che, se il messaggio è più lungo di $2^{b}$ bit, allora sarà necessario riutilizzare la chiave più volte, il che vuol dire introdurre correlazione tra i vari blocchi del messaggio. Questa è una negazione del principio fondamentale

$H(k)\geq H(m)$

perché se $k$ è molto più corto di $m$, allora la sua entropia sarà sicuramente inferiore.

Più il blocco è lungo, minore è il numero di ripetizioni; questo, però, porta anche a dover allungare la chiave $k$.

Per la codifica, il messaggio $m$ dovrà essere diviso in chunks, blocchi

$m=\left(m_{1}|m_{2}|\cdots |m_{i}|\cdots \right)$

A sua volta, anche il cifrato sarà una composizione di blocchi

$c=\left(c_{1}|c_{2}|\cdots |c_{i}|\cdots \right)$

Si nota subito la correlazione tra $m$ e $c$: i blocchi saranno nelle stesse posizioni e si potrà fare analisi di frequenza sul risultato dell'operazione. Siamo ben lontani dalla sicurezza perfetta che richiede l'indipendenza statistica tra $m$ e $c$.

Al diminuire di $b$, sarà sempre più facile fare analisi frequenziale sul cifrato, quindi sarà sempre più facile trovare correlazioni statistiche. Se pensiamo ad una lingua (come l'italiano), questa ha delle ridondanze che possono essere sfruttate per cercare di decifrare i blocchi. Per esempio, in italiano

• $P('a')\gg P('k')$
• $P('e')>P('g')$
• $\cdots$

D'altro canto, all'aumentare di $b$ la dimensione dello spazio delle chiavi aumenta esponenzialmente.

Esempio:

Sia $b=64$ bit. Allora

$l=\log _{2}(|K|)=\log _{2}(2^{64}!)\simeq 2^{70}>10^{26}$ bit

Ora, memorizzare $10^{26}$ bit non è una cosa semplice, né per una macchina, né tantomeno per un umano.

Quindi, per avere un blocco di dimensione accettabile è necessario lavorare con una chiave di dimensioni eccessive.

Esempio: Sostituzione del carattere ASCII, $b=8$

Imponiamo che $M$ sia una stringa di $b=8$ bit, cioè un singolo carattere ASCII.

Si otterrà un algoritmo a sostituzione perfettamente casuale e mono-alfabetico, dove ad ogni lettera dell'alfabeto corrisponde un simbolo cifrato. Si ha:

• $b=8$
• $|M|=2^{8}$
• $|K|=2^{8}!$
• la lunghezza della chiave è $\log _{2}(|K|)\simeq 2^{11}=2048{\text{ bit}}$

Un algoritmo di questo tipo è molto esposto all'analisi della frequenza di ripetizione dei simboli. Usando un algoritmo di questo tipo, una frase come

i vitelli dei romani sono belli

diventerebbe

g bgazqqg pzg xksdrg jkrk hzqqg

Confrontando il cifrato con il testo originale, si può:

• Riconoscere immediatamente le doppie:
• Individuare le lunghezze delle parole;
• Fare analisi statistica sulla frequenza con cui appaiono le lettere;
• ...

Cifratura per permutazione

Stiamo cercando di ridurre la dimensione dello spazio delle chiavi, per renderle gestibili. Un algoritmo per permutazione lavora permutando (spostando) i bit tra di loro, all'interno di un blocco di cifratura. Siccome $b$ bit possono essere trasposti in $(b!)$ maniere, allora la dimensione dello spazio delle chiavi diventa

$|K|=b!$

e la lunghezza della chiave risulta

$l=\log _{2}(b!)$

Esempio:

Con un blocco di $b=64$ bit, si ha una chiave lunga

$l\simeq 384$ bit

In questa maniera otteniamo una chiave di lunghezza ragionevole, ma ci stiamo allontanando sempre di più dalla segretezza perfetta; in particolare, un algoritmo di questo tipo preserva il numero di zeri e uno all'interno dei singoli blocchi e diventa, quindi, molto semplice da crittanalizzare.

Composizione di algoritmi

Abbiamo visto che gli algoritmi per sostituzione e gli algoritmi per permutazione posseggono dei difetti importanti:

• Chiavi lunghe
• Facili da decifrare

Da una composizione di questi due algoritmi, però, possiamo ottenere il meglio da entrambi; la cosa fondamentale da tener presente è che gli algoritmi risultanti dalla composizione dovranno essere invertibili, cosa non sempre vera.

Un algoritmo come quello in figura accetta in ingresso un messaggio lungo $m$, che è la dimensione del blocco. Quello che viene fatto è separare questo blocco in sottoblocchi più piccoli, ai quali si applica un algoritmo di cifratura per sostituzione. In questa maniera, i blocchetti avranno bisogno di una chiave $k$ più corta. A questo punto, i blocchetti cifrati vengono ricomposti in un'unica parola, alla quale viene applicato una cifratura per permutazione; siccome la cifratura per permutazione richiede una chiave più corta, allora si può applicare l'algoritmo a tutta la parola nella sua interezza.

Questo algoritmo, quindi, usa una singola chiave $k$ ripetutamente: $n$ volte per gli algoritmi a sostituzione ed un'altra volta per l'algoritmo a permutazione. Per migliorare ancora di più la protezione, si può decidere di ciclare più volte la parola all'interno dell'algoritmo composizione, in modo tale da amplificare l'effetto valanga: infatti, se si facesse lavorare l'algoritmo per una sola volta, un bit cambiato avrebbe effetto soltanto su $j$ bit (il singolo blocchetto su cui è operata la sostituzione); al contrario, a noi interessa che, se viene cambiato un solo bit della parola originale, tutti i bit del testo cifrato risultino invertiti con probabilità $0.5$.

Per migliorare le prestazioni di questo algoritmo, si può prendere in considerazione l'ipotesi di usare

• XOR
• bit shift
• ...

Data Encryption Standard, DES

L'algoritmo di cifratura DES è simmetrico a blocchi, in cui

• Il numero di bit del blocco è $b=64$ bit;
• La lunghezza della chiave è $l=56$ bit, più altri 8 bit di ridondanza (che servono per proteggere la chiave da errori).

Questo algoritmo è stato pensato per essere molto efficiente se implementato in hardware, e molto inefficiente se implementato in software; infatti, il DES lavora sui singoli bit, mentre i processori devono gestire almeno 8 bit per volta (nei processori moderni, 32 o 64). Il DES è stato definito dalla multinazionale IBM in collaborazione con la National Security Agency del governo americano, e per questo motivo non è mai stato considerato come un algoritmo sicuro. Pubblicato nel 1977 e standardizzato nel 1979 dal NIST, è classificato per utilizzo aziendale e altri usi, quindi non è mai stato pensato per proteggere nulla di veramente importante, come per esempio comunicazioni tra governi ed applicazioni importanti per la sicurezza delle persone.

Ad oggi, il DES risulta essere l'algoritmo più vecchio ancora utilizzato (con alcune modifiche), proprio per la qualità con la quale è stato progettato.

Storia del DES

Il DES è stato commissionato dall'NSA all'IBM, con dei parametri di progetto strani. Quello che succedeva è che l'IBM disegnava il funzionamento dell'algoritmo e, a scadenze programmate, mandava il progetto all'NSA, perché fosse modificato e giudicato. Alcune modifiche fatte dall'NSA erano inspiegabili per gli ingegneri ed i matematici dell'IBM, che furono costretti ad accettare le correzioni senza conoscere i motivi per cui queste venivano fatte.

Questo fatto da sempre ha creato un certo sospetto, da parte degli addetti ai lavori, nei confronti dell'algoritmo DES; in particolare, si sospettavano delle trap doors, cioè si sospettava che l'NSA avesse inserito quelle modifiche in modo tale da poter decrittare i messaggi senza possedere la chiave, con qualche algoritmo sconosciuto alla scienza moderna. Soltanto nel 1992 si scoprirà la crittanalisi lineare, un metodo per analizzare gli algoritmi di cifratura nuovo ed assolutamente innovativo: con la scoperta di questo tipo di crittanalisi, ci si renderà conto che il DES era stato pensato in maniera tale da resistere ad attacchi di questo tipo, quindi già negli anni '70 l'NSA conosceva teorie che il resto del mondo ha conosciuto soltanto negli anni '90: un ritardo di circa 20 - 25 anni che ad oggi si stima possa essersi assottigliato, ma che comunque deve lasciar riflettere ogni volta che ci si approccia ad un algoritmo definito come sicuro che, nella realtà, potrebbe non essere sicuro nei confronti dell'NSA o comunque dei governi del mondo.

Il DES risponde ad una specifica richiesta di progettazione: poco efficiente in software, molto efficiente in hardware. Questa specifica trova una motivazione certamente interessante. Per poter decifrare un testo senza rompere l'algoritmo, è necessario fare una ricerca in tutto lo spazio delle chiavi, fino a trovare la chiave corretta. Per far ciò, è necessario provare tutte le possibili chiavi, decifrando il testo ad ogni tentativo, nella speranza di giungere a qualcosa di sensato. L'idea che spinse l'NSA a richiedere questa specifica è che chi poteva decifrare il testo senza chiave doveva essere soltanto il governo americano (o comunque, un governo potente), l'unico abbastanza ricco da potersi permettere un'implementazione molto efficiente dell'algoritmo.

Un difetto del DES è lo spazio delle chiavi, che sono lunghe soltanto 56 bit. Una chiave di quel tipo permette, ad oggi, una ricerca esaustiva in relativamente poco tempo (con elettronica sufficientemente potente); anche negli anni '70 una chiave di 56 bit era considerata corta: la motivazione, ancora una volta, va ricercata nel fatto che l'algoritmo è di per sé sicuro da attacchi, quindi l'unico modo per romperlo è una ricerca nello spazio completo delle chiavi.

L'algoritmo

Il primo e l'ultimo stadio, le permutazioni, sono indipendenti dalla chiave, ed hanno come unico scopo quello di rendere meno efficiente l'implementazione in software dell'algoritmo. L'algoritmo, inoltre, può essere usato sia per cifrare che per decifrare, cambia soltanto il modo con cui si devono derivare le sottochiavi.

Il generatore di sottochiavi si occupa di derivare delle chiavi da 48 bit, una per ogni step dell'algoritmo. Nel caso in cui si stia decifrando invece che cifrare, allora le chiavi andranno usate in ordine inverso per i vari step.

Le permutazioni iniziale e finale, che non sono casuali, sono una lo speculare dell'altro, cioè si annullano a vicenda. Questa loro proprietà fa sì che la stessa implementazione possa essere usata sia per cifrare che per decifrare il testo.

Generatore di sottochiavi

Gli step dell'algoritmo

Inner function

La funzione interna, inner function, è quella deputata principalmente a creare l'effetto valanga, grazie ai box di espansione.

Box di sostituzione

Ogni box di sostituzione, S-box, è una funzione che lavora su simboli da 4 bit, con una chiave da 2 bit, dove la chiave sono il primo e l'ultimo bit della parola da 6 bit che viene passata al box. Queste funzioni sono implementate attraverso una look-up table, cioè una tabella prestabilita.

La parte più importante di tutto l'algoritmo, la chiave di volta della sicurezza, sta proprio in queste funzioni. Se, infatti, le tabelle di corrispondenza fossero state diverse da quelle decise dall'NSA in fase di progettazione, oggi il DES sarebbe stato rotto, proprio grazie all'invenzione della crittoanalisi lineare, del 1992.

Tutto l'algoritmo DES è basato soltanto su funzioni lineari, tranne che per questi box di sostituzione. È dimostrato che, se un algoritmo non ha funzioni non lineari, il suo cifrato è facilmente recuperabile a partire da attacchi a testo noto, cioè è possibile ricavare la chiave di cifratura a partire dai testi cifrato e in chiaro, fatto molto pericoloso.

Cifratura e decifratura

Come detto, il DES è un algoritmo simmetrico, cioè la stessa implementazione può essere usata sia per cifrare che per decifrare il testo, con l'unica accortezza che le sottochiavi devono essere passate in maniera inversa ai vari step della funzione.

Come detto, soltanto 56 dei 64 bit della chiave vengono effettivamente usati, mentre gli altri 8 bit sono inseriti come bit di ridondanza, per verificare che le chiavi siano correttamente trasmesse. Ad oggi, in certe condizioni, si può fare una ricerca bruta (cioè, provando tutte le chiavi disponibili) in uno spazio di chiavi di dimensione $2^{55}$.

Nel 1993 è stato dimostrato che, con un computer da 1 milione di dollari, si può scandire l'intero spazio delle chiavi del DES in poco meno di 3 ore e mezza, mentre nel 1977 lo stesso calcolatore sarebbe costato 20 milioni di dollari.

Le chiavi scelte possono essere di tre tipi:

• Weak, cioè ad un certo punto le sottochiavi generate diventano composte di soli "1";
• Semi-weak, cioè ad un certo punto le sottochiavi diventano composte da "101010";
• Secure, se non ci sono regole.

Non tutte le implementazioni di DES controllano se la chiave scelta è sicura.

Le permutazioni

Si può dimostrare che le permutazioni iniziali non aumentano la sicurezza dell'algoritmo. Infatti, siccome le permutazioni sono deterministiche, queste possono essere tolte senza conoscere la chiave. Eseguendo la permutazione dal testo cifrato, si ottiene un nuovo testo, che ovviamente non può essere più sicuro di quello non permutato.

Se ne ricava che l'unico motivo per cui esistono le permutazioni iniziale e finale è rendere meno efficiente l'implementazione software rispetto all'implementazione hardware; infatti, in questo ultimo caso, fare una permutazione deterministica dei bit è una cosa estremamente semplice.

Al contrario, le permutazioni che si trovano all'interno dei vari step dell'algoritmo sono sicuramente importanti per amplificare l'effetto valanga: grazie a loro, infatti, si è potuto ridurre il numero di iterazioni da fare per far in modo che la modifica di un bit interessi tutti i bit del cifrato con probabilità $0,5$.

3DES

Dal momento che la chiave del DES, come detto, è troppo corta, considerando il fatto che DES è comunque un algoritmo sicuro, si è deciso di standardizzare un uso diverso del DES: il 3DES. Come il suo predecessore, il 3DES lavora su blocchi di 64 bit, ma utilizza una chiave lunga il doppio,

$k=k_{1}|k_{2}$

La chiave totale è la concatenazione di due chiavi DES, quindi la lunghezza totale della chiave è

$l=56+56=112$ bit

da cui lo spazio delle chiavi ha dimensione

$|K|=2^{112}$

Uso delle chiavi

Le chiavi $k_{1}$ e $k_{2}$ nel 3DES sono usate in cascata:

$E_{k}=E_{k1}D_{k2}E_{k1}$

cioè:

• Si cifra il testo con DES e con la chiave $k_{1}$;
• Si decifra il risultato con $DES^{-1}$ e con la chiave $k_{2}$;
• Si cifra nuovamente con DES e con la chiave $k_{1}$.

Questo utilizzo delle chiavi permette la compatibilità con il DES originale: infatti, basta usare $k_{1}=k_{2}$ ed il risultato è un DES (3 volte più lento) compatibile con l'originale. Questo fatto è possibile grazie proprio alla natura simmetrica del DES.

Usi alternativi delle chiavi

Le chiavi possono essere usate, a seconda dei gusti dell'utente, in varie maniere:

• $E_{k}=E_{k1}E_{k2}$: questo uso ha un difetto, derivante da un attacco denominato meet-in-the-middle, quindi ridurrebbe la sicurezza dell'algoritmo;
• $E_{k}=E_{k1}E_{k2}E_{k1}$: sostituendo $E_{k2}$ a $D_{k2}$ si ottiene un algoritmo altrettanto sicuro (quindi, utilizzabile), ma si perde la compatibilità con il DES originale;
• $E_{k}=E_{k_{1}}D_{k2}E_{k3}$: cioè, aggiungere una chiave $k_{3}$ e portare la lunghezza totale a $56\times 3=168$ bit. Si può fare, ma chi ha standardizzato ha deciso che non serviva. Comunque, esistono implementazioni;
• $E_{k}=E_{k1}E_{k1}$: si ottiene un algoritmo due volte più lento, ma la lunghezza della chiave resterebbe identica.

Conclusioni

Il DES è considerato un algoritmo di cifratura sicuro, dal momento che è considerato il protocollo più crittanalizzato e non si sono mai trovati grandi errori che possano far temere una caduta della sua sicurezza. Se non si usano chiavi weak o semi-weak, il migliore attacco possibile è una ricerca esaustiva nello spazio delle chiavi, quindi soltanto governi potenti possono permettersi di decifrare i dati senza chiave.

Nonostante questo, ci sono altri algoritmi, più efficienti, che potrebbero essere tanto sicuri quanto il DES (soltanto il tempo e la crittanalisi ci diranno quanto sono effettivamente sicuri). Infatti, il difetto principale del DES, ad oggi, è la scarsissima efficienza del calcolo in software.

International Data Encryption Algorithm

L'algoritmo IDEA è un algoritmo di cifratura a blocchi, anch'esso a 64 bit, pubblicato nel 1991 e brevettato (brevetto software, non riconosciuto dall'Unione Europea). La lunghezza del blocco è di per sé bassa, dal momento che con 64 bit si possono fare analisi di frequenza serie; la lunghezza della chiave, invece, è di 128 bit, quindi è adatta (ad oggi).

Il vantaggio principale di IDEA, se confrontato con DES, sta nell'efficienza con cui può essere implementato, sia in software che in hardware.

Ad oggi, non esiste alcuna dimostrazione dell'insicurezza di questo algoritmo (nonostante alcune voci), quindi si può ipotizzare che sia ancora sicuro. Tra i software che lo implementano, troviamo PGP ed S/MIME.

Blowfish

Anche blowfish è un algoritmo di cifratura a blocchi di 64 bit, ma con la particolarità di avere una lunghezza di chiave variabile tra i 32 bit (molto pochi) fino a 448 bit. La difficoltà computazionale dell'algoritmo aumenta all'aumentare della lunghezza della chiave, così come la sua sicurezza. Blowfish è stato progettato per essere particolarmente efficiente nelle implementazioni software su processori general-purpose, quindi è molto usato ad oggi. Tra le implementazioni esistenti, annoveriamo:

• OpenSSH
• PGPfone
• ...

L'unico difetto di questo algoritmo è la sua giovinezza, il che vuol dire che non è stato ancora crittanalizzato in maniera approfondita e c'è il rischio che, di qui a qualche anno, la sua sicurezza possa decadere (come per tutti gli algoritmi giovani).

Advanced Ecryption Standard

Anche l'algoritmo AES, come tutti quelli elencati qui, è un algoritmo per la cifratura a blocchi, che però sono di 128 bit. Si basa sull'algoritmo di Rijndael, che è libero da brevetti ed è stato pubblicato nel 1991.

L'algoritmo AES nasce come sostituto del DES, ma il processo di standardizzazione è stato ben diverso: se per DES c'è stata una forte spinta da parte degli enti governativi americani, per AES si è trattato di un processo pubblico ed aperto, quindi la probabilità che vi siano delle backdoor è molto più bassa rispetto al DES.

La chiave ha lunghezza variabile e può essere di 128, 192 e 256 bit, da cui derivano le denominazioni AES-128, AES-192 e AES-256. Anche in questo caso, maggiore è la lunghezza della chiave, peggiore sarà l'efficienza computazionale dell'algoritmo; l'efficienza, comunque, è alta sia in software che in hardware.

Nel 2007 sono apparse delle ipotesi di bug per AES, ma può ancora essere considerato un algoritmo sicuro.

Comparazione tra gli algoritmi di cifratura a blocchi

Le prestazioni di un algoritmo sono importanti, soprattutto se consideriamo la possibilità di usare la cifratura in applicazioni come il rendere sicura una rete wireless, dove ad oggi circolano dati ad una velocità di 54 Mbps. Per questo sono stati creati dei test di velocità degli algoritmi. Indicativamente, con un processore Pentium4 a 2.1 GHz si ottiene

• 3DES a 82 Mbps;
• DES a 186 Mbps;
• IDEA a 200 Mbps;
• AES-128 a 520 Mbps;
• Blowfish a 536 Mbps.

Cifratura a flusso

Finora abbiamo visto gli algoritmi di cifratura a blocchi, che hanno una particolarità: sono senza uno stato, cioè il testo cifrato dipende semplicemente dalla chiave e dal testo nel blocco da cifrare. Gli algoritmi di cifratura a flusso sono un particolare tipo di algoritmo di cifratura a blocco, in cui abbiamo dei blocchi molto piccoli (di solito, da 1 bit fino a 8 bit), ma l'algoritmo è detto stateful, cioè viene preso in considerazione uno stato, una condizione dell'algoritmo, dovuto a ciò che è stato cifrato precedentemente. Con un algoritmo di questo tipo, non si può più creare un attacco di tipo probabilistico, perché la stessa sequenza di bit nel messaggio $m$ sarà codificata con due blocchi diversi in $c$.

Ci sono diversi modi di operare per tener conto dello stato.

Algoritmi a flusso sincroni

Come possiamo vedere dal grafico, la chiave $k$ viene usata per generare iterativamente delle sottochiavi $g$ da usare all'interno di una funzione $h$, che di norma è uno $XOR$. In questa maniera, ogni singola sottochiave generata è lunga esattamente come il blocco che viene cifrato, quindi anche i blocchi di testo cifrato e non cifrato corrispondono tra loro. Con questo approccio, siamo lontanissimi dalla perfect forward secrecy.

Per decifrare, si ha lo schema:

La funzione per creare le sottochiavi è sempre la stessa, non deve nemmeno essere cambiata. L'unica cosa che può cambiare è la funzione $h$ che deve essere invertita, anche se, usando lo $XOR$, non si deve invertire proprio nulla.

Questo tipo di algoritmo è adatto ai canali con perdita, perché l'errore non si propaga: lo stato non va a modificare le sottochiavi durante la cifratura, che quindi potranno sempre essere ricalcolate, anche se ci sono errori durante la trasmissione dello stream. Al contrario, però, se si perdono dei blocchi interi di informazione, allora il testo cifrato $c_{i}$ e le sottochiavi $z_{i}$ si sfaseranno, e i dati non saranno più recuperabili. Per questo, se vogliamo trasmettere informazioni cifrate con questo algoritmo, è necessario usare il protocollo TCP, mentre l'UDP non può essere usato, dal momento che non garantisce l'integrità e l'ordine dei dati in arrivo. Quindi, questo tipo di algoritmo è adatto per canali che introducono errori sui bit (che non si propagano), ma è totalmente inadatto per canali che introducono perdite di blocchi di dati.

Le sottochiavi $z_{i}$ sono delle chiavi calcolate attraverso una funzione che le rende pseudorandomiche. Un algoritmo a flusso sincrono non può essere usato per cifrare dati che devono essere accessibili in maniera casuale, come per esempio su un hard disk: infatti, se si volesse leggere il blocco corrispondente alla posizione 100GB, si dovrebbero prima calcolare 100 GB di sottochiavi, il che non è accettabile.

Algoritmi a flusso auto-sincronizzanti

In questo tipo di algoritmi, le sottochiavi $z_{i}$ sono derivate sia dalla chiave originale $k$, sia dai blocchi di testo cifrato in precedenza. Questo fatto rende subito necessario creare un vettore di inizializzazione, o initialization vector IV, casuale. Questo vettore di inizializzazione viene trasmesso in chiaro, e deve essere casuale (random).

La decifratura del testo è simile al caso sincrono: dobbiamo invertire la funzione $h$ e calcolare ancora le sottochiavi $z_{i}$, soltanto che dobbiamo tenere in considerazione anche

• Vettore di inizializzazione
• Testo cifrato

Il vettore di inizializzazione, come detto, deve essere casuale, ma casuale davvero. Iniziare due flussi di dati con lo stesso vettore può essere un grave errore, dal momento che si introduce correlazione tra due flussi.

Questo tipo di algoritmi, gli auto-sincronizzanti, sono protetti dalla perdita di dati: infatti, se ci sono errori sul canale o se vengono persi dei blocchi, allora l'errore andrà ad influire soltanto sul blocco singolo (nel caso di errori) o per pochi blocchi che seguiranno il blocco perduto: il numero di blocchi corrotti dipende dal ritardo $r$ con cui utilizziamo, per creare la sottochiave $z_{i+r}$, il blocco perduto $c_{i}$.

RC4

Un esempio di utilizzo di un algoritmo a flusso auto-sincronizzante è l'RC4, l'algoritmo usato per le reti wireless con cifratura WEP. RC4 permette di usare chiavi lunghe da 1 bit fino a 256 bit, ed è estremamente semplice da implementare (sono 20 righe di codice). Il problema di RC4 è che i primi 256 byte trasmessi mostrano un'alta correlazione tra la chiave ed il testo cifrato, per questo motivo non possono essere utilizzati. In RC4, le sottochiavi $z_{i}$ sono lunghe 8 bit.

L'algoritmo RC4, creato da Ronald Rivest (coautore del protocollo RSA), fu scritto nel 1987 ed il suo codice fu mantenuto segreto fino al 1994, quando apparve su internet. Ad oggi, è protetto da brevetto e non può essere usato liberamente.

Metodi di utilizzo degli algoritmi di cifratura a blocchi

Nel caso in cui il testo da cifrare sia più lungo della dimensione del blocco, per poter usare un algoritmo di cifratura a blocchi, servono delle regole. Ci sono diversi modi di operare, con vantaggi e svantaggi, tuttavia nessuno di questi può garantire l'integrità dei dati o l'autenticazione del mittente, ma soltanto la confidenzialità tra chi cifra e chi decifra, indipendentemente da chi essi siano. Di conseguenza, sarà necessario associare, a questi protocolli, degli algoritmi di MAC per garantire autenticazione ed integrità dei dati.

Electronic Code Book mode

ECB è la modalità di utilizzo dell'algoritmo più semplice in assoluto. Ad un blocco del messaggio $m_{i}$ corrisponde un blocco del testo cifrato $c_{i}$.

Un utilizzo di questo tipo espone ad attacchi non solo passivi (come l'analisi di frequenza), ma anche attivi, come per esempio il man in the middle: chiunque può cambiare il messaggio, oppure rimandarlo successivamente (replay attack), o anche solo modificare l'ordine con cui vengono mandati i blocchi. Si tratta di un protocollo molto semplice, in cui gli errori si propagano solo all'interno del singolo blocco. Meglio non usarlo.

Cipher Block Chaining mode

CBC è il tentativo di inserire un po' di memoria all'interno di un algoritmo a blocchi.

Anche in questo caso, gli errori non si propagano, se non al blocco interessato ed al successivo. Interessante notare come, in presenza dello stesso blocco in posizioni diverse, il testo cifrato non è identico: questo fatto rende il protocollo molto più sicuro dal punto di vista degli attacchi di frequenza.

Se da un lato un algoritmo di questo tipo è molto più sicuro dell'ECB da modificazioni dell'ordine dei blocchi, questi possono sempre essere aggiunti o modificati in una maniera tale da rendere il tutto predicibile. Ovviamente, visto che c'è un vettore di inizializzazione IV, questo dovrà essere casuale e non dovrà essere usato due volte.

Output FeedBack mode

OFB è il punto di congiunzione tra gli algoritmi di cifratura a blocco ed a flusso. Con questo metodo di cifratura, abbiamo tre diversi flussi di dati:

• il messaggio in chiaro, $m_{i}$;
• la chiave generata, $o_{i}$;
• il testo cifrato, $c_{i}$.

Questo tipo di cifratura non propaga gli errori, dal momento che qualsiasi errore nel testo cifrato influenza soltanto il blocco all'interno del quale si trova l'errore.

È da notare il fatto che la chiave generata, cioè il flusso di bit $o_{i}$, può essere calcolato in anticipo, partendo dalla chiave $k$, senza nemmeno conoscere il messaggio che si dovrà poi mandare. Questo stesso flusso, inoltre, può avere la dimensione che si preferisce, da blocchi di un singolo bit a un unico blocco totale.

Un difetto di questo approccio è il fatto che l'algoritmo non è protetto dalla perdita di dati: se manca anche un solo bit tutto il flusso che segue risulta sbagliato. Si noti anche il fatto che non è necessario che la funzione $E$ sia invertibile, infatti si usa sempre in senso diretto.

Questo utilizzo della chiave mostra in maniera chiara perché è importante non usare mai due volte lo stesso vettore di inizializzazione IV: si può impostare l'equazione

$m'\oplus o_{1}\oplus m''\oplus o_{1}=m'\oplus m''\oplus (o_{1}\oplus o_{1})=m'\oplus m''$

cioè, se si usano due volte lo stesso vettore di inizializzazione e la stessa chiave, mettendo il XOR i due testi cifrati si può ottenere lo XOR dei due testi non cifrati: a questo punto, si ha un alto grado di correlazione tra i dati ed i messaggi originali, e un'analisi frequenziale può essere fatta in maniera semplice.

Counter mode

Il CTR è l'ultimo metodo di utilizzo di un algoritmo di cifratura a blocchi che vedremo noi.

Si tratta di una modalità simile all'output feedback, ma lo stato in ingresso allo stadio di cifratura, invece di essere preso dal flusso degli $o_{i}$, è calcolato con l'equazione

$p_{i}=IV+i-1$

dove $i$ è l'indice del blocco in uso, mentre $IV$ è il valore del vettore di inizializzazione. Come per la modalità output feedback, l'algoritmo di decifratura è speculare a quello di cifratura.

Come nel caso output feedback, il flusso di chiave può essere calcolato in maniera asincrona rispetto al testo da cifrare o decifrare, il che è una cosa buona per le applicazioni che hanno bisogno di accedere ai dati in maniera casuale, come per le memorie. Questo protocollo è vulnerabile ad attacchi sia attivi che passivi. Un esempio di attacco attivo:

Esempio: Attacco attivo al protocollo Counter

Alice manda un messaggio a Bob,

$c_{i}=m_{i}\oplus o_{i}$

Trudy conosce il testo in chiaro ed il cifrato $<c_{i},m_{i}>$ che è in grado di mettere in corrispondenza. Allora, Trudy può sostituire del testo

$c_{i}^{\prime }=c_{i}\oplus m_{i}\oplus m_{i}^{\prime }$

In questo caso, Bob riceverà il testo cifrato $c_{i}^{\prime }$, così leggerà il messaggio $m'$, credendo che sia il vero messaggio mandato da Alice. Questo problema può essere risolto con un MAC, ma comunque è una dimostrazione della vulnerabilità di questi semplici protocolli.

Offset Code Book mode

Una modalità di utilizzo degli algoritmi che non analizziamo. Ideata nel 2001, è considerata sicura per quanto riguarda la confidenzialità e la protezione dell'integrità dei dati. È protetto da brevetti software, ma non sono necessarie licenze se il software è open source.

Altri progetti

Altri progetti

Wikipedia

Wikimedia Commons

• Wikipedia contiene informazioni su crittografia simmetrica
• Wikimedia Commons contiene immagini o altri file su crittografia simmetrica

Note