:: Crittografia - DES ::
Torna alla pagina di Crittografia
Mancano le IMMAGINI, che renderanno il tutto molto più chiaro (si spera...)
Il DES è un crittosistema basato sulla rete di Feistel. Usa un blocco di 64 bit e una chiave di 56 bit, ed è abbastanza complicato!
In complesso i passaggi sono i seguenti:
Scambia di posto i 64 bit del blocco, ed è una funzione invertibile. Infatti, la permutazione finale è l'inverso di quella iniziale.
La sottochiave è composta da 48 bit, ricavati - vedremo poi - dalla chiave di 56 bit.
Il destino del blocco R è il seguente:
Poi, l'output di questo lavorìo viene XORato con il blocco L.
In pratica, la funzione F della rete di Feistel diviene in DES la sequenza di operazioni qui sopra.
La funzione di sostituzione di cui abbiamo parlato cui sopra è realizzata tramite 8 S-Box.
Ogni S-Box prende in input 6 bit e ne restituisce 4. Ecco perché passa da 48 bit a 32.
Una S-Box è composta da 4 righe e 16 colonne, e non è una funzione lineare.
Il primo e l'ultimo bit dei 6 in ingresso scelgono la riga, i 4 in mezzo scelgono la colonna. La cella della S-Box tramite riga e colonna contiene un numero a 4 bit (0 - 16).
Abbiamo visto che si parte da una chiave a 56 bit, ma la sottochiave è di 48.
In realtà non è proprio così: si prende una chiave di 64 bit, e un bit ogni 8 viene scartato, ottenendone così 56. Questi 56 bit vengono divisi in 2 parti, ciascuna di 28 bit.
Vengono fatte 2 copie di queste mezze chiavi, e ciascuna copia segue una strada diversa:
Sito internet con immagini sul funzionamento di DES : http://www.amagri.it/crittologia/crittografia/algoritmi_crittografici/des/analisi_algoritmo.htm
Come in Feistel, la decrittazione avviene eseguendo le fasi con le chiavi generate al contrario.
Tutto questo macello produce un effetto valanga, che vuol dire che da pochi bit di differenza - nel testo in chiaro o nella chiave - si producono molti bit di differenza nel testo cifrato.
In generale si usano tante fasi perché, anche se una fase è relativamente debole, metterle una dopo l'altra aumenta notevolmente la robustezza dell'intero algoritmo. Nel caso di DES, le 16 fasi sono in grado di vanificare gli attacchi di analisi differenziale con known plain text.
La funzione F serve per aumentare la confusione. Deve essere il meno lineare possibile, sia che usi le S-Box sia che non le usi.
I criteri sono due: SAC e BIC.
La chiave deve contribuire anch'essa a soddisfare BIC e SAC.
Lo scopo di vita delle S-Box è quello di dare un aspetto il più casuale possibile al blocco in input. Se sono grosse, funzionano meglio, ma sono anche molto più difficili da realizzare e da implementare correttamente.
È stato inventato il criterio GA = Guaranteed Avalanche. Una S-Box soddisfa il GA di ordine γ se, per ogni bit in input che cambia, ci sono γ bit in output che cambiano. Un GA con γ tra 2 e 5 è considerato buono per la diffusione.
Ci sono 4 modi per inventare S-Box:
Il DES non si usa sempre allo stesso modo, ma sono stati inventati modi diversi per utilizzarlo.
Si divide il testo in blocchi di 64 bit, e ogni blocco viene DESsificato con la stessa chiave. Se la lunghezza del testo non è multipla di 64 bit, si aggiungono bit per pareggiare.
Questo vuole anche dire che 2 blocchi uguali vengono cifrati allo stesso modo.
L'inpute che viene DESsificato non è il blocco in chiaro, ma è il prodotto dello XOR tra il blocco corrente e il blocco cifrato precedente.
Quando si cifra il primo blocco, ovviamente, non si ha a disposizione un blocco cifrato precedente. Si usa allora un vettore di inizializzazione, detto IV, che deve quindi fare parte della chiave.
Anche qui non uso blocchi di 64 bit di testo in chiaro, ma uso un altro concetto detto segmento composto da un numero s di bit, con s < 64.
Anche qui si parte con un IV di 64 bit, che viene DESsificato e che produce un blocco cifrato di 64 bit.
Di questo blocco cifrato, prendo gli s bit più significativi, e ne faccio lo XOR con i primi s bit del testo in chiaro. Il prodotto di questo XOR è il primo segmento di testo cifrato, lungo quindi s bit.
Questo segmento di testo cifrato viene utilizzato anche per cifrare il segmento successivo. Prendo ancora il vettore IV, elimino gli s bit più significativi e aggiungo in coda gli s bit cifrati (in sostanza compio uno scorrimento a sinistra di s bit, aggiungendo il testo cifrato precedente).
E poi vado avanti: DESsifico il nuovo IV, ottengo 64 bit, di cui i primi s diventano il secondo segmento di testo cifrato, e che andranno anche a nutrire IV per la cifratura del prossimo segmento etc.
In genere si usa s = 8 bit, così ho che 1 segmento corrisponde ad un byte.
È uguale a CFB, con una differenza: gli s bit che userò al posto degli s bit meno significativi di IV nella prossima cifratura, NON sono il prodotto dello XOR tra gli s bit più significativi della DESsificazione precedente e il primo segmento di testo in chiaro, bensì sono direttamente gli s bit più significativi della DESsificazione.
Questo serve per non propagare errori di trasmissione.
Questa è la modalità più interessante. C'è un contatore, che ad ogni passo deve produrre un valore a 64 bit.
QUESTO valore a 64 bit viene DESsificato, e al risultato della DESsificazione si XORano i 64 bit del testo in chiaro.
Questo procedimento ha degli ottimi vantaggi:
Il contatore può essere realizzato in qualsiasi modo, purché sia un valore a 64 bit.
È una modalità di utilizzo di DES, che prevede una doppia cifratura. In pratica:
Ek2(Ek1(M))
che vuol dire che cifro M con la prima chiave, e cifro il cifrato con la seconda chiave.
Il flusso delle informazioni è il seguente:
x -> DES -> y -> DES -> z
Utilizzando 2 chiavi, i bit totali che compongono la chiave devono quindi essere 56 * 2 = 112. Ci si aspetterebbe quindi che la crittanalisi di Double DES sia pesante il doppio rispetto a quella di DES, che si aggira, per la forza bruta, intorno a 255.
E invece no: adesso vedremo che un attacco a forza bruta a Double DES richiede uno sforzo asintotico a 256, che rispetto al 255 del DES normale non giustifica affatto la chiave lunga il doppio.
x -> DES -> y -> DES -> z
Si tratta di un attacco known plaintext, ovvero l'attaccante conosce il testo in chiaro ed anche il suo cifrato corrispondente: x e z in questo schema.
Si procede così:
Quello che si fa in pratica è provare a crittare in tutti i modi possibili il testo in chiaro x di cui dispongo. Crittare in tutti i modi possibili vuol dire provare a crittare x con tutte le 256 chiavi.
Poi, devo provare a decrittare z, anche lui con tutte le 256 chiavi possibili. In pratica, cerco di arrivare ad y sia da sinistra che da destra.
Siccome la chiave di 56 bit è ben minore di 64 * 264 bit, allora ci saranno chiavi diverse che, applicate allo stesso blocco, porteranno allo stesso risultato, sia in cifratura che in decifratura: ecco perché ci sarà più di una coincidenza, e occorre una seconda coppia di testo in chiaro / testo cifrato.