Data Encryption Standard | |
---|---|
La funzione Feistel (funzione F) nel DES | |
Generale | |
Progettisti | IBM |
Prima pubblicazione | 1975 (Standard dal gennaio 1977) |
Derivato da | Lucifer |
Successori | Triple DES, G-DES, DES-X, LOKI89, ICE |
Dettagli | |
Dimensione chiave | 56 bit |
Dimensione blocco | 64 bit |
Struttura | Rete di Feistel |
Numero di passaggi | 16 |
Migliore crittanalisi | |
DES è considerato insicuro perché un attacco a forza bruta è possibile (vedi Deep Crack). Fino al 2004, il migliore attacco di tipo crittanalitico è la crittanalisi lineare, che richiede la conoscenza di 243 simboli in chiaro e un numero di operazioni complessive per l'analisi di 239-43 (Junod, 2001). Supponendo di poter scegliere il testo in chiaro la complessità diminuisce di un fattore quattro. (Knudsen e Mathiassen, 2000). | |
In crittografia il Data Encryption Standard (DES, lett. "Norma per la crittografia dei dati") è un algoritmo di cifratura scelto come standard dal Federal Information Processing Standard (FIPS) per il governo degli Stati Uniti d'America nel 1976 e in seguito diventato di utilizzo internazionale. Si basa su un algoritmo a chiave simmetrica con chiave a 64 bit (ma solo 56 utili poiché 8 sono di controllo).
Questo algoritmo all'inizio ha suscitato molte discussioni per via della sua chiave di cifratura corta e per via di alcune scelte progettuali che erano segretate. Si supponeva che dietro queste scelte vi fosse la National Security Agency (NSA) e l'inserimento di una backdoor. Di conseguenza il DES è stato oggetto di un'intensa analisi di tipo accademico che ha contribuito in modo notevole allo sviluppo delle conoscenze che sono alla base dei moderni algoritmi di cifratura e delle moderne tecniche di crittoanalisi.
Attualmente DES è considerato insicuro per moltissime applicazioni. La sua insicurezza deriva dalla chiave utilizzata per cifrare i messaggi, che è di soli 56 bit. Nel gennaio del 1999 distributed.net ed Electronic Frontier Foundation collaborarono per rompere pubblicamente una chiave di crittazione, e ci riuscirono in 22 ore e 15 minuti. Con le potenze di calcolo disponibili al 2009 si può forzare una chiave DES in poche ore esaminando tutte le possibili combinazioni. L'algoritmo è ritenuto sicuro reiterandolo tre volte nel Triple DES, anche se in teoria così è esposto ad alcuni attacchi. Negli ultimi anni DES è stato sostituito dall'Advanced Encryption Standard (AES)[1] un nuovo algoritmo che elimina molti dei problemi del DES.
In alcuni documenti parlando del DES si utilizza anche la sigla DEA (Data Encryption Algorithm), il nome originale dell'algoritmo così come fu ideato da IBM. Il nome DES si pronuncia (di-i-es, [ˌdiːˌiːˈɛs]) o come una singola sillaba (des).
Storia del DES
[modifica | modifica wikitesto]Le origini del DES risalgono all'inizio degli anni settanta. Nel 1972 l'NBS (National Bureau of Standards), ora chiamato NIST, dopo aver concluso una serie di studi sulla sicurezza informatica per il governo statunitense, stabilì che era necessario individuare un algoritmo di cifratura per documenti senza alcuna classificazione di sicurezza, pubblico e comune in modo da favorire la comunicazione protetta tra le varie organizzazioni governative statunitensi[2]. Dopo essersi consultata con la National Security Agency il 15 maggio 1972 venne presentata la prima richiesta pubblica di uno standard di cifratura definito secondo criteri rigorosi[2][3]. Nessuno degli algoritmi presentati superò i test dell'NSA[2] e quindi il 27 agosto 1974 fu diramato un secondo bando[2]. In quel periodo IBM sottopose come candidato il DEA[2], sviluppato tra il 1973 e il 1974 e basato su un precedente algoritmo denominato Lucifer. Il gruppo di lavoro che a IBM era dedito allo studio degli algoritmi crittografici era capitanato da Horst Feistel: la struttura del Lucifer e del DEA era una novità del ricercatore e da lui prendeva il nome di rete di Feistel. Il gruppo era composto anche da Walter Tuchman, Don Coppersmith, Alan Konheim, Carl Meyer, Mike Matyas, Roy Adler, Edna Grossman, Bill Notz, Lynn Smith e Bryant Tuckerman.
Coinvolgimento dell'NSA
[modifica | modifica wikitesto]Il 17 marzo 1975 il DES proposto fu pubblicato nel Federal Register.[3] Furono richiesti commenti pubblici e l'anno seguente si tennero due congressi pubblici[2] per discutere lo standard proposto. Pervennero critiche da varie parti, anche dai pionieri della crittografia a chiave pubblica Martin Hellman e Whitfield Diffie, che citarono la brevità della lunghezza della chiave e le misteriose S-box come prova di un'interferenza impropria da parte della NSA. Il sospetto che aleggiava era che l'algoritmo fosse stato indebolito di nascosto dall'agenzia di intelligence in modo che loro, ma nessun altro, potesse facilmente leggere i messaggi cifrati[4]. Alan Konheim (uno dei progettisti del DES) rispose
«Noi inviammo le S-box a Washington. Tornarono indietro completamente differenti ...[5].»
Il Select Committee on Intelligence del Senato degli Stati Uniti esaminò le azioni della NSA per determinare se ci fosse stato un coinvolgimento improprio. Nel resoconto delle indagini pubblicato nel 1978, il Comitato scrisse
«Nello sviluppo del DES la NSA convinse l'IBM che era sufficiente una lunghezza ridotta della chiave; assistette indirettamente nello sviluppo delle strutture dell'S-box e certificò che la versione finale dell'algoritmo DES fu, per quanto di loro conoscenza, libero da ogni debolezza statistica o matematica[6].»
A ogni modo, scoprirono che,
«L'NSA non alterò il progetto dell'algoritmo in alcun modo. L'IBM inventò e progettò l'algoritmo, prese tutte le decisioni pertinenti e fu d'accordo nel ritenere che la lunghezza della chiave fosse più che adeguata a tutti gli usi commerciali al quale il DES era destinato[7].»
A un altro membro del gruppo di sviluppo del DES, Walter Tuchman, si attribuisce la seguente citazione:
«Sviluppammo l'algoritmo DES interamente all'interno di IBM con persone dell'IBM. La NSA non cambiò una virgola![8]»
Questo, però, è in contrasto con quanto affermato in una pubblicazione non più top secret dell'NSA sull'evoluzione della crittografia:
«Nel 1973 l'NBS sollecitò le industrie private a sviluppare uno standard di criptazione dei dati (DES). La prima richiesta fu disattesa, così l'NSA iniziò a pensare a un suo algoritmo. In seguito Howard Rosenblum, candidato alla direzione della ricerca e sviluppo, scoprì che Walter Tuchman di IBM stava lavorando su una versione modificata di Lucifer adatta a un uso generico. NSA richiese a Tuchman di unirsi al gruppo di lavoro dell'Agenzia per lavorare insieme sulla sua versione modificata di Lucifer[9].»
Alcuni sospetti su possibili debolezze nascoste nelle S-box furono dissipati nel 1990 in seguito alla pubblicazione da parte di Eli Biham e Adi Shamir della crittanalisi differenziale, un metodo generale per violare i cifrari a blocchi. Le S-box del DES erano molto più resistenti agli attacchi che se fossero state scelte a caso, facendo fortemente sospettare che l'IBM conoscesse questa tecnica già negli anni '70. Quello che accadde veramente fu chiarito in parte nel 1994, quando Don Coppersmith pubblicò i criteri di progetto originali delle S-box[10]. L'IBM aveva scoperto la crittanalisi differenziale negli anni '70 e, dopo aver reso sicuro il DES, gli fu richiesto dalla NSA di mantenere segreta questa tecnica[11]. Come spiega Coppersmith,
«La crittanalisi differenziale può essere una tecnica potentissima usata contro vari schemi e c'era il rischio che se questa informazione fosse diventata di pubblico dominio avrebbe potuto creare un problema di sicurezza nazionale.»
Levy, citando Walter Tuchman, disse:
«Ci chiesero di stampare tutta la nostra documentazione come confidenziale... noi dobbiamo mettere un numero su ciascun documento e chiuderlo in luogo sicuro, perché li considerano documenti confidenziali del governo degli Stati Uniti. Ci dissero di farlo. Così io lo feci.[11]»
L'algoritmo diventa uno standard
[modifica | modifica wikitesto]Nonostante le critiche, il DES fu approvato come standard federale nel novembre del 1976 e pubblicato il 15 gennaio 1977 come FIPS PUB 46, certificato per l'uso su tutti i dati non classificati. È stato in seguito riconfermato come standard nel 1983, 1988 (riesaminato come FIPS-46-1), 1993 (FIPS-46-2) e nuovamente nel 1998 (FIPS-46-3), nel quale si prescrive il "Triple DES" (vedi più avanti). Il 26 maggio 2002, il DES è stato finalmente rimpiazzato dall'AES, l'Advanced Encryption Standard, in seguito a un confronto pubblico. Il 19 maggio 2005, lo standard FIPS 46-3 è stato ufficialmente ritirato, ma il NIST ha approvato l'uso di Triple DES fino all'anno 2030 per informazioni governative sensibili[12].
L'algoritmo è anche descritto nell'ANSI X3.92[13], nel NIST SP 800-67[12] e nell'ISO/IEC 18033-3[14] (come un componente di TDEA).
Un altro attacco teorico, la crittanalisi lineare, è stato pubblicato nel 1994 ma è stato un attacco a forza bruta nel 1998 a dimostrare che il DES può essere praticamente violato e che si rendeva pertanto necessario il rimpiazzo con un altro algoritmo. Questo e altri metodi di crittanalisi saranno discussi con maggiore dettaglio nel corso dell'articolo.
L'introduzione del DES è stato un catalizzatore per ricerche accademiche sulla crittografia, in particolare sui metodi di violazione dei cifrari a blocchi. In accordo con la visione NIST del DES
«Si può affermare che il DES ha permesso un "salto in avanti" agli studi e allo sviluppo di algoritmi di crittazione in campo non militare. Nel 1970 c'erano pochissimi esperti in crittografia, non impiegati in organizzazioni militari o di spionaggio, e pochissimi studi accademici sulla crittografia. Ora ci sono molti esperti in crittografia nelle università, dipartimenti di matematica con programmi molto validi in crittografia e aziende e consulenti specializzati in sicurezza. Una generazione di crittoanalisti ha affilato i denti analizzando e cercando di forzare l'algoritmo DES. Secondo Bruce Schneier,[15] il «DES ha fatto di più per galvanizzare il campo della crittanalisi di qualsiasi altra cosa. Adesso c'era un algoritmo da studiare». Un gran proliferare di pubblicazioni sulla crittografia degli anni '70 e '80 riguardano il DES e il DES è lo standard con cui tutti gli algoritmi a chiavi simmetriche si sono dovuti confrontare[16].»
Cronologia
[modifica | modifica wikitesto]Data | Anno | Evento |
---|---|---|
15 maggio | 1973 | L'NBS pubblica una prima richiesta per un algoritmo standard di cifratura |
27 agosto | 1974 | L'NBS pubblica una seconda richiesta per un algoritmo di cifratura |
17 marzo | 1975 | Il DES viene pubblicato nel Federal Register per avere dei commenti |
agosto | 1976 | Primo workshop sul DES |
settembre | 1976 | Secondo workshop, si discute sui fondamenti matematici del DES |
novembre | 1976 | Il DES è approvato come standard |
15 gennaio | 1977 | Il DES è pubblicato come standard FIPS in FIPS PUB 46 |
1983 | DES è confermato per la prima volta | |
1986 | Videocipher II, propone un sistema di crittazione di segnali TV satellitari analogici basato su DES | |
22 gennaio | 1988 | Il DES è confermato per la seconda volta come FIPS 46-1, in sostituzione di FIPS PUB 46 |
luglio | 1990 | Biham e Shamir (ri) scoprono la crittanalisi differenziale, e la applicano a un sistema di crittazione di tipo DES a 15 fasi. |
1992 | Biham e Shamir pubblicano il primo attacco teorico con complessità minore di uno con forza bruta: crittanalisi differenziale. A ogni modo, richiede l'irrealistico numero di 247 testi in chiaro (Biham e Shamir, 1992). | |
30 dicembre | 1993 | Il DES è confermato per la terza volta come FIPS 46-2 |
1994 | La prima crittanalisi sperimentale del DES è attuata utilizzando la crittanalisi lineare (Matsui, 1994). | |
giugno | 1997 | Il progetto DESCHALL riesce, per la prima volta in pubblico, a violare la crittazione DES di un messaggio[17]. |
luglio | 1998 | Il DES cracker dell'EFF (Deep Crack) viola una chiave DES in 56 ore. |
gennaio | 1999 | Deep Crack e distributed.net in congiunzione violano una chiave DES in 22 ore e 15 minuti. |
25 ottobre | 1999 | Il DES è confermato per la quarta volta come FIPS 46-3, dove si specifica che è raccomandato l'uso del Triple DES, il DES singolo è permesso solo per compatibilità col passato. |
26 novembre | 2001 | L'Advanced Encryption Standard è pubblicato come FIPS 197 |
26 maggio | 2002 | Lo standard AES diventa effettivo |
26 luglio | 2004 | Proposta di ritiro del FIPS 46-3 e altri standard correlati[18] |
19 maggio | 2005 | NIST ritira la FIPS 46-3[19] |
15 marzo | 2007 | Una macchina parallela FPGA denominata COPACOBANA dell'università di Bochum e Kiel in Germania viola una codifica DES in 6,4 giorni con un sistema dal costo di $10.000. |
Algoritmi sostitutivi
[modifica | modifica wikitesto]Alcune considerazioni sulla sicurezza e la relativa lentezza di alcune implementazioni software del DES hanno motivato i ricercatori a proporre un certo numero di progetti di cifrature a blocchi alternativi a cominciare dalla fine degli anni ottanta e i primi anni novanta, per esempio RC5, Blowfish, IDEA, NewDES, SAFER, CAST5 e FEAL. La maggior parte di questi progetti hanno mantenuto la dimensione dei blocchi a 64 bit come nel DES per poterlo sostituire con minori modifiche; inoltre usano chiavi di 64 o 128 bit. In URSS fu introdotto l'algoritmo GOST 28147-89 con un blocco dalla dimensione di 64 bit e una chiave a 256 bit. Questo algoritmo, più tardi, è stato adottato come standard governativo anche dalla Russia.
Il DES stesso può essere adattato e riutilizzato secondo uno schema più sicuro. Molti dei precedenti utilizzatori del DES ora usano il Triple DES (TDES) che è stato analizzato e descritto nelle pubblicazioni ufficiali[12]; questo schema implica l'applicazione dell'algoritmo DES tre volte. Questa operazione può avvenire utilizzando due chiavi diverse (questa variante di TDES è chiamata 2TDES) o tre chiavi diverse (3TDES). Il 3TDES è considerato adeguatamente sicuro[12], anche se abbastanza lento. Un'alternativa computazionalmente meno pesante è rappresentata dal DES-X che aumenta la lunghezza della chiave effettuando un'operazione di XOR con dei bit extra prima e dopo l'applicazione del DES. Il GDES è stata un'altra variante del DES proposta per avere un'alternativa più veloce ma si è dimostrata debole nei confronti degli attacchi mediante crittanalisi differenziale.
Nel 2001, dopo una competizione internazionale, il NIST ha selezionato un nuovo algoritmo di cifratura come sostituto del DES: l'Advanced Encryption Standard. L'algoritmo che è stato selezionato per diventare l'AES è stato proposto dai progettisti col nome di Rijndael. Gli altri finalisti della competizione per l'AES del NIST sono stati l'RC6, il Serpent (secondo classificato), il MARS e il Twofish (terzo classificato).
Descrizione
[modifica | modifica wikitesto]Il DES è l'archetipo della cifratura a blocchi, un algoritmo che prende in ingresso una stringa di lunghezza fissa di testo in chiaro e la trasforma con una serie di operazioni complesse in un'altra stringa di testo cifrato della stessa lunghezza. Nel caso del DES la dimensione del blocco è di 64 bit. Il DES usa inoltre una chiave per modificare la trasformazione in modo che l'operazione di decifratura possa essere effettuata solo conoscendo la chiave stessa. La chiave è lunga 64 bit ma solo 56 di questi sono effettivamente utilizzati dall'algoritmo. Otto bit sono utilizzati solo per il controllo di parità e poi scartati, per questo la lunghezza della chiave effettiva è riportata come di 56 bit.
Come altri algoritmi di cifratura a blocchi, il DES deve essere utilizzato secondo una modalità di cifratura se applicato a messaggi più lunghi di 64 bit. FIPS-81 specifica diverse modalità di utilizzo del DES, inclusa l'autenticazione[20]. Ulteriori considerazioni sull'uso del DES sono presenti in FIPS-74[21].
Struttura generale
[modifica | modifica wikitesto]La struttura generale dell'algoritmo è mostrata nella Figura 1: ci sono sedici fasi identiche di processo dette round, o cicli. Ci sono inoltre una permutazione iniziale e una finale dette IP e FP, che sono tra di loro inverse (IP "disfa" l'azione di FP e viceversa). IP e FP non hanno alcuna importanza per la cifratura ma sono state probabilmente aggiunte per facilitare il caricamento dei blocchi sull'hardware tipico degli anni '70; queste fasi comportano, come effetto collaterale, un rallentamento nelle implementazioni software del DES.
Prima del ciclo principale, il blocco è suddiviso in due metà di 32 bit e processato alternativamente; questo incrocio è detto rete di Feistel. La struttura della rete di Feistel assicura che la cifratura e la decifratura siano processi molto simili - la sola differenza è che le sottochiavi sono applicate nell'ordine inverso nella fase di decifratura. Il resto dell'algoritmo rimane identico. Questo semplifica enormemente l'implementazione, in particolare se effettuata direttamente con un circuito poiché non occorre avere algoritmi separati per cifrare e per decifrare.
Il simbolo denota l'operazione di OR esclusivo (XOR). La funzione Feistel (F-function nello schema) mescola metà del blocco con una parte della chiave. Il risultato della funzione Feistel è poi combinato con l'altra metà del blocco, e le due metà sono scambiate prima del ciclo successivo. Dopo il ciclo finale, le metà non sono scambiate per rendere le fasi di cifratura e decifratura più simili.
La funzione Feistel (F)
[modifica | modifica wikitesto]La funzione Feistel, rappresentata nella Figura 2, opera su mezzo blocco (32 bit) per volta e consiste di quattro passi:
- Espansione: il mezzo blocco di 32 bit è espanso fino a 48 bit utilizzando la permutazione di espansione contraddistinta con E nello schema, che duplica alcuni bit.
- Miscelazione con la chiave: il risultato è combinato con una sottochiave usando un'operazione di XOR. Sedici sottochiavi di 48 bit — una per ogni ciclo — sono derivate dalla chiave principale usando il gestore della chiave (descritto più avanti).
- Sostituzione: dopo la miscelazione con la sottochiave, il blocco viene diviso in otto parti di sei bit prima del processamento con le S-box o substitution box ("scatole di sostituzione"). Ognuna delle otto S-box sostituisce sei bit in input con quattro bit in output mediante una trasformazione non lineare effettuata attraverso una tabella. Le S-box forniscono il cuore della sicurezza del DES — senza di esse, la cifratura sarebbe lineare e quindi facilmente violabile.
- Permutazione: infine, i 32 bit risultanti dalle S-box sono riordinati in base alle permutazioni fisse della P-box o permutation box.
L'alternanza di sostituzioni mediante le S-box, le permutazioni con la P-box e le espansioni forniscono la cosiddetta confusione e diffusione, un concetto identificato da Claude Shannon negli anni quaranta come condizione necessaria per rendere pratica e sicura la cifratura.
Gestore della chiave
[modifica | modifica wikitesto]La figura 3 illustra il gestore della chiave per la cifratura - l'algoritmo che genera le sottochiavi. Inizialmente, vengono selezionati 56 bit della chiave dagli iniziali 64 bit mediante la funzione Permuted Choice 1 (PC-1) - i rimanenti otto bit sono scartati o utilizzati come bit di controllo della parità. I 56 vengono poi suddivisi in due metà di 28 bit; ogni metà è poi trattata separatamente. Nei cicli successivi entrambe le metà vengono fatte slittare verso sinistra di 1 o 2 bit (per i round 1, 2, 9, 16 lo shift, cioè lo slittamento, è di 1 bit, per gli altri è di 2) e quindi vengono scelti 48 bit per la sottochiave mediante la funzione Permuted Choice 2 (PC-2) - 24 bit dalla metà di sinistra e 24 bit da quella di destra. La rotazione (denotata da "<<<" nello schema) significa che in ogni sottochiave è usato un insieme differente di bit; ogni bit è usato più o meno in 14 delle 16 sottochiavi.
Il gestore delle chiavi per la decifratura è simile, deve generare le chiavi nell'ordine inverso quindi la rotazione è verso destra invece che verso sinistra.
Sicurezza e crittanalisi
[modifica | modifica wikitesto]Nonostante siano state pubblicate più informazioni sulla crittanalisi del DES che per ogni altro algoritmo di cifratura a blocchi, il tipo più pratico di attacco a tutt'oggi è quello con forza bruta. Sono conosciute varie proprietà crittanalitiche minori e tre possibili attacchi ma, nonostante la complessità teorica sia minore di quella di un attacco con forza bruta, richiedono una quantità di testo in chiaro conosciuto o scelto a priori tale da renderne difficile l'utilizzo pratico.
Attacco a forza bruta
[modifica | modifica wikitesto]Per ogni algoritmo di cifratura, il metodo più semplice di attacco è quello con forza bruta ovvero provare tutte le possibili chiavi a partire dall'inversione dell'algoritmo di cifratura che è quasi sempre noto. La lunghezza n della chiave determina il numero di chiavi possibili (2^n) e quindi la fattibilità dell'attacco a livello computazionale. Per DES, obiezioni sull'adeguatezza della lunghezza della chiave furono sollevate molto presto, anche prima dell'adozione dello standard e fu proprio la lunghezza della chiave piuttosto che debolezze crittanalitiche a spingere il rimpiazzo dell'algoritmo. Si sa che la NSA incoraggiò o piuttosto persuase l'IBM a ridurre la lunghezza della chiave da 128 bit a 64 per poi giungere a 56 bit; questo particolare è spesso citato come un indizio che la NSA possedesse computer abbastanza potenti da violare chiavi di questa lunghezza già a metà degli anni '70.
A livello teorico, furono avanzate varie proposte per un computer in grado di violare il DES. Nel 1977, Diffie e Hellman proposero una macchina del costo stimato di 20 milioni di dollari in grado di trovare una chiave DES in un solo giorno. Nel 1993 Wiener propose una macchina per la ricerca della chiave, del costo di un milione di dollari, in grado di trovarla in sette ore. La vulnerabilità del DES fu dimostrata praticamente nel 1998 quando fu costruita appositamente la DES-cracker dall'Electronic Frontier Foundation (EFF), un gruppo per la difesa dei diritti civili nel cyberspazio, del costo di circa 250.000 dollari[22]. Fu costruita per dimostrare che il DES era violabile anche in pratica, non solo in teoria:
«Ci sono molte persone che non credono finché non vedono con i propri occhi. Mostrare loro una macchina fisica che può violare il DES in pochi giorni è l'unico modo per convincere qualcuno che veramente non è possibile fidarsi del DES[23].»
La DES-cracker violò con la sola forza bruta una chiave in meno di due giorni di ricerca.
L'unico altro sistema ufficialmente conosciuto per violare la cifratura DES è il sistema COPACOBANA[24] (abbreviazione in inglese di cost-optimized parallel code breaker) costruito da un team delle università di Bochum e Kiel, entrambe in Germania. A differenza del sistema EFF, COPACOBANA è costruito utilizzando unicamente circuiti integrati riconfigurabili normalmente disponibili in commercio. La versione del marzo 2007 era composta da 120 Field programmable gate array (FPGA) di tipo XILINX Spartan3-1000 operanti in parallelo mentre la versione di maggio 2008 è composta da 128 Virtex-4 SX 35 FPGA. L'utilizzo di hardware riconfigurabile permette al sistema di poter essere impiegato anche su altri sistemi di cifratura. Uno degli aspetti più interessanti del sistem COPACOBANA è il fattore costo. Il sistema del 2007 può essere costruito con un budget di € 8.000 con una riduzione, quindi, di 25 volte rispetto al sistema EFF dimostrando l'impressionante e continuo miglioramento dell'hardware. In otto anni si è moltiplicata per trenta la velocità di calcolo. È interessante fare un parallelo con la Legge di Moore che indicherebbe un aumento della potenza di 32 volte, in quanto sono trascorsi circa otto anni fra lo sviluppo dei due sistemi, che implicano cinque raddoppi di potenza di calcolo o cinque dimezzamenti del costo.
Attacchi più rapidi di quello a forza bruta
[modifica | modifica wikitesto]Esistono 3 tipi di attacco conosciuti in grado di violare il DES completo con tutti i 16 cicli di complessità inferiore a quello di forza bruta: la crittanalisi differenziale, la crittanalisi lineare e l'attacco di Davies. Ad ogni modo, questi attacchi sono solo teorici, non attuabili in pratica; questi tipi di attacchi vengono detti a volte certificational weakness.
- La crittanalisi differenziale è stata scoperta alla fine degli anni '80 da Eli Biham e Adi Shamir, anche se era già nota sia ad IBM che alla NSA e tenuta segreta. Per violare tutti i 16 cicli, la crittanalisi differenziale richiede 247 testi in chiaro scelti. Il DES è stato progettato per resistere a questo attacco.
- La crittanalisi lineare è stata scoperta da Mitsuru Matsui ed occorrono 243 testi in chiaro (Matsui, 1993); il metodo è stato implementato (Matsui, 1994) ed è stato il primo esperimento di crittanalisi sul DES documentato. Non ci sono prove che il DES sia stato progettato per resistere a questo tipo di attacco. Una generalizzazione della crittanalisi lineare — crittanalisi lineare multipla - è stata proposta nel 1994 (Kaliski e Robshaw) e poi in seguito migliorata da Biryukov ed altri (2004); la loro analisi suggerisce che possono essere utilizzate approssimazioni lineari multiple per ridurre la quantità di dati per portare avanti l'attacco di un fattore 4 (cioè 241 invece che 243). Una riduzione simile nella complessità dei dati può essere ottenuta con una variante della crittanalisi lineare con testo scelto (Knudsen e Mathiassen, 2000). Junod (2001) eseguì diversi esperimenti per determinare l'attuale complessità della crittanalisi lineare e documentò che era un po' più veloce di quanto predetto, richiedendo un tempo equivalente a 239–241 calcoli del DES.
- L'attacco migliorato di Davies: mentre la crittanalisi lineare e differenziale sono tecniche generali e possono essere applicate anche ad altri algoritmi, l'attacco di Davies è una tecnica specializzata per il DES, proposto per primo da Davies negli anni '80 e migliorato da Biham e Biryukov (1997). La forma più potente dell'attacco richiede 250 testi in chiaro, ha una complessità computazionale di 250 ed il 51% di probabilità di successo.
Esistono anche alcuni attacchi proposti su versioni con un minor numero di cicli di cifratura, per esempio versioni del DES con meno di 16 cicli. Questo tipo di analisi permette di valutare quanti cicli siano necessari per avere una certa sicurezza e che margine di sicurezza ha la versione completa. La crittanalisi differenziale-lineare è stata proposta da Langford ed Hellman nel 1994 e combina l'analisi lineare e differenziale in un singolo attacco. Una versione migliorata dell'attacco può violare una versione del DES con 9 cicli con 215,8 testi in chiaro ed una complessità temporale di 229,2 (Biham ed altri, 2002).
Proprietà crittanalitiche minori
[modifica | modifica wikitesto]Il DES possiede la proprietà complementare cioè che
dove è il complemento bit a bit di . denota la cifratura con la chiave . e indicano rispettivamente il testo in chiaro ed il testo cifrato. La proprietà complementare significa che la complessità di un attacco di forza bruta può essere ridotto di un fattore 2 (o un singolo bit) con il presupposto di un attacco con testo scelto[25].
Il DES ha inoltre le 4 cosiddette chiavi deboli. La cifratura (E) e la decifratura (D) con una chiave debole hanno lo stesso effetto (vedi involuzione):
- o in modo equivalente,
Esistono anche 6 coppie di chiavi semi-deboli. La cifratura con un elemento di una coppia di chiavi semideboli, , ha lo stesso risultato della decifratura con l'altro elemento, :
- o equivalentemente,
È relativamente semplice evitare di usare chiavi deboli o semideboli, le si può escludere esplicitamente o scegliere le chiavi in modo casuale, la probabilità di usare una di queste chiavi è trascurabile[25].
È stato dimostrato che il DES non è un gruppo[26][27] o più precisamente, l'insieme (per tutte le possibili chiavi ) sotto la composizione di funzioni non è un gruppo e neanche si avvicina ad essere un gruppo (Campbell e Wiener, 1992). Questo è stato un problema aperto per qualche tempo e, se fosse stato vero, sarebbe stato possibile violare il DES, e le sue varianti come il Triple DES non ne avrebbero accresciuto la sicurezza.
Note
[modifica | modifica wikitesto]- ^ (EN) Definizione dell'AES su Best Damn Cisco Internetworking Book Period, su Google libri. URL consultato il 14 giugno 2009 (archiviato il 31 luglio 2013).
- ^ a b c d e f (EN) Walter Tuchman, A brief history of the data encryption standard., Internet besieged: countering cyberspace scofflaws, ACM Press/Addison-Wesley Publishing Co. New York, NY, USA, 1997, pp. 275-280.
- ^ a b (EN) Data Encryption Standard (PDF), su nvl.nist.gov. URL consultato il 26 giugno 2006 (archiviato dall'url originale il 23 agosto 2006).
- ^ (EN) RSA Laboratories, Has DES been broken?, su rsa.com. URL consultato il 14 giugno 2009 (archiviato dall'url originale il 31 maggio 2009).
- ^ (EN) Bruce Schneier, Applied Cryptography, 2ª ed., John Wiley & Sons, 1996, pp. 280, ISBN 0-471-12845-7.
- ^ (EN) D.W. Davies, W.L. Price, Security for computer networks, 2ª ed., John Wiley & Sons, 1989.
- ^ (EN) (EN) Robert Sugarman, On foiling computer crime, in IEEE Spectrum, luglio 1979.
- ^ (EN) P. Kinnucan, Data Encryption Gurus: Tuchman and Meyer, in Cryptologia, vol. 2, n. 4, ottobre 1978.
- ^ (EN) Thomas R. Johnson, American Cryptology during the Cold War, 1945-1989. Book III: Retrenchment and Reform, 1972-1980 (PDF), su United States Cryptologic History. URL consultato il 14 giugno 2009 (archiviato il 4 luglio 2009).
- ^ Alan G. Konheim, Computer Security and Cryptography, p. 301, ISBN 978-0-471-94783-7.
- ^ a b (EN) Steven Levy, Crypto: How the Code Rebels Beat the Government Saving Privacy in the Digital Age (Paperback), p. 55.
- ^ a b c d (EN) Recommendation for the Triple Data Encryption Algorithm (TDEA) Block Cipher (PDF), su NIST Special Publication 800-67. URL consultato il 14 giugno 2009 (archiviato il 4 maggio 2012).
- ^ American National Standards Institute, ANSI X3.92-1981 American National Standard, Data Encryption Algorithm
- ^ (EN) Iso.org, ISO/IEC 18033-3:2005 Information technology — Security techniques — Encryption algorithms — Part 3: Block ciphers, su iso.org, 15 ottobre 2008. URL consultato il 14 giugno 2009 (archiviato il 18 settembre 2016).
- ^ (EN) Bruce Schneier, Applied Cryptography, Protocols, Algorithms, and Source Code in C, 3ª ed., New York, John Wiley and Sons, 1996, p. 267.
- ^ (EN) William E. Burr, "Data Encryption Standard", in NIST's anthology "A Century of Excellence in Measurements, Standards, and Technology: A Chronicle of Selected NBS/NIST Publications, 1901–2000, su nvl.nist.gov. URL consultato il 14 giugno 2009 (archiviato dall'url originale il 19 giugno 2009). PDF (PDF), su nvl.nist.gov (archiviato dall'url originale il 23 agosto 2006).
- ^ (EN) DESCHALL - First Public "Crack" of a DES-Encrypted Message, su interhack.net. URL consultato il 14 giugno 2009 (archiviato il 24 giugno 2009).
- ^ (EN) Federal Register, Volume 69, Numero 142 - Proposta ritiro della FIPS 46-3, su edocket.access.gpo.gov. URL consultato il 14 giugno 2009 (archiviato il 14 febbraio 2012).
- ^ (EN) Federal Register, Volume 70, Numero 96 - Ritiro della FIPS 46-3 da parte del NIST (PDF), su csrc.nist.gov. URL consultato il 14 giugno 2009 (archiviato il 25 giugno 2008).
- ^ (EN) NIST - FIPS 81 - DES MODES OF OPERATION, su itl.nist.gov. URL consultato il 14 giugno 2009 (archiviato dall'url originale il 4 giugno 2009).
- ^ (EN) NIST - FIPS 74 - Guidelines for Implementing and Using the NBS Data, su itl.nist.gov. URL consultato il 14 giugno 2009 (archiviato dall'url originale il 3 gennaio 2014).
- ^ (EN) "EFF DES CRACKER" MACHINE BRINGS HONESTY TO CRYPTO DEBATE, su w2.eff.org. URL consultato il 14 giugno 2009 (archiviato dall'url originale il 1º gennaio 2010).
- ^ (EN) Electronic Frontier Foundation, Cracking DES - Secrets of Encryption Research, Wiretap Politics & Chip Design, O'Reilly, luglio 1998, ISBN 978-1-56592-520-5. URL consultato il 14 giugno 2009 (archiviato il 22 maggio 2009).
- ^ (EN) COPACOBANA the Cost-Optimized Parallel COde Breaker, su copacobana.org. URL consultato il 14 giugno 2009 (archiviato dall'url originale il 20 luglio 2009).
- ^ a b Eli Biham, Adi Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer Verlag, 21 maggio 1993, ISBN 0-387-97930-1. URL consultato il 25 giugno 2009 (archiviato il 7 giugno 2009).
- ^ (EN) Is the Data Encryption Standard a Group? (PDF), su people.csail.mit.edu. URL consultato il 26 giugno 2009 (archiviato il 12 luglio 2012).
- ^ Keith W. Campbell, Michael J. Wiener, DES is not a Group, in Advances in Cryptology — CRYPTO' 92 (PDF)[collegamento interrotto], Springer Verlag, 30 giugno 1993, ISBN 978-3-540-57340-1.
Bibliografia
[modifica | modifica wikitesto]- Il Data Encryption Standard (JPG), in MCmicrocomputer, n. 136, Roma, Technimedia, gennaio 1994, pp. 235-238, ISSN 1123-2714 .
- (EN) Eli Biham, Adi Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer Verlag, 21 maggio 1993, ISBN 0-387-97930-1. URL consultato il 25 giugno 2009.
- (EN) Eli Biham, Alex Biryukov, An Improvement of Davies' Attack on DES, in Advances in Cryptology — EUROCRYPT'94[collegamento interrotto], Springer Berlin / Heidelberg, 1995, ISBN 978-3-540-60176-0. URL consultato il 25 giugno 2009.
- (EN) Eli Biham, Orr Dunkelman; Nathan Keller, Enhancing Differential-Linear Cryptanalysis, in Advances in Cryptology — ASIACRYPT 2002[collegamento interrotto], pp. pag.254–266, ISBN 3-540-36178-2. URL consultato il 25 giugno 2009.
- (EN) Alex Biryukov, Christophe De Canniere; Michael Quisquater, On Multiple Linear Approximations (PDF), 2004. URL consultato il 26 giugno 2009.
- (EN) Keith W. Campbell, Michael J. Wiener, DES is not a Group, in Advances in Cryptology — CRYPTO' 92 (PDF)[collegamento interrotto], Springer Verlag, 30 giugno 1993, ISBN 978-3-540-57340-1.
- (EN) Don Coppersmith, The data encryption standard (DES) and its strength against attacks, IBM Journal of Research and Development, 1994. URL consultato il 26 giugno 2009 (archiviato dall'url originale il 4 marzo 2016).
- (EN) Whitfield Diffie, Martin Hellman, Exhaustive Cryptanalysis of the NBS Data Encryption Standard (PDF), IEEE Computer, giugno 1977, pp. pag.74-84, DOI:10.1109/C-M.1977.217750. URL consultato il 26 giugno 2009.
- (EN) John Gilmore, Cracking DES: Secrets of Encryption Research, Wiretap Politics and Chip Design, Electronic Frontier Foundation, 1998, ISBN 1-56592-520-3. URL consultato il 26 giugno 2009.
- (EN) Pascal Junod:, On the Complexity of Matsui's Attack. Selected Areas in Cryptography: 8th Annual International Workshop, SAC 2001, Toronto, Ontario, Canada, Springer-Verlag, agosto 2001, pp. pag.199-211. URL consultato il 26 giugno 2009 (archiviato dall'url originale il 27 maggio 2009).
- (EN) Burton S. Kaliski Jr., Matthew J. B. Robshaw, Linear Cryptanalysis Using Multiple Approximations, in Lecture Notes In Computer Science; Vol. 839 archive - Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology (PDF), ISBN 3-540-58333-5, pp. pag.26–39. URL consultato il 26 giugno 2009.
- (EN) Lars Knudsen, John Erik Mathiassen, A Chosen-Plaintext Linear Attack on DES, in Fast Software Encryption[collegamento interrotto], Springer Berlin / Heidelberg, 2001, pp. pag.262–272, DOI:10.1007/3-540-44706-7_18, ISBN 978-3-540-41728-6. URL consultato il 26 giugno 2009.
- (EN) Susan K. Langford, Martin Hellman, Differential-Linear Cryptanalysis (PDF), 1994, pp. pag.17–25. URL consultato il 26 giugno 2009 (archiviato dall'url originale il 27 maggio 2003).
- (EN) Steven Levy, Crypto: How the Code Rebels Beat the Government Saving Privacy in the Digital Age, Penguin (Non-Classics), 15 gennaio 2002, ISBN 0-14-024432-8. URL consultato il 26 giugno 2009.
- (EN) Mitsuru Matsui, Linear Cryptanalysis Method for DES Cipher, in Workshop on the theory and application of cryptographic techniques on Advances in cryptology (PDF), Springer-Verlag, 1993, pp. pag.386-397, ISBN 3-540-57600-2. URL consultato il 26 giugno 2009.
- (EN) Mitsuru Matsui, The First Experimental Cryptanalysis of the Data Encryption Standard, in Lecture Notes In Computer Science; Vol. 839 archive - Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology (PDF), Springer-Verlag, 1994, pp. pag.1-11, ISBN 978-3-540-58333-2. URL consultato il 26 giugno 2009.
- (EN) National Bureau of Standards, Data Encryption Standard, FIPS-Pub.46. National Bureau of Standards, U.S. Department of Commerce, Washington D.C., January 1977.
Voci correlate
[modifica | modifica wikitesto]- Informazioni aggiuntive su DES
- Crittografia simmetrica
- Skipjack
- Triple DES
- Advanced Encryption Standard
- Meet-in-the-middle
- Lucifer (cifrario)
Altri progetti
[modifica | modifica wikitesto]- Wikibooks contiene testi o manuali sul Data Encryption Standard
- Wikimedia Commons contiene immagini o altri file sul Data Encryption Standard
Collegamenti esterni
[modifica | modifica wikitesto]- DES, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
- (EN) Gustavus J. Simmons, Data Encryption Standard, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
- (EN) Denis Howe, Data Encryption Standard, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL
- codice del DES in diversi linguaggi di programmazione
- (EN) FIPS 46-3: The official document describing the DES standard (PDF), su csrc.nist.gov.
- (EN) FIPS 46-2 rimpiazzato da FIPS 46-3
- (EN) Il progetto: COPACOBANA, a $10,000 DES cracker based on FPGAs by the Universities of Bochum and Kiel, su copacobana.org. URL consultato il 13 dicembre 2008 (archiviato dall'url originale il 20 luglio 2009).
- (EN) Un JavaScript in grado cifrare un testo utilizzando DES e mostrare gli step intermedi, su cs.eku.edu. URL consultato il 9 gennaio 2005 (archiviato dall'url originale il 24 agosto 2004).
- (EN) Collegamenti utili di Helger Lipmaa sul DES, su research.cyber.ee. URL consultato il 13 dicembre 2008 (archiviato dall'url originale il 21 dicembre 2008).
- (EN) Esempio pratico di cifratura DES, su tropsoft.com.
- (EN) Una presentazione passo-passo della metodologia di cifratura e decifratura utilizzando il DES, su dhost.info. URL consultato il 13 dicembre 2008 (archiviato dall'url originale il 21 novembre 2008).
- (EN) Descrizione dell'algoritmo DES di John Savard, su quadibloc.com.
- (EN) Esempio di implementazione DES da Bit slice, su darkside.com.au.
- (EN) RFC4772: Security Implications of Using the Data Encryption Standard (DES) (TXT), su rfc-editor.org.