Crittografia - DES

 :: 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:

1. permutazione iniziale = si permuta il blocco di 64 bit
2. 16 fasi in stile Feistel
3. preoutput = si scambiano la metà di SX e quella di DX
4. permutazione finale = è l'inverso di quella iniziale.

Permutazione iniziale

Scambia di posto i 64 bit del blocco, ed è una funzione invertibile. Infatti, la permutazione finale è l'inverso di quella iniziale.

Fase

La sottochiave è composta da 48 bit, ricavati - vedremo poi - dalla chiave di 56 bit.

Il destino del blocco R è il seguente:

• viene espanso da 32 bit (metà di 64) a 48 bit, e viene messo in XOR con la chiave K.
• quello che esce viene dato in pasto ad una funzione di sostituzione che ottiene, dai 48 bit, ancora 32bit.
• si permuta ancora secondo una tabella.

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.

Funzione di sostituzione

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).

Generazione della chiave

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:

1. la prima copia di mezze chiavi viene sottoposta a scorrimento circolare a sx o dx, di 1 o 2 bit, e viene mandata alla fase successiva
2. la seconda copia viene sottoposta ad una tabella, che la riduce da 56 a 48 bit, e la fa entrare nella funzione di sostituzione

Immagine chiarificatrice

Sito internet con immagini sul funzionamento di DES : http://www.amagri.it/crittologia/crittografia/algoritmi_crittografici/des/analisi_algoritmo.htm

Decrittazione

Come in Feistel, la decrittazione avviene eseguendo le fasi con le chiavi generate al contrario.

Effetto valanga

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.

Numero di fasi

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

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.

• SAC = Strict Avalanche Criterion: se cambio un bit in input, i bit in output devono avere probabilità almeno 1/2 di cambiare
• BIC = Bit Independence Criterion: se cambio 1 bit in input, i bit di output devono cambiare l'uno indipendentemente dall'altro

La chiave deve contribuire anch'essa a soddisfare BIC e SAC.

Le S-Box

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:

• generarle casualmente
• generarle casualmente, ma sottoporle a test
• crearle manualmente
• crearle matematicamente seguendo qualche algoritmo

Modi di utilizzo di DES

Il DES non si usa sempre allo stesso modo, ma sono stati inventati modi diversi per utilizzarlo.

ECB = Electronic CodeBook

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.

CBC = Cipher Block Chaining

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.

CFB = Cipher FeedBack

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.

OFB = Output FeedBack

È 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.

Counter

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:

• Per decifrare un blocco, NON mi serve il blocco precedente. Posso quindi eseguire in parallelo le decifrature di diversi blocchi, sfruttando le CPU parallele etc.
• Se conosco prima il contatore, posso PRECALCOLARE l'output del DES per tot posizioni del contatore, così che quando più tardi mi arriva il blocco, devo solo fare lo XOR
• Posso accedere direttamente al blocco che voglio, senza dover dipendere dalla decrittatura di tutti i blocchi precedenti
• È sicuro quanto gli altri metodi
• È anche più semplice

Il contatore può essere realizzato in qualsiasi modo, purché sia un valore a 64 bit.

Double DES

È 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 2⁵⁵.
E invece no: adesso vedremo che un attacco a forza bruta a Double DES richiede uno sforzo asintotico a 2⁵⁶, che rispetto al 2⁵⁵ del DES normale non giustifica affatto la chiave lunga il doppio.

Attacco meet in the middle

  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ì:

• dato x, calcolo tutte le possibili crittografie usando tutte le 2⁵⁶ chiavi possibili, e le salvo in una tabella
• dato z, calcolo tutte le possibili decrittografie e le salvo in una tabella
• confronto le 2 tabelle per vedere le voci che coincidono
• scopro la password usando un'altra coppia di testo in chiaro / testo cifrato

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 2⁵⁶ chiavi.
Poi, devo provare a decrittare z, anche lui con tutte le 2⁵⁶ 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 * 2⁶⁴ 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.

Torna alla pagina di Crittografia