Alla fine degli anni ‘60, IBM iniziò un progetto di ricerca sulla crittografia simmetrica, diretto da Feistel, che portò allo sviluppo di Lucifer, un algoritmo basato sulla rete di Feistel che operava su blocchi di 64 bit con una chiave di 128 bit.
Nel 1972, il National Bureau of Standards (NBS) emise una richiesta di proposte per un algoritmo di cifratura da adottare come standard per tutte le agenzie governative americane. Tale algoritmo doveva soddisfare dei requisiti rigorosi, e in questa prima “gara” non fu proposto nessun algoritmo soddisfacente. Nel 1975 fu allora indetta una seconda gara, alla quale partecipò anche IBM, inviando una versione modificata di Lucifer, che vinse e fu adottata come Data Encryption Standard (DES).77
Quando il DES fu pubblicato per ricevere commenti dalla comunità, ci furono due critiche, legate alle differenze del DES rispetto a Lucifer:
Per fare queste modifiche, IBM aveva lavorato con dei crittografi che collaboravano con l’NSA, quindi la comunità sospettava che l’NSA avesse intenzionalmente indebolito l’algoritmo, introducendo delle backdoor per facilitare la decifratura dei messaggi senza la conoscenza della chiave.
A causa di questi sospetti, il DES è stato molto analizzato dalla comunità di ricerca crittografica, e tali studi hanno dimostrato che l’algoitmo è molto robusto. In particolare, negli anni ‘90 furono pubblicati i primi attacchi di crittoanalisi differenziale, un nuovo tipo di attacco chosen plaintext, e si scoprì che il DES era molto resistente a questi attacchi (servivano $2^{47}$ chosen plaintext, un numero che in pratica è impossibile ottenere), mentre la versione originale di Lucifer non lo era (bastavano 256 chosen plaintext, dunque l’attacco risultava concretamente fattibile). Perciò, si pensò che già al tempo della progettazione del DES, quasi 20 anni prima, l’NSA conoscesse la crittoanalisi differenziale, e avesse quindi modificato Lucifer proprio per renderlo resistente a essa; siccome molti altri algoritmi di cifratura del tempo erano vulnerabili a questi attacchi, per evitare di renderli noti al pubblico sarebbe stato necessario tenere segreti alcuni criteri progettuali del DES. Tale ipotesi fu sostanzialmente confermata pochi anni dopo, quando uno dei progettisti del DES pubblicò alcuni di questi criteri progettuali.
Nel 1994, l’NBS — ora chiamato National Institute of Standards and Technology (NIST) — riaffermò il DES per l’utilizzo a livello federale per altri 5 anni (ma solo per cifratura di informazioni non confidenziali). Poi, nel 1999, il NIST richiese l’adozione del Triple DES, che rende più difficili gli attacchi a forza bruta triplicando la lunghezza della chiave, poichè lo spazio delle chiavi di 56 bit cominciava a essere troppo piccolo. Infine, nel 2002 DES fu rimpiazzato da un nuovo standard, AES (Advanced Encryption Standard), ma principalmente per motivi di efficienza dell’implementazione, perchè il Triple DES è ancora considerato sicuro, tanto è vero che nel 2005 il NIST ne approvò l’utilizzo fino all’anno 2030.
La struttura dell’algoritmo DES può essere suddivisa in due parti: la rete di Feistel e l’algoritmo di key scheduling, cioè di generazione delle sottochiavi.
La rete di Feistel opera su un blocco di 64 bit, suddivisi in due metà di 32 bit, e prevede 16 round, seguiti, come al solito, da uno scambio finale delle due metà del blocco. In più, DES applica ai bit del blocco una permutazione iniziale (IP, Initial Permutation) prima di mandarli in input alla rete di Feistel. L’output della rete di Feistel (dopo lo scambio finale) è chiamato blocco di pre-output; per ottenere il blocco di output vero e proprio, si applica a esso una permutazione che è l’inversa di quella iniziale.
La chiave data in input all’algoritmo è di 64 bit, ma 8 bit sono usati come bit di parità (per il controllo degli errori nella trasmissione della chiave), quindi la dimensione effettiva della chiave è 56 bit. Da questa, l’algoritmo di key scheduling genera le 16 sottochiavi di 48 bit usate per i 16 round.
Uno dei parametri da specificare quando si implementa una rete di Feistel è la funzione di round $F$. Nel caso del DES, all’*i-*esimo round essa riceve in input i 48 bit della sottochiave $K_i$ e i 32 bit della metà destra $R_{i-1}$ del blocco prodotto al round precedente, e deve produrre un output $F(R_{i-1}, K_i)$ di 32 bit (in modo che l’output possa essere messo in XOR bit a bit con la metà sinistra del blocco, $L_{i-1}$, anch’essa di 32 bit). Tale output viene calcolato nel seguente modo: