Pillole di crittografia teorica 2: Cifratura a blocchi DES

Tempo di lettura: 9 minuti
Data pubblicazione: January 23, 2017

La cifratura a blocchi è uno schema di crittografia nel quale ciascun blocco in chiaro viene elaborato in modo indipendente per produrre un blocco di testo cifrato di identiche dimensioni.

Tipi di operazioni nei cifrari a blocchi:

ECB (Electronic Code Book):

è una tecnica utilizzata per l’applicazione di algoritmi di crittografia simmetrica che operano su blocchi di dati di lunghezza fissa B. Se si vuole cifrare un dato di dimensione maggiore di B occorre suddividerlo in blocchi di dimensione B ed eventualmente riempire l’ultimo blocco con tecniche di padding (viene utilizzato, ad esempio, da DES o AES).

CBC (Cipher Block Chain):

l’input dell’algoritmo di crittografia è il risultato dello XOR tra il blocco di testo in chiaro corrente e il blocco di testo cifrato precedente; per ciascun blocco viene utilizzata la stessa chiave. In fase di decifratura, ciascun blocco di testo cifrato passa attraverso l’algoritmo di decrittografia; il risultato subisce uno XOR con il blocco di testo cifrato precedente, per produrre il blocco di testo in chiaro.

CFB (Cipher Feedback)

è stata ideata per convertire idealmente una cifratura a blocchi in una cifratura a flusso. La cifratura a flussi non necessita di eseguire riempimenti e può inoltre operare in tempo reale. Nell’operazione di cifratura, l’input della funzione di crittografia è un registro a scorrimento a 64 bit che inizialmente viene impostato con un vettore di inizializzazione IV (Initialization Vector). Gli s bit più significativi (ovvero quelli più a sinistra) dell’output subiscono uno XOR con il primo segmento di testo in chiaro P1 per produrre la prima unità di testo cifrato C1. Il contenuto del registro di scorrimento viene fatto scorrere a sinistra di s bit, e negli s bit meno significativi (quelli più a destra) del registro viene inserito C1. Il processo viene reiterato fino all’esaurimento di tutte le unità di testo in chiaro.

OFB (Output FeedBack)

Il vantaggio della OFB è che non propaga gli errori di trasmissione dei bit. Il suo svantaggio è che è più vulnerabile a un attacco a modifica del flusso dei messaggi.

CTR (Counter)

In questa modalità viene utilizzato un contatore corrispondente alle dimensioni del blocco di testo in chiaro. Il requisito essenziale è che il suo valore sia differente per ciascun blocco da cifrare; in genere viene inizializzato con un determinato valore e poi incrementato di un’unità per ogni blocco successivo.

Cifratura di Feistel

Feistel suggerisce di eseguire due o più cifrature di base in sequenza in modo che il risultato prodotto sia più resistente. In sostanza si sviluppa una cifratura a blocchi con lunghezza della chiave di k bit e lunghezza di blocco di n bit, consentendo 2k trasformazioni (invece che 2n! nell’ideale a blocchi).

La cifratura di Feistel possiede le proprietà di:

  • Diffusione: la struttura statistica del testo in chiaro viene espansa in modo che ogni cifra del testo cifrato sia influenzata da più cifre del testo in chiaro, cerca quindi di complicare ogni relazione statistica fra il plain text e il cipher text.
  • Confusione: complica la relazione tra le statistiche del testo cifrato e il valore della chiave.

Struttura di Feistel

Tutte le fasi hanno la stessa struttura:

  1. Viene eseguita una sostituzione sulla metà sinistra dei dati. In questa operazione viene applicata la funzione F alla metà destra dei dati e poi si svolge l’operazione di OR esclusivo (XOR) dell’output di tale funzione con la metà sinistra dei dati;
  2. Dopo la sostituzione viene eseguita una permutazione che consiste nello scambio delle due metà dei dati.

I parametri caratterizzanti Feistel sono:

  • Dimensioni del blocco;
  • Dimensioni della chiave;
  • Numero di fasi;
  • Algoritmo di generazione delle sotto-chiavi;
  • Funzione di fase;

Decrittografia di Feistel

Per effettuarla si dà come input si usa il testo cifrato ma si applicano le sottochiavi Ki in ordine inverso (Kn la prima, Kn-1 la seconda, e cosi via).

Algoritmo DES

DES è stato adottato nel 1977 dal National Bureau of Standards, i dati vengono crittografati in blocchi di 64 bit con una chiave di 56 bit.

Cifratura DES

L’elaborazione del testo avviene in diverse fasi:

  1. il testo in chiaro di 64 bit viene sottoposto ad una permutazione iniziale;
  2. viene eseguita la stessa funzione di permutazione e sostituzione per 16 volte;
  3. L’output della sedicesima fase è composto da 64 bit.
  4. La metà di sinistra e destra vengono scambiate per produrre un pre-output che attraversa poi la permutazione inversa della permutazione iniziale per produrre il testo cifrato a 64 bit.

1.Permutazione iniziale

L’input di una tabella è costituito da 64 bit numerati da 1 a 64. Le voci della tabella di permutazione contengono una permutazione dei numeri da 1 a 64. Ciascuna voce della tabella delle permutazioni indica la posizione di un bit di input nell’output.

2.Dettagli di una fase

La metà sinistra e destra di ciascun valore intermedio di 64 bit vengono trattate come due entità distinte da 32 bit. L’elaborazione generale in ogni fase è:

  • Li=Ri-1
  • Ri=Li-1 XOR F(Ri-1,Ki)

La chiave della fase Ki è di 48 bit e l’input R è di 32 bit. L’input R viene espanso a 48 bit usando una tabella che definisce una permutazione più un’espansione che prevede la duplicazione di 16 bit di R. Ai 48 bit risultanti viene applicata con una XOR la chiave Ki. Il risultato di 48 bit attraversa una funzione di sostituzione che produce un output di 32 bit che viene permutato. Nella F(R,K), dopo lo XOR tra i 48 bit di R e K, il risultato passa per le S-box. La sostituzione che avviene è costituita da 8 S-box, ognuna delle quali accetta in input 6 bit e produce un output di 4 bit. L’operazione eseguita è la seguente:

  1. Il primo e ultimo bit dell’input della box Si formano un numero binario di 2 bit che seleziona una della quattro sostituzioni definite dalla tabella per Si.
  2. I 4 bit centrali selezionano una delle sedici colonne.
  3. Il valore decimale della cella identificata dalla riga e dalla colonna viene poi convertito nella sua rappresentazione a 4 bit per produrre l’output.

Ad esempio, con un input 011001, la riga è 01 (converto in decimale->riga 1) e la colonna è 1100 (converto in decimale->colonna 12). Il numero trovato alla 1° riga e 12° colonna della S-box lo converto in binario e ho il mio output.

3.Generazione della chiave

La chiave è da 64 bit, un bit ogni 8 viene ignorato. La chiave viene permutata, e quella risultante di 56 bit viene trattata come 2 quantità di 28 bit, dette C0 e D0. In ciascuna fase C e D sono soggette a uno scorrimento circolare o rotazione a sinistra di 1 o 2 bit. I valori risultanti vengono utilizzati per la fase successiva e come input per la tabella Permuted Choice 2 che funge da input per la funzione F(Ri-1,Ki).

Potenza di DES

Nel luglio 98 la EFF costruì una macchina in grado di rompere il DES in meno di tre giorni. Visto che il prezzo hardware continuava a scendere e la potenza ad aumentare, rese il DES praticamente inutile.

Per chi volesse vedere DES in azione, o non si gli ben chiaro qualche passaggio, consiglio questo sito, che permette di osservare tutte le fasi di una cifrature e capirle in modo ottimale.