La crittografia moderna utilizza ancora operazioni di
sostituzione e trasposizioni combinate tra loro in algoritmi molto complessi. Il
primo fra questi è il DES.
DES
Il DES (Data Encryption Standard) è un cifrario composto sviluppato dall'IBM, modificato dalla National Security Agency (NSA) e adottato dal governo statunitense nel 1977 ufficialmente per la protezione di dati riservati ma non classificati come "segreti militari" o di "stato" e che tuttora è usato da tutte le agenzie federali (fatta eccezione per quegli atti che richiedevano un livello più alto di sicurezza).
Il DES è un codice cifrato a blocchi. La chiave usata per cifrare è un blocco di 64 bit suddivisa in 8 sottoblocchi di 8 bit ciascuno; l'ultimo bit di ogni sottoblocco è di controllo, di conseguenza i bit liberi che costituiscono in pratica la chiave sono 56.
Il testo da cifrare viene suddiviso in blocchi di 64 bit ciascuno e vengono cifrati uno dopo l'altro in successione con uguale procedimento.
Se un blocco non raggiunge la lunghezza desiderata di 64 bit si utilizza un procedimento detto "pad", che può essere implementato in diversi modi: un metodo aggiunge zeri fino alla lunghezza stabilita mentre un altro, se i dati sono binari, integra il blocco con bit che sono l'opposto degli ultimi bit del messaggio. Nel caso di dati ASCII si usano invece byte generati in modo casuale specificando nell'ultimo byte il carattere ASCII corrispondente al numero di byte aggiunti. Infine un'ultima tecnica, in parte equivalente alla precedente, usa sempre bit casuali ma fornisce, negli ultimi tre bit, il numero di byte originali, cioè quelli che costituiscono il messaggio senza riempimento
Durante la cifratura un blocco di testo normale viene per prima cosa trasposto, cioè, come già ampiamente spiegato in precedenza, cambia posizione con un altro. Poi il blocco di 64 bit viene diviso in una metà destra e una metà sinistra di 32 bit. A questo punto vengono applicati 16 passi tramite una funzione che opera delle trasposizioni e delle sostituzioni ad ogni metà mediante delle sottochiavi diverse per ogni passaggio e ricavate dalla chiave originale.
Durante ogni passo l'output della metà sinistra diventa l'input della destra e viceversa. Dopo il completamento di tutti i 16 passi dell'algoritmo i due sottoblocchi vengono riuniti e sul risultato viene effettuata una sostituzione per invertire la trasposizione iniziale.
L'orgoritmo di ogni passo è quindi ricorsivo, cioè utilizza i risultati del passo precedente. Vediamolo in dettaglio le operazioni compiute in ogni passo:
Indichiamo con
- T(i) il risultato del i-esimo passo
- S(i) il semiblocco sinistro
- D(i) il semiblocco destro
- K(i) la sottochiave di ogni passaggio
avremo che:
- T(i)=S(i)D(i)
- S(i)=D(i-1)
- D(i)=S(i-1) XOR f[D(i-1),K(i)]
L'uscita di destra è quindi costituita da un'operazione di OR esclusivo (XOR) bit per bit dell'ingresso di sinistra e di una funzione dell'ingresso di destra e la chiave K(i) per questo blocco. Vediamo come opera la funzione "f":
- il blocco D(i-1) viene espanso da 32 bit a 48 con un modulo di espansione E. Indichiamo il blocco espanso con E[D(i-1)];
- si calcola E[D(i-1)] XOR K(i);
- il risultato precedente viene spezzato in 8 blocchi di 6 bit ciascuno: B(1),B(2)...B(8) contenenti rispettivamente i bit 1-6, 7-12, 13-18 ecc...
- ciascun blocchetto B(i) viene usato come ingresso ad una funzione Z che restituisce stringhe di 4 bit indicate Z[B(i)]. La funzione Z opera in questo modo: preleva da ogni matrice fissata S-box (Substitution Box) i 4 bit del nuovo blocchetto S(i)=Z[B(i)] posizionati in base alle righe e colonne specificate dai 6 bit del corrispondente B(i);
- una volta concatenati gli 8 blocchetti S(1), S(2)...S(8) verranno scambiati di posto ottenendo alla fine P[S(1),..S(8)]=f [D(i-1), K(i)].
In precedenza abbiamo più volte parlato di sottochiavi k(i) ricavate dalla chiave originale, ed è giunto il momento di capire come funziona tutto ciò.
Come detto la chiave è una stringa di 64 bit con 8 bit di controllo che vengono ignorati durante la cifratura/decifratura. Essa viene spezzata in due blocchi di 28 bit, supponiamo di chiamarli, usando la simbologia di prima, S(0) e D(0). Dopodiché per 16 volte i semiblocchi vengono spostati a sinistra ottenendo s(1), D(1), S(2), D(2) ... S(16), D(16). Quindi al primo passo l'algoritmo utilizzerà la sottochiave K(1)=P[S(1)D(1)] dove P al solito indica una permutazione (lo scambio di posto), al secondo K(2)=P[S(2)D(2)] e al 16° round K(16)=P[S(16)D(16)]. In questo modo tutte le operazioni effettuate producono sottochiavi K(i) di 48 bit.
Per la decifratura il procedimento è lo stesso, l'unica differenza sta nelle sottochiavi utilizzate in ogni passo: al 1° passo verrà utilizzata K(16)=P[L(16)L(16)], al secondo K(15)=P[L(15)L(15)] e cosi via.
Avremo quindi:
T(i)=S(i)D(i)
D(i-1)=S(i)
S(i-1)=D(i) XOR f[S(i),K(i)]
Dove T(i) in questo caso indica il testo cifrato. Queste sono le fasi principali del processo eseguito dal DES per la cifratura e la decifratura del messaggio. Chi volesse conoscere i particolari dei due processi per implementarli in un software, può scaricare dall'indirizzo ftp://ftp.ox.ac.uk/pub/crypto/DES/des-how-to.txt il file (in lingua inglese) che contiene una descrizione passo-passo dell'algoritmo e le matrici S-box nominate sopra.
La sconfitta del DES
Il 17 luglio 1998 la Electronic Frontier Foundation diffonde un comunicato stampa con il quale annuncia la definitiva sconfitta del DES. Per dimostrare i gravi rischi di sicurezza a cui si sottopone chi utilizza il DES, la EFF costruisce il primo apparecchio Hardware non coperto dal segreto di stato per decodificare i messaggi crittografati utilizzando il Data Encryption Standard. In meno di un anno viene costruito un calcolatore costato 250.000 dollari che in meno di sessanta ore era capace di forzare un messaggio cifrato con DES. Tutte le specifiche utilizzate sono documentate in un libro realizzato dalla EFF dal titolo "Cracking DES: Secrets of Encryption Research, Wiretap Politics, and Chip Design". Con le informazioni contenute nel libro è possibile realizzabile, a partire da un normale personal computer domestico, il così detto DES cracker. Il testo è disponibile unicamente in versione cartacea perché secondo le leggi USA in materia di esportazioni è reato pubblicare e quindi esportare questo tipo di informazioni su Internet.
