Progettazione di DES e cifrario Lucifer

Nel 1971, Horst Feistel di IBM Research sviluppò un cifrario chiamato Lucifer nell'ambito di un progetto di sicurezza bancaria per Lloyd's of London. Lucifer fu uno dei primi cifrari a blocchi moderni e utilizzava una chiave a 128 bit e blocchi da 128 bit.

Lucifer dimostrò che era possibile costruire un cifrario a blocchi robusto utilizzando la struttura di Feistel: round alternati di sostituzione e permutazione applicati a metà blocco. Fu il diretto precursore di DES.

DES applica 16 round della struttura di Feistel a blocchi da 64 bit. In ogni round, il blocco da 64 bit viene diviso in due metà da 32 bit. La metà destra viene espansa a 48 bit, combinata tramite XOR con una sottochiave da 48 bit, fatta passare attraverso le S-box, permutata e combinata tramite XOR con la metà sinistra.

Le metà vengono poi scambiate e il processo si ripete. Dopo 16 round, una permutazione finale produce il testo cifrato da 64 bit. La decifratura utilizza la stessa struttura, con le sottochiavi in ordine inverso.

DES cifra i dati in blocchi da 64 bit (8 byte). Questa dimensione fissa del blocco era adeguata all'hardware del 1977, ma è diventata un problema di sicurezza. Con una quantità sufficiente di dati, le collisioni previste dal paradosso del compleanno diventano probabili.

Con blocchi da 64 bit, emergono pattern statistici dopo circa 2^32 blocchi (~32GB di dati cifrati con la stessa chiave). Questo attacco Sweet32 ha reso 3DES insicuro per il traffico ad alto volume, come HTTPS.

DES utilizza una chiave da 64 bit, ma 8 bit sono bit di parità usati per il rilevamento degli errori e non per la crittografia. La lunghezza effettiva della chiave è quindi di soli 56 bit.

Ciò significa che esistono solo 2^56 chiavi DES possibili (circa 72 milioni di miliardi). Secondo gli standard del 1977, era considerato sufficiente. Nel 1997 era ormai dimostrabile che un avversario determinato poteva violarlo.

DES inizia con una permutazione iniziale (IP) che riordina i 64 bit del blocco di testo in chiaro e termina con una permutazione finale (IP^-1), che ne è l'inversa esatta. Queste permutazioni non aggiungono alcuna robustezza crittografica.

Furono progettate per garantire efficienza hardware su specifiche architetture di chip degli anni '70, consentendo di caricare più velocemente i bit nei registri. Le analisi moderne confermano che non contribuiscono alla sicurezza.

Le otto S-box (scatole di sostituzione) costituiscono il cuore della non linearità di DES. Ogni S-box accetta 6 bit in ingresso e produce 4 bit in uscita, utilizzando una tabella di ricerca fissa. I 2 bit esterni selezionano la riga e i 4 bit interni selezionano la colonna.

Senza la non linearità fornita dalle S-box, DES sarebbe un cifrario puramente lineare, banalmente attaccabile con l'algebra lineare. La progettazione specifica delle S-box di DES resiste alla crittoanalisi differenziale.

Dopo le S-box, DES applica una permutazione P-box che riordina i 32 bit di output delle S-box. Ciò fornisce diffusione, distribuendo l'output di ogni S-box in modo da influenzare più S-box nel round successivo.

La P-box è stata progettata con cura per massimizzare la diffusione: ogni bit di output di una S-box influenza almeno due S-box diverse nel round successivo, garantendo un rapido effetto valanga.

DES ricava 16 sottochiavi diverse da 48 bit dalla chiave principale da 56 bit, una per ogni round. La schedulazione della chiave inizia applicando una scelta permutata (PC-1) per rimuovere i bit di parità e riordinare i bit della chiave.

I 56 bit vengono divisi in due metà da 28 bit, che a ogni round vengono ruotate a sinistra di 1 o 2 posizioni. Successivamente, una scelta permutata (PC-2) seleziona 48 dei 56 bit per formare la sottochiave di ciascun round.

Durante lo sviluppo di DES, la NSA collaborò con IBM, riducendo la lunghezza della chiave dai 128 bit di Lucifer a 56 bit e modificando la progettazione delle S-box. Ciò alimentò decenni di controversie sulla possibile introduzione di backdoor.

Negli anni Novanta, funzionari della NSA confermarono di aver rafforzato le S-box contro la crittoanalisi differenziale, una tecnica scoperta da IBM nel 1974. La NSA conosceva la crittoanalisi differenziale da anni prima del mondo accademico, il che fa pensare che abbia reso DES più resistente, non più debole.

DES fu adottato come Federal Information Processing Standard 46 nel gennaio 1977, dopo un processo di valutazione competitiva. Divenne il cifrario standard per i dati governativi non classificati e fu ampiamente adottato dal settore bancario e industriale.

La standardizzazione di DES ebbe un'importanza storica: fu il primo algoritmo crittografico disponibile pubblicamente e approvato da un governo. Favorì lo sviluppo di implementazioni hardware e stabilì il modello per i futuri processi di standardizzazione dei cifrari.

DES è un cifrario a blocchi che cifra esattamente 64 bit alla volta. I messaggi reali sono più lunghi, quindi le modalità operative definiscono come applicare il cifrario a più blocchi. Tra le modalità comuni vi sono ECB (cifra ogni blocco in modo indipendente), CBC (esegue lo XOR di ogni blocco con il testo cifrato precedente prima della cifratura), CFB, OFB e CTR.

ECB è la modalità più debole: blocchi di testo in chiaro identici producono blocchi di testo cifrato identici, creando schemi visibili. Le modalità CBC e CTR eliminano questa vulnerabilità e sono preferibili nell'uso pratico di DES e 3DES.

Metta alla prova le Sue conoscenze sui parametri di progettazione di DES.

DES si è evoluto dal cifrario Lucifer di IBM in un cifrario Feistel a 16 round, con blocchi da 64 bit e chiavi effettive da 56 bit. La sua sicurezza deriva dalle 8 S-box non lineari, che forniscono confusione, dalla P-box, che fornisce diffusione, e dai 16 round, che amplificano l'effetto valanga.

Il coinvolgimento della NSA nella progettazione delle S-box fu controverso, ma alla fine migliorò la resistenza alla crittoanalisi differenziale. La chiave da 56 bit di DES, progettata per l'hardware del 1977, si rivelò inadeguata alla fine degli anni Novanta.