Crittografia · 27 dicembre 2007 0

Il DES e gli algoritmi di cifratura a blocchi (1a parte)

Molti usano la crittografia in campo informatico senza sapere da dove essa tragga origine. Ebbene, il viaggio che iniziamo oggi ci porterà ad analizzare quelle che possiamo considerare le sue vere radici: il primo algoritmo che prenderemo in considerazione è visto un po’ come il capostipite degli algoritmi di crittazione, nonché uno dei più anziani ancora in circolazione: il DES, acronimo di Data Encryption Standard. Esaminandolo vedremo anche i principali modi d’uso di un algoritmo a blocchi nonché alcune tra le più diffuse funzioni crittografiche, così da avere un’infarinatura a livello generale che arricchirà il bagaglio culturale di ogni utente di computer alle prime armi. Siccome l’argomento è molto lungo da trattare, ho diviso l’articolo in 2 parti: nella prima, che potete leggere qui di seguito, viene presentato il DES, mostrando come è nato e come è strutturato. La storia del DES inizia nel 1972, quando l’NSA* (la National Security Agency, l’organizzazione di intelligence americana preposta alla sicurezza dei dati governativi) chiese al National Bureau of Standards, NBS, adesso divenuto NIST (National Institute of Standards and Tecnology), di sviluppare un algoritmo di crittazione da adottare come standard per la cifratura dei documenti governativi riservati. Fu indetto un primo bando di concorso, che però vide lo scarto di tutti i codici presentati perché non rispondenti ai criteri stabiliti dall’NSA. Ne fu quindi indetto un secondo: fu allora che IBM presentò, il 17 Marzo 1975, un algoritmo di crittazione denominato DEA (Data Encryption Algorithm), basato su un suo precedente codice, il Lucifer. Il DEA piacque subito perché rispondeva ai suddetti criteri. Però doveva subire ancora qualche lavoro di affinamento. E fu così che IBM lavorò sull’algoritmo fino a presentare la versione che fu alla fine adottata dal Governo Americano nel 1977 con il nome ufficiale di Data Encryption Standard, abbreviato in DES. Nel 1983 fu riconfermato come standard, e così anche nel 1988 e nel 1993. Nel 1999, dopo alcuni tentativi di crack portati a termine nel corso dei precedenti 12 mesi, il Governo Americano decise di adottarne una versione irrobustita denominata Triple-DES, in cui la cifratura si otteneva eseguendo 3 volte il DES con 3 chiavi differenti (per un totale di 168 bit complessivi). Solo nel 2002 il NIST ha selezionato come standard un nuovo algoritmo, il Rijndael, divenuto poi l’Advanced Encryption Standard, abbreviato AES, per pensionare il vecchio DES. Ma dobbiamo arrivare al 2004 affinché una nota decreti l’abbandono ufficiale dell’algoritmo da parte del Governo USA in favore del suo più forte ed efficiente successore: si conclude solo allora la sua onorata carriera ventennale.

Analisi generale del DES Tabella1
Come riportato nella scheda introduttiva visibile in Tabella 1, il DES è un algoritmo di cifratura a blocchi a chiave simmetrica. Spieghiamo questi termini… Un algoritmo di cifratura a blocchi è un algoritmo che tratta i dati in blocchi di dimensioni predefinite: nel caso del DES, ogni ciclo opera su 64 bit di dati. Se la lunghezza del messaggio da cifrare non corrisponde ad un multiplo della lunghezza del blocco, bisogna eseguire un’operazione di padding (o riempimento): bisogna cioè aggiungere dei bit senza significato alla fine del testo da cifrare per far sì che la sua lunghezza diventi modulo lung_blocco (vale a dire che la divisione della lunghezza del testo del messaggio per la lunghezza del blocco che può essere trattato dall’algoritmo deve dare zero). Esempio: se il messaggio è lungo 100 bit, per eseguire il DES bisogna portarne la lunghezza a 128 bit [64*2] aggiungendo 28 bit nulli (128 mod 64 = 0). Un algoritmo a chiave simmetrica, detto anche a chiave privata, è un algoritmo in cui la chiave di cifratura è la stessa della chiave di decifratura. Bisogna fare in modo che la chiave resti il più possibile segreta: non si deve in nessun modo divulgarla pubblicamente, altrimenti tutti quelli che ne entrano in possesso possono decifrare il messaggio cifrato. Tornando al DES fu, come detto, sviluppato partendo dal Lucifer, che adottava una chiave a 256 bit. IBM propose inizialmente per il DES una chiave a 128 bit ma l’NSA prima “suggerì” l’adozione di una chiave a 64 bit e poi fece introdurre una modifica all’algoritmo in modo che venissero in pratica usati solo 56 bit; gli altri 8 bit dovrebbero essere utilizzati per operazioni di controllo della parità ma sono generalmente scartati. Come altri algoritmi a blocchi, il DES non è utilizzabile per lavorare su un testo di lunghezza arbitraria dato che è nato per operare su un blocco di dati di lunghezza prefissata. Bisogna utilizzarlo in una delle cosiddette “modalità operative”, vale a dire un sistema di codifica basato sull’algoritmo in questione.

Le modalità operative del DES
Secondo i documenti ufficiali che segnano le linee guida dello standard DES, le modalità utilizzabili per questo algoritmo sono: Electronic CodeBook (ECB), Cipher Block Chaining (CBC), Cipher FeedBack (CFB), Output FeedBack (OFB). Esistono anche altre modalità molto diffuse, il Vettore di Inizializzazione, VI, e la modalità Counter (CTR), che però non approfondisco in quanto non usate con il DES. Vediamo brevemente le differenze fra di esse (Ci è il blocco di dati cifrato, E l’operazione di cifratura, K è la chiave, Pi il blocco di dati in chiaro, k il numero di blocchi da cifrare):

  • ECB
    E’ questa la modalità di utilizzo più semplice di un algoritmo a blocchi, ma è anche la più insicura! Tecnicamente si tratta di prendere un blocco di dati e di cifrarlo separatamente con la chiave: Ci = E(K, Pi) con i= 1...k Perché è insicura? Perché lo stesso blocco di dati cifrato con la stessa chiave fornirà sempre lo stesso risultato! Quindi, NON va mai utilizzata!
  • CBC
    La modalità CBC (concatenamento dei blocchi) è la più utilizzata. Si tratta di effettuare uno XOR fra il blocco di dati in chiaro da cifrare ed il blocco di dati cifrati precedentemente, in modo da introdurre un fattore di casualità che renda più difficoltosa l’analisi del testo cifrato ed evitando i problemi dell’ECB: Ci = E(K, Pi XOR Ci-1) con i=1..k
  • CFC
    Questa modalità, molto simile alla precedente, trasforma di fatto l’algoritmo a blocchi in uno a flusso (stream cipher) auto-sincronizzante. L’operazione di XOR viene eseguita tra l’attuale blocco di dati in chiaro ed il blocco di dati cifrato precedentemente:
    Ci = E(Ci-1) XOR Pi con i=1..k
    La modalità CFC può essere utilizzata per cifrare/decifrare blocchi di dati da un flusso continuo dove serve bassa latenza, come ad esempio un canale di streaming: questo perché l’algoritmo opera utilizzando un blocco di dati già cifrato (che può perciò essere mantenuto in memoria tramite una cache) e quello in chiaro appena passatogli.
  • OFB
    A differenza delle modalità finora mostrate, l’OFB opera in maniera diversa, non usando mai il messaggio diviso a blocchi ma trasformandolo in un flusso pseudo-casuale di bit denominato keystream, il quale viene poi combinato per cifrare il testo in chiaro. Questa modalità trasforma l’algoritmo a blocchi in un vero e proprio algoritmo a flusso sincronizzato (synchronous stream cipher). L’algoritmo viene inizializzato con un VI, Vettore di Inizializzazione (che può essere un contatore o un valore generato casualmente, l’importante è che non venga mai utilizzato lo stesso VI più di una volta con la stessa chiave, altrimenti si possono avere gli stessi problemi di sicurezza della modalità ECB):
    K0 = VI
    Ki = E(K, Ki-1) con i=1..k
    Ci = Pi XOR Ki

    Questa modalità offre alcuni vantaggi: non c’è bisogno di nessuna operazione di padding (riempimento) perché la keystream è lunga quanto il messaggio stesso, per cui se anche l’ultima parte di esso non riempie tutto un blocco di dati, vengono cifrati esclusivamente i bit esistenti; la decifratura corrisponde esattamente alla cifratura perciò non c’è bisogno di scrivere 2 funzioni differenti per le 2 operazioni.

Analisi strutturale
Figura1 La struttura del DES è molto lineare (come si vede dalla Figura 1): ogni blocco di dati in chiaro (lungo 64 bit) passa attraverso 16 identici cicli del processo di crittazione (denominati “rounds” in inglese). Alla fine si hanno 64 bit di dati cifrati. La Permutazione Iniziale e la Permutazione Finale sono 2 processi inversi (la Permutazione Finale fa esattamente le stesse operazioni di quella Iniziale ma in ordine inverso) che non hanno crittograficamente nessun significato: si pensa che siano stati inseriti per poter caricare e scaricare più facilmente i blocchi dati nell’hardware degli anni ’70 e contemporaneamente per rallentare la velocità del DES se eseguito in software. Il simbolo rosso indica uno XOR, cioè un OR esclusivo. La funzione Feistel (rappresentata dal blocco giallo con la lettera F) rappresenta il cuore del DES: riceve in input metà del blocco di dati, che viene cifrato con parte dei bit della chiave. L’output della funzione viene poi ricombinato con l’altra metà del blocco di dati ancora in chiaro e ne vengono invertite le posizioni prima del ciclo successivo (la metà di destra diventa la metà di sinistra e viceversa). L’ultimo ciclo non inverte le 2 metà, così che i dati abbiano alla fine la stessa posizione di partenza: questa caratteristica della struttura del Feistel rende i processi di cifratura e decifratura molto simili. Ma vediamo in dettaglio le varie strutture interne alla base del DES.

La funzione Feistel
Questa funzione, nota anche come Rete di Feistel, prende il nome dall’omonimo crittografo che lavorava in IBM e che aveva inventato questo algoritmo come cifrario a sé stante. La prima utilizzazione della funzione di Feistel si ebbe nel Lucifer, il progenitore del DES. Generalizzando, la funzione Feistel opera nel seguente modo: prende un blocco di dati ed una chiave come input; effettua delle operazioni di riordinamento dei bit (chiamate Permutation Boxes o P-Boxes), applica delle semplici funzioni non lineari di sostituzione dei bit (indicate come Substitution Boxes o S-Boxes) e mescola linearmente i bit con operazioni di XOR. Alla fine del ciclo si ottiene il dato cifrato in output. La particolarità della rete di Feistel sta nel fatto che le funzioni di cifratura e decifratura sono spesso molto simili, se non proprio identiche: in questo ultimo caso, la funzione può essere usata anche per decifrare il messaggio, utilizzandolo come input: si otterrà come output il testo in chiaro. La funzione Feistel del DES esegue 4 operazioni (vedi figura 2):

  • Espansione: Figura2
    viene preso metà blocco dei dati da elaborare (32 bit), che viene poi espanso a 48 bit effettuando delle semplici operazioni di duplicazione dei suoi bit;
  • Mescolamento:
    l’output dell’operazione di espansione viene combinato con una sotto-chiave di 48 bit (ottenuta mediante un procedimento denominato key-schedule, gestione della chiave, descritto più avanti e che fornisce 16 sotto-chiavi diverse, una per ogni ciclo del DES), utilizzando una semplice operazione di OR esclusivo (XOR);
  • Sostituzione:
    dopo il mescolamento con la sotto-chiave, il blocco viene diviso in 8 porzioni di 6 bit ciascuna e poi processato da 8 S-Boxes (indicate con Sx in figura). Ogni S-box sostituisce i 6 bit in ingresso con 4 bit scelti arbitrariamente da una tabella di sostituzione. Senza l’operazione di sostituzione la funzione Feistel sarebbe lineare e quindi facilmente violabile.
  • Permutazione:
    l’ultima parte della funzione ricostruisce il blocco di dati riassemblando i bit ricevuti come output dalle S-Boxes.

Il key-schedule
Figura3Il key-schedule è un algoritmo che genera le sotto-chiavi a partire dalla chiave primaria (vedi figura 3). Dei 64 bit originali ne vengono selezionati solo 56 tramite la funzione S.P. 1 (Scelta Permutata 1); i restanti 8 bit vengono scartati (quasi sempre) o utilizzati come bit di controllo parità. I 56 bit vengono poi divisi in 2 parti di 28 bit ciascuna, ognuna delle quali viene poi trattata in maniera separata dall’algoritmo. Durante i 16 cicli, il key-schedule ruota, a seconda del ciclo, entrambe le metà così generate di 1 o 2 bit verso sinistra (i segni <<< in rosso nello schema) e poi seleziona con la funzione S.P. 2 (Scelta Permutata 2) i 48 bit da fornire come sotto-chiave alla funzione Feistel: 24 bit sono prelevati dalla pipeline di sinistra e 24 bit da quella di destra. Grazie alla rotazione, ogni sotto-chiave è formata da una diversa combinazione di bit (ogni bit è usato in 14 sotto-chiavi su 16).
In caso di decrittazione, il key-schedule genera le sotto-chiavi in ordine inverso e ruotando i bit verso destra.

Termino qui la prima parte di questo lungo articolo dedicato al DES. Nella seconda ed ultima parte affronteremo le dicerie sull’interferenza dell’NSA nello sviluppo del DES e gli attacchi che hanno mostrato le vulnerabilità di questo algoritmo.

Il DES ed i cifrari a blocchi
Il DES ed i cifrari a blocchi
DES_e_cifrari_a_blocchi.pdf
317.9 KiB
4963 Downloads
Dettagli...