Criptografia a chiave simmetrica

Bibliografia:
Computer Networking. Autori: James F. Kurose (University of Massachusetts, Amherst) Keith W. Ross (Polytechnic Institute of NYU).

Cifrari a Blocchi

La criptografia a chiave simmetrica, anche detta a chiave segreta condivisa, è divisa in due classi di cifrari: a blocchi e a flusso. Il metodo del cifrario a flusso è ampiamente usato nelle reti wireless, mentre nelle reti cablate si usa il cifrario a blocchi. I principali protocolli di Internet che usano questo cifrario sono il PGP, per scambiare e-mail in modo sicuro, SSL, per rendere sicure le connessioni TCP e IPsec per rendere sicuro il livello rete.

In un cifrario a blocchi, il messaggio da criptare viene elaborato in blocchi di k bit. Ad esempio, se k = 64, allora il messaggio viene suddiviso in blocchi di lunghezza 64 bit, ed ogni blocco viene criptato indipendentemente dagli altri. Per codificare un blocco, il cifrario usa una corrispondenza biunivoca che viene stabilita tra i blocchi di k bit del testo in chiaro e i blocchi di k bit del testo cifrato. Ad esempio, se k=3, il cifrario stabilisce una corrispondenza tra 3 bit del testo in chiaro e 3 bit del testo cifrato. La tabella seguente mostra un esempio:

input	output		input	output
000	110		100	011
001	111		101	010
010	101		110	000
011	100		111	001

Notare che esiste una corrispondenza biunivoca tra i codici di input e i codici di output, cioè per ogni codice di output esiste uno ed un solo codice di input e, viceversa, per ogni codice di input esiste uno ed un solo codice di output. Il cifrario viene usato per codificare blocchi di 3 bit del testo in chiaro. Si verifichi che il testo in chiaro 010110001111 viene criptato in 101000111001.

La tabella di corrispondenza mostrata è solo un esempio. Gli 8 codici che si possono formare con 3 bit, possono essere permutati in 8!=40320 modi, ottenendo, quindi, 40320 possibili tabelle di codifica. Una tabella di codifica costituisce la chiave con cui due interlocutori possono criptare e decriptare i messaggi che si scambiano.

L'attacco di forza bruta a questo cifrario consiste nel tentare di decriptare il testo cifrato usando tutte le possibili tabelle di corrispondenza. Con il cifrario di esempio, con k=3, non è richiesto molto tempo per provare le 40320 possibili tabelle di codifica. Per contrastare l'attacco di forza bruta, il cifrario a blocchi usa blocchi di lunghezza maggiore, con k=64 o oltre. Notare che il numero di possibili tabelle di codifica o, equivalentemente, il numero di possibili chiavi è 2^k!, che è un numero molto grande anche per piccoli valori di k.

Sembrerebbe che, anche con piccoli valori di k, si possono creare cifrari a blocchi difficilmente violabili. Purtroppo, per creare un cifrario con blocchi di 64 bit, i due interlocutori devono memorizzare una tabella di corrispondenza con 2⁶⁴ righe: un numero improponibile! Inoltre se volessero cambiare la chiave, dovrebbero rigenerare la tabella di codifica. Di conseguenza, la tabella completa di un cifrario a blocchi è un'idea da scartare.

Un cifrario a blocchi, anzichè usare una tabella di codifica completa, usa funzioni per calcolare le permutazioni della tabella. La funzione scompone un blocco di 64 bit in 8 pezzi di 8 bit. Ogni pezzo di 8 bit è elaborato da un tabella che a ogni gruppo di 8 bit fa corrispondere un altro gruppo di 8 bit. Questa volta la tabella ha dimensioni ragionevoli. Ad esempio il primo gruppo di 8 bit è elaborato con la tabella T1. Si ottengono, quindi, 8 pezzi in output dalle 8 tabelle, che vengono riassemblati per ottenere un blocco da 64 bit. Le posizioni dei 64 bit nel blocco vengono rimescolate (permutate) per ottenere un output a 64 bit. Questa configurazione viene riportata in input per ripetere le stesse operazioni. Dopo n cicli, la funzione fornisce il blocco di 64 bit del testo cifrato. Lo scopo di ripetere ciclicamente le operazioni è quello di fare in modo che ogni bit di ingresso influenzi la maggior parte (se non tutti) dei bit di uscita finali. (Se si eseguisse un solo passaggio, un dato bit di ingresso riguarderebbe solo 8 dei 64 bit di uscita). La chiave di questo algoritmo di cifratura a blocchi sarebbe costituita dalle 8 tabelle di permutazione (assumendo che la funzione di rimescolamento sia di pubblico dominio).

Sono stati proposti molti cifrari a blocchi, tra questi il DES (Data Encryption Standard), 3DES, ed AES (Advanced Encryption Standard). Ognuno di questi standard usa funzioni, anzichè le tabelle Ti predeterminate mostrate nell'esempio precedente, molto complesse e caratteristiche di ogni cifrario. Ogni algoritmo usa una stringa di bit come chiave. Ad esempio il DES usa blocchi di 64 bit con una chiave di 56 bit. AES usa blocchi di 128 bit e può operare con chiavi di lunghezza 128, 192, o 256 bit. Per un algoritmo, una chiave determina una tabella di codifica e le permutazioni interne. L'attacco di forza bruta per questi cifrari consiste nell'applicare l'algoritmo di decriptografia provando, in successione, tutte le chiavi. Se la chiave è di lunghezza n ci sono 2ⁿ possibili chiavi. Si è stimato che se una macchina prova tutte le 2⁵⁶ chiavi del DES in un secondo, dovrebbe impiegare 149·10¹² anni per scoprire una chiave AES di 128 bit.

Cifrario con blocchi concatenati

Nelle applicazioni di rete, si ha necessità di criptare messaggi molto lunghi. Se a questi messaggi si applica il cifrario a blocchi come descritto, scomponendo semplicemente il messaggio in blocchi di k bit, e criptando indipendentemente ciascun blocco, si corre il rischio di agevolare la scoperta della chiave. Si pensi, ad esempio ad un testo in chiaro, in cui si ripetono alcune parole e, di conseguenza, dopo la suddivisione del testo, si hanno alcuni blocchi uguali. Il cifrario a blocchi produrrebbe blocchi cifrati uguali. Un attaccante, vedendo blocchi cifrati uguali, potrebbe intuire a quale testo in chiaro corrispondono, e potrebbe riuscire a decriptare anche l'intero messaggio.

Per risolvere questo problema, bisogna fare in modo che blocchi di testo in chiaro uguali producano blocchi di testo cifrati diversi. Per conseguire questo risultato, si indichi con m(i) l'i-mo blocco di testo in chiaro, mentre con c(i) si denota l'i-mo blocco cifrato. Per specificare l'algoritmo di criptografia con chiave S, si userà la notazione K_S. L'idea è la seguente: il mittente crea un numero casuale r(i) di k bit per l'i-mo blocco e calcola:
c(i) = K_S(m(i) ⊕ r(i)).
Ovviamente, per ogni blocco il mittente genera un nuovo numero casuale di k bit. Il mittente trasmette c(1), r(1), c(2), r(2), c(3), r(3), ecc. Quando il destinatario riceve c(i) e r(i), può risalire al blocco di testo in chiaro calcolando:
m(i) = K_S(c(i) ⊕ r(i)).
Si può osservare che sebbene r(i) venga trasmesso in chiaro, e quindi può essere intercettato e compreso, un intruso non riesce a risalire al testo in chiaro m(i), perchè non conosce la chiave K_S. Inoltre, se due blocchi in chiaro sono uguali, i corrispondenti blocchi cifrati saranno diversi, se sono diversi i numeri casuali, ciò è vero con elevata probabilità

Per costruire un esempio, si consideri il cifrario a blocchi di 3 bit riportato nella figura precedente. Si scelga il testo in chiaro: 010010010. Se Alice lo cripta direttamente, senza aggiungere la casualità, il testo cifrato risultante sarebbe 101101101. Se Trudy intercetta questo testo cifrato, nota subito che i tre blocchi sono uguali e che tali devono essere i tre blocchi del testo in chiaro. Questa informazione consente all'intruso di applicare un metodo di criptoanalisi. Si supponga, adesso, che Alice generi i blocchi casuali r(1) = 001, r(2) = 111, e r(3) = 100 ed usi la tecnica descritta prima per generare i testi cifrati c(1) = 100, c(2) = 010, e c(3) = 000. Notare che, adesso, i tre blocchi cifrati sono tutti diversi. Alice trasmette c(1), r(1), c(2), e r(2). (Si verifichi che Bob può ottenere il messaggio in chiaro originale usando la chiave condivisa K_S).

Il lettore attento osserverà che l'introduzione della casualità risolve un problema a costo di raddoppiare il volume del traffico trasmesso. Infatti, per ogni bit del testo cifrato, deve spedire anche un bit del numero casuale, raddoppiando l'occupazione di banda. I cifrari a blocchi usano una tecnica denominata Concatenazione dei Blocchi Cifrati (CBC). L'idea base è quella di trasmettere solo un valore casuale insieme al primo messaggio, poi il mittente ed il destinatario usano i blocchi di codifica calcolati al posto dei successivi numeri casuali.

Più esattamente, CBC funziona così:

1. Prima di criptare il messaggio (o il flusso di dati ), il mittente genera una stringa di k bit casuali, chiamata il vettore di inizializzazione (IV). Questo vettore di inizializzazione viene indicato con c(0). Il mittente trasmette l'IV al ricevitore, in chiaro.

2. Per il primo blocco, il mittente calcola m(1) ⊕ c(0), cioè calcola l'OR esclusivo del primo blocco del testo in chiaro con IV. Il risultato viene elaborato attraverso l'algoritmo del cifrario a blocchi per ottenere il corrispondente blocco cifrato; cioè:
   c(1) = K_S(m(1) ⊕ c(0)).
   Il mittente trasmette il blocco cifrato c(1) al ricevitore.

3. Per l'i-mo blocco, il mittente genera l'i-mo blocco cifrato da c(i) = K_S(m(i) ⊕ c(i - 1)).

Riassumendo:

• il ricevitore riesce a risalire al messaggio originale, infatti quando il destinatario riceve c(i), lo decripta con k_S per ottenere s(i) = m(i) ⊕c(i-1); Poichè il ricevitore conosce anche c(i-1), ricava il testo in chiaro del blocco da m(i) = s(i) ⊕c(i-1).

• Anche se due blocchi di testo in chiaro sono identici, i corrispondenti blocchi di testo cifrato sono (con elevata probabilità) diversi.

• Nonostante il mittente trasmetta l'IV in chiaro, un intruso non riuscirà a decriptare i blocchi cifrati, perchè non conosce la chiave segreta S.

• Il mittente trasmette solo un blocco di dati in più, l'IV, che costituisce un aumento trascurabile dell'occupazione di banda, se il messaggio è molto lungo.

Come esempio, usando il cifrario riportato nella tabella in alto, si determini il testo cifrato per i tre blocchi da 3 bit 010010010 e con IV = c(0) = 001. Il mittente usa l'IV per calcolare c(1) = K_S(m(1) ⊕ c(0)) = 100. Il mittente poi calcola c(2) = K_S(m(2)⊕ c(1)) = K_S(010 ⊕ 100) = 000, e c(3) = K_S(m(3) ⊕ c(2)) = K_S(010 ⊕ 000) = 101. Come esercizio, si verifichi che il ricevitore, conoscendo l'IV e K_S può risalire al testo in chiaro.