DES, la codificazione a chiave segreta

Il 15 maggio 1973 l' NBS (National Bureau of Standards, oggi chiamatoNIST - National Institute of Standards and Technology) ha lanciato una gara nel Federal Register (l'equivalente negli USA della Gazzetta Ufficiale in Italia) per la creazione di un algoritmo di codificazione che rispondesse ai criteri seguenti :

• possedere un alto livello di sicurezza legato ad una chiave di piccole dimensioni che serva da codificazione e da decodificazione
• essere comprensibile
• non dipendere dalla confidenzialità dell'algoritmo
• essere adattabile ed economico
• essere efficace e esportabile

Alla fine del 1974, IBM propone « Lucifer », che, grazie alla NSA (National Security Agency), viene modificato il 23 novembre 1976 per dare il DES (Data Encryption Standard). Il DES è stato finalmente approvato nel 1978 dall'NBS. Il DES fu messo in norma dall'ANSI (American National Standard Institute) con il nome di ANSI X3.92, più conosciuto sotto la denominazione DEA (Data Encryption Algorithm).

Principio del DES

Si tratta di un sistema di codificazione simmetrica per blocchi di 64 bits, di cui 8 bits (un byte) servono da test di parità (per verificare l'integrità della chiave). Ogni bit di parità della chiave (1 ogni 8 bits) serve a testare un dei bits della chiave per parità dispari, cioè ogni bit di parità è sistemato in modo da avere un numero dispari di '1' nel gruppo degli 8 bits al quale appartiene. La chiave possiede quindi una lunghezza « utile » di 5 bits, il che significa che solo 56 bits servono in realtà all'algoritmo.

L'algoritmo consiste nell'effettuare delle combinazioni, delle sostituzioni e delle permutazioni tra il testo da cifrare e la chiave, facendo in modo che le operazioni possano farsi nei due sensi (per la decodificazione). La combinazione tra sostituzioni e permutazioni è detta codice prodotto .

La chiave è codificata a 64 bits e formata da 16 blocchi di 4 bits, generalmente abbreviatik₁ à k₁₆. Dato che « solo » 56 bits servono effettivamente a codificare, possono esisterne 2⁵⁶ (sia 7.2*10¹⁶) chiavi diverse !

L'algoritmo di DES

Le grandi linee dell'algoritmo sono le seguenti :

• Frazionamento del testo in blocchi da 64 bits(8 byte) ;
• Permutazione iniziale dei blocchi ;
• Divisione dei blocchi in due parti: sinistra e destra, detti S e D ;
• Tappe di permutazione e di sostituzione ripetute 16 volte (dette ronde) ;
• Ricollaggio delle parti sinistra e destra poi permutazione iniziale inversa.

Frazionamento del testo

Permutazione iniziale

In un primo tempo, ogni bit di un blocco è sottoposto alla permutazione iniziale, che può essere rappresentata dalla matrice di permutazione iniziale (sigla PI) seguente :

Questa matrice di permutazione indica, percorrendo la matrice da sinistra a destra poi dall'alto in basso, che il 58^esimo bit del blocco del testo da 64 bits si trova in prima posizione, il 50^esimoin seconda posizione e così via.

Scissione in blocchi da 32 bits

Una volta che la permutazione iniziale è realizzata, il blocco di 64 bits è scisso in due blocchi da 32 bits, siglati rispettivamente S e D (per sinistra e destra, con la sigla anglosassone L e R per Left and Right). Si nota S₀ et D₀ lo stato iniziale di questi due blocchi :

E' interessante osservare che S₀ contiene tutti i bits che possiedono una posizione pari nel messaggio iniziale, mentre D₀contiene i bits di posizione dispari.

Ronde

I blocchi S_n e D_n sono sottoposti ad una serie di trasformazioni interattive dette ronde, eplicitate in questo schema, e i cui dettagli vengono forniti più in basso :

Funzione d'espansione

I 32 bits del blocco D₀ sono estesi a 48 bits grazie ad una tabella (matrice) detta tabella d'espansione (sigla E), nella quale i 48 bits sono mischiati e 16 fra loro sono duplicati :

Così, l'ultimo bit di D₀ (cioè il 7^imobit del blocco d'origine) diventa il primo, il primo diventa il secondo, …
In più, i bits 1,4,5,8,9,12,13,16,17,20,21,24,25,28 e 29 di D₀ (rispettivamente 57, 33, 25, l, 59, 35, 27, 3, 6l, 37, 29, 5, 63, 39, 31 e 7 del blocco d'origine) sono duplicati e disseminati nella matrice.

O esclusivo con la chiave

La matrice che risulta dai 48 bits è detta D'₀ oppure E[D₀]. L'algoritmo DES esegue quindi un O esclusivo tra la prima chiave K₁ e E[D₀]. Il risultato di questo O esclusivo è una matrice di 48 bits che chiameremo D₀ per comodità (non si tratta dello stesso D₀ dell'inizio!).

Funzione di sostituzione

D₀ e in seguito scisso in 8 blocchi da 6 bits, sigla D_0i. Ciascuno di questi blocchi passa per delle funzioni di selezione (dette talvotascatole di sostituzione o funzioni di compressione), siglate generalmente S _i.
I primi e gli ultimi bits di ogni D_0i determinano (in codice binario) la linea della funzione di selezione, gli altri bits (rispettivamente2, 3, 4 e 5) determinano la colonna. Dato che la sezione della linea si fa su due bits, vi sono 4 possibilità (0,1,2,3). Dato che la sezione della linea si fa su 4 bit, vi sono 16 possibilità (da 0 a 15). Grazie a questa informazione, la funzione di selezione "seleziona" un valore codificato su 4 bits.

Ecco la prima funzione di sostituzione, rappresentata da una matrice di 4 per 16 :

Sia D₀₁ uguale a 101110. I primi e gli ultimi bits danno 10, cioè 2 in codice binario. I bits 2, 3, 4 e 5 danno 0111, ovvero 7 in binario. Il risultato della funzione di selezione è quindi il valore situato nelle linea n° 2, nella colonna n° 7. Si tratta del valore 11, sia in binario 111.

Ciascuno degli 8 blocchi di 6 bits è passato nella funzione di selezione corrispondente, che da a ognuno 8 valori di 4 bits ciascuno. Ecco le altre funzioni di selezione :

Ogni blocco di 6 bits è poi sostituito con un blocco di 4 bits. Questi bits sono raggrupati per formare un blocco da 32 bits.

Permutazione

Il blocco di 32 bits ottenuto è infine sottoposto ad una permutazione Pdi cui vediamo la tabella :

O esclusivo

L'insieme di questi risultati in uscita da P è sottoposto ad un O esclusivocon S₀ di partenza (come indicato nel primo schema) per dare D1, mentre lo D₀ iniziale da S₁.

iterazione

L'insieme delle tappe precedenti (ronde) e reiterato 16 volte.

Permutazione iniziale inversa

Alla fine delle iterazioni, i due blocchi S₁₆ e D₁₆sono "reincollati, poi sottomessi alla permutazione iniziale inversa :

Il risultato in uscita è un testo codificato a 64 bits!

Generazione delle chiavi

Visto che l'algoritmo di DES presentato qui sopra è pubblico, tutta la sicurezza è basata sulla complessità delle chiavi di codificazione.

L'algoritmo qui sotto mostra come ottenere, partendo da una chiave a 64 bits (composta da 64 caratteri alfanumerici qualunque), 8 chiavi diversificate di 48 bits da utilizzare nell'algoritmo di DES :

In un primo tempo i bits di parità della chiave sono eliminati per ottenere una chiave di una lunghezza utile di 56 bits.

La prima tappa consiste in una permutazione siglata CP-1 con la seguente matrice :

Questa matrice può infatti essere scritta sotto forma di due matrici S_i e D_i (per sinistra e destra) composta ciascuna da 28 bits :

Osserviamo come S₀ e D₀ il risultato di questa prima permutazione.

Questi due blocchi subiscono poi una rotazione verso sinistra, in maniera che i bits in seconda posizione vadano in prima, quelli in terza in seconda,…
I bits in prima posizione passano invece all'ultima.

I due blocchi da 28 bits sono in seguito raggrupati in un blocco da 56 bits. Questo passa da una permutazione, detta CP-2, fornendo un blocco di 48 bits, che rappresenta la chiave K_i.

Alcune iterazioni sull'algoritmo permettono di dare le 16 chiaviK₁ a K₁₆ usate nell'algoritmo di DES.

TDES, un'alternativa al DES

Nel 1990 Eli Biham e Adi Shamir hanno messo a punto la criptanalisi differenziale che ricerca delle COPIE di testi in chiaro e di testi cifrati. Questo metodo funziona fino a un numero di ronde inferiore a 15, e nell'algoritmo qui sopra vi sono 16 ronde.

In ogni caso, anche se in una chiave di 56 bits vi sono molteplici possibilità, numerosi processori permettono di calcolare più di 10⁶ chiavi al secondo, così, se utilizzate parallalelamente su un grande numero di terminali, danno la possibilità ad un grande organismo (uno stato ad esempio) di trovare la chiave corretta…

Una soluzione a breve termine può consistere nell'incatenare tre codificazioni DES attraverso due chiavi da 56 bits (il che equivale ad una chiave di 112 bits). Questo processo è chiamato Triplo DES, sigla TDES (a volte 3DEs o 3-DES).

Il TDES permette di aumentare significativamente la sicurezza del DES, ma ha come inconveniente maggiore di chiedere più risorse per la codificazione e la decodificazione.

Distinguiamo solitamente diversi tipi di codificazione triplo DES :

• DES-EEE3 : 3 codificazioni DES con 3 chiavi differenti ;
• DES-EDE3: una chiave diversa per ognuna delle 3 operazioni DES (codificazione, decodificazione, codificazione) ;
• DES-EEE2 e DES-EDE2: una chiave diversa per la seconda operazione (decodificazione).

nel 1997 il NIST lanciò una nuova consultazione di progetto per l'elaborazione dell'AES(Advanced Encryption Standard), un algoritmo di codificazione destinato a sostituire il DES.

Il sistema di codificazione DES fu reaggiornato ogni 5 anni. Nel 2000 all'ultima versione, dopo un processo di valutazione durato 3 anni, l'algoritmo ideato congiuntamente da due candidati belgi, Vincent Rijmen e Joan Daemen fu scelto come nuovo standard dal NIST. Questo nuovo algoritmo battezzato RIJNDAEL dai suoi inventori, sostituirà da quel momento il DES.

Ulteriori informazioni

• http://csrc.nist.gov/encryption/tkencryption.html - Specifiche degli algoritmi di DES di TDES e dell'AES (site du NIST) ;
• RFC 2420 The PPP Triple-DES Encryption Protocol (3DESE)