# Crittografia/DES

Crittografia
Copertina Tutti i moduli · Sviluppo
    Copertina
Parte I: Introduzione alla Crittografia
* Introduzione alla crittografia
* Storia della crittografia
** Crittografia classica
** Crittografia medievale
** Crittografia dal 1800 alla seconda guerra mondiale
** Crittografia durante la seconda guerra mondiale
** Crittografia contemporanea
** Crittografia nella cultura popolare
** Linea temporale degli eventi importanti
* Concetti fondamentali
** Principio di Kerckhoffs
** Obiettivi della crittografia
** Obiettivi della crittanalisi
** Il ruolo della crittografia nella sicurezza informatica
** Cifrature simmetriche
** Cifrature asimmetriche
** Funzioni Hash
** Distribuzione e autenticazione della chiave
** Difetti e debolezze comuni
Parte II: Progettare cifrari
* Principi base nella progettazione
* Piccoli segreti nascondono segreti più grandi
* algoritmi aperti e il valore del Peer-Review
* Pensa come un crittoanalista
* La matematica che devi conoscere
* La sicurezza informatica non è solo la cifratura
* Un codice non violato non è necessariamente non violabile
Parte III: Violare cifrature
* I principi base nel violare cifrari
* Debolezze
** La proporzionalità della segretezza
*** La lunghezza della chiave
*** Qualità della sorgente casuale
*** Gli effetti del testo in chiaro sul testo cifrato
** Debolezze statistiche
** Implementazioni errate
** Peer-review non adeguato
** Ingegneria sociale e coercizione
* Attacchi
** Attacco di forza bruta
** Analisi della frequenza
** Indice delle coincidenze
** Crittanalisi lineare
** Crittanalisi differenziale
** Attacco incontro nel mezzo
* Come furono violate le cifrature storiche
** Violare i cifrari a trasposizione
** Violare il cifrario di Cesare
** Violare la macchina Enigma
** Violare il cifrario a permutazione
** Violare il cifrario di Vigenère
Parte IV: Usare cifrature
* Applicazioni della crittografia
** Firma elettronica
*** Firma elettronica
*** DSA
** Moneta elettronica
** Voto elettronico
** DRM
** Anonimato
* Cifrature classiche
** Cifrario di Beale
** Cifrari a trasposizione
** Cifrario di Cesare
** Cifrario Atbash
** Cifrario a chiave autocifrante
** Cifrario di Playfair
** Sostituzione polialfabetica
** S-box
** Scytale
** Cifrario a sostituzione
** Cifrario a permutazione
** Cifrario di Vernam
** Cifrario di Vigenère
* Cifrature contemporanee
** Cifrature simmetriche
*** Macchina Enigma
*** One-time pads
*** Data Encryption Standard (DES)
*** Advanced Encryption Standard
** Cifrature asimmetriche
*** Introduzione alla cifratura a chiave pubblica
*** RSA
*** ElGamal
*** Curva ellittica
** Funzioni di hash
*** MD5
*** SHA-1
*** RIPEMD-160
*** Tiger
* Protocolli
** Protocolli di autentificazione
*** Kerberos
** Protocolli per lo scambio chiave
*** Diffie-Hellman
** Comunicazioni sicure
*** SSL, SSH
Parte V: La crittografia e la società
* La natura mutevole dell'uso della crittografia
* Crittografia, governi e leggi
* Aspettative dell'utente normale
* Snake Oil
Parte VI: Miscellanea
* Possibilità future
** Crittografia quantistica
** Miglioramento del calcolo parallelo dei computer
* Glossario dei termini
* Letture addizionali
* Appendice A: background matematico
** Crittografia/Teoria dei numeri
** Crittografia/Teoria dei gruppi
** Crittografia/Complessità computazionale
Modifica il sommario
Il Data Encryption Standard (DES) è 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. Questo algoritmo all'inizio ha suscitato molte discussioni per via della sua chiave di codifica corta e per via di alcune scelte progettuali che erano classificate. Si supponeva che dietro queste scelte vi fosse la National Security Agency (NSA) e l'inserimento di una backdoor. Di conseguenza il DES è stato soggetto a una intensa analisi di tipo accademico che ha prodotto le ricerche che sono alla base dei moderni algoritmi di cifratura e delle moderne tecniche di crittanalisi.
DES è considerato insicuro per moltissime applicazioni. La sua insicurezza deriva dalla chiave utilizza per cifrare i messaggi che è di soli 56 bit. Macchine specializzate sono in grado di esaminare tutte le possibili chiavi e decifrare il messaggio in meno di 24 ore. Dal punto di vista teorico esistono delle tecniche crittanalitiche in grado di forzare il DES ma queste tecniche non sono applicabili praticamente. Per rendere sicuro il DES si sono sviluppate delle evoluzioni come il Triple DES. Questo algoritmo espande la chiave impedendo per il momento un attacco a forza bruta sebbene renda l'algoritmo in teoria vulnerabile a degli attacchi che però non sono attuabili nella pratica. Negli ultimi anni è stato sostituito dall'Advanced Encryption Standard (AES) un nuovo algoritmo che elimina molti dei problemi del DES.
In molti documenti parlando del DES si utilizza anche la sigla DEA (Data Encryption Algorithm). Il nome DES si pronuncia (dee-ee-ess) o come una singola sillaba (des).

## Storia del DES

Le origini del DES risalgono all'inizio degli anni '70. Nel 1972 l'NBS (National Bureau of Standards) dopo aver concluso una serie di studi sulla sicurezza informatica per il governo statunitense definì la necessità dell'individuazione di un algoritmo di cifratura per documenti non classificati sicuro, pubblico e comune in modo da favorire la comunicazione protetta tra le varie organizzazioni governative statunitensi. Dopo essersi consultata con l'NSA il 15 maggio 1972 venne presentata la prima richiesta pubblica di uno standard di cifratura definito secondi criteri rigorosi. Nessuno degli algoritmi presentati ha superato i test dell'NSA e quindi il 27 agosto 1974 un secondo bando è stato diramato. In quel periodo l'IBM sottopose come candidato il suo algoritmo di cifratura sviluppato tra il 1973 e il 1974. Questo algoritmo chiamato Lucifer e sviluppato da un team guidato da Horst Feistel si basava su una nuova tipologia di rete sviluppata dal ricercatore. Il team era formato anche da Walter Tuchman, Don Coppersmith, Alan Konheim, Carl Meyer, Mike Matyas, Roy Adler, Edna Grossman, Bill Notz, Lynn Smith, and Bryant Tuckerman.

### L'NSA modifica l'algoritmo

Il 17 marzo 1975, il DES proposto è stato pubblicati nel Federal Register. Furono richiesti commenti pubblici e l'anno seguente si tennero due workshop pubblici per discutere lo standard proposto. Sono pervenute 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 essi — ma nessun altro — potesse facilmente leggere messaggi cifrati. Alan Konheim (uno dei progettisti del DES) rispose che "Noi inviammo le S-box a Washington. Tornarono indietro ed erano differenti". 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". 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 pertineti 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". 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!".
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 — nel 1994, Don Coppersmith pubblicò i criteri di progetto originali delle S-box. 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. Coppersmith spiega, "questo accadde perché [la crittanalisi differenziale] può essere una tecnica molto potente usata contro vari schemi e c'era il dubbio che se questa informazione fosse di pubblico dominio avrebbe potuto essere un problema di sicurezza nazionale.". Lo stesso Shamir commentò: "Io vorrei dire che, contrariamente a quello che alcune persone credono, non c'è alcuna prova di manomissioni del DES tali che il progetto di base ne risultasse indebolito."
L'altra critica — che la chiave fosse troppo breve — era avvalorata dal fatto che la ragione data dalla NSA per ridurre la lunghezza della chiave da 64 bit a 56 fu che gli altri 8 bit sarebbero potuti servire come bit di parità, argomento alquanto capzioso. È una convinzione comune che la decisione della NSA fosse motivata dal fatto che essi sarebbero stati in grado di sottoporre una chiave di 56 bit a un attacco di forza bruta alcuni anni prima del resto del mondo.

### L'algoritmo diventa uno Standard

Nonostante le critiche, il DES fu approvato come standard federale nel novembre 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. Ancora oggi, a ogni modo, il DES è ancora largamente utilizzato.
Un altro attacco teorico, la crittanalisi lineare, è stato pubblicato nel 1994 ma fu un attacco di forza bruta nel 1998 a dimostrare che il DES potesse essere praticamente attaccato e si rese 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 è stata un catalizzatore per ricerche accademiche sulla crittografia, in particolare sui metodi di violazione dei cifrari a blocchi. Bruce Schneier scrive:
    "Ufficiosamente, la NSA ha definito il DES come uno dei propri più grandi errori. Se avessero saputo che i dettagli sarebbero stati rilasciati pubblicamente in modo che chiunque avrebbe potuto scrivere il software, non sarebbero stati d'accordo. Il DES galvanizzò il campo della crittanalisi come null'altro. Ora c'era un algoritmo da studiare: uno che la NSA dichiarava sicuro."

### Cronologia

| Data | Anno | Evento |
| 15 maggio | 1973 | L'NBS pubblica una prima richiesta per un algoritmo standardi 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 |
| 22 gennaio | 1988 | Il DES è confermato per la seconda volta come FIPS 46-1, in sostituzione di FIPS PUB 46 |
| | 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 2$^{47}$ testi in chiaro (Biham and 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). |
| 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 ch è 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 | Il ritiro del FIPS 46-3 (e altri standard correlati) è proposto nel Federal Register |

## Algoritmi sostitutivi

Alcune considerazioni sulla sicurezza e la relativa lentezza di alcune operazioni del software DES, hanno motivato i ricercatori a proporre un certo numero di progetti di cifrature a blocchi alternativi a cominciare dalla fine degli anni '80 e i primi anni '90; 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.
Il DES stesso può essere adattato e riutilizzato secondo uno schema più sicuro. Molti dei precedenti utilizzatori del DES ora usano il Triple DES (3DES) che è stato analizzato e descritto nelle pubblicazioni ufficiali (vedi FIPS Pub 46-3); questa schema implica l'applicazione del DES tre volte con due chiavi diverse. Il 3DES è considerato adeguatamente sicuro 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 il l'applicazione del DES. 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 internazionele, il NIST ha selezionato un nuovo algoritmo di cifratura: l'Advanced Encryption Standard (AES), come sostituto. L'algoritmo selezionato come AES era stato proposto dai progettisti col nome di Rijndael. Gli altri finalisti della competizione per l'AES del NIST furono RC6, Serpent, MARS e Twofish.

## Descrizione

    Per brevità, la seguente descrizione omette le esatte trasformazioni e permutazioni che specificano l'algoritmo; i dettagli sono disponibili in DES supplementary material.
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 effettiva è riportata come di 56 bit.
Come altri algoritmi di cifratura a blocchi, il DES deve essere utilizzato in modalità di cifratura a blocchi se applicato a messaggi più lunghi di 64 bit. FIPS-81 specifica diverse modalità di utilizzo del DES, inclusa l'autenticazione . Ulteriori considerazioni sull'uso del DES sono presenti in FIPS-74 .

### Struttura generale

La struttura generale dell'algoritmo è mostrata nella Figura 1: ci sono 16 fasi identiche di processo dette round. 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. 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 rosso $\oplus$ denota l'operazione di OR esclusivo (XOR). La F-function mescola metà del blocco con una parte della chiave . Il risultato della F-function è 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)

La F-function, rappresentata nella Figura 2, operate 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 key schedule (descritto più avanti).
* Sostituzione — dopo la miscelazione con la sottochiave, il blocco viene diviso in 8 pezzi di 6 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 mediante 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 risultati delle S-box sono riordinati in base alle permutazioni|permutazioni fisse della P-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 '40 come condizione necessaria per rendere pratica e sicura la cifratura.

### Gestore della chiave

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 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 ruotate verso sinistra di uno o due bit (specifico per ogni ciclo) e quindi vengono scelti 48 bit per la sottochiave mediante la 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

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 che ne rende difficile l'utilizzo pratico.

### Attacco a forza bruta

Per ogni algoritmo di cifratura, il metodo più semplice di attacco è quello con Metodo forza bruta|forza bruta — provare tutte le possibili chiavi. La lunghezza della chiave determina il numero di chiavi possibili e quindi la fattibilità dell'attacco. Per il 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 possedeva computer abbastanza potenti da violare chiavi di questa lunghezza 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 7 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 ciberspazio, del costo di circa 250.000 dollari (vedi EFF DES cracker). Fu costruita per dimostrare che il DES era violabile 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". Questa macchina violò con la sola forza bruta una chiave in meno di 2 giorni di ricerca; più o meno nello stesso momento un membro del Dipartimento della Giustizia degli Stati Uniti annunciava che il DES era inviolabile.

### Attacchi più rapidi di quello a forza bruta

Esistono tre tipi di attacco conosciuti in grado di violare il DES completo con tutti i sedici cicli di complessità inferiore a quello di forza bruta: la crittanalisi differenziale, crittanalisi lineare e l'attacco di Davies. A ogni modo, questi attacchi sono solo teorici, non attuabili in pratica; questo tipo di attacchi viene detto 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 a IBM sia alla NSA e tenuta segreta. Per violare tutti i 16 cicli, la crittanalisi differenziale richiede 2$^{47}$ testi in chiaro scelti. Il DES è stato progettato per resistere a questo attacco.
* La crittanalisi lineare è stata scoperta da Mitsuru Matsui e occorrono 2$^{43}$ 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 e 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è 2$^{41}$ inveche che 2$^{43}$). 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 2$^{39}$–2$^{41}$ 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 2$^{50}$ testi in chiaro, ha una complessità computazionale di 2$^{50}$ e 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 sedici 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 e 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 2$^{15,8}$ testi in chiaro e una complessità temporale di 2$^{29,2}$ (Biham e altri, 2002).

### Proprietà crittanalitiche minori

Il DES possiede la proprietà complementare cioè che
    $E_{K}(P)=C\Leftrightarrow E_{\overline {K}}({\overline {P}})={\overline {C}}$
dove ${\overline {x}}$ è il complemento bit a bit di $x$. $E_{K}$ denota la cifratura con la chiave $K$. $P$ e $C$ indicano rispettivamente il testo in chiaro e 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.
Il DES ha inoltre le quattro cosiddette chiavi deboli. La cifratura (E) e la decifratura (D) con una chiave debole hanno lo stesso effetto (vedi involuzione):
    $E_{K}(E_{K}(P))=P$ o in modo equivalente, $E_{K}=D_{K}$
Esistono anche sei coppie di chiavi semi-deboli. La cifratura con un elemento di una coppia di chiavi semideboli, $K_{1}$, ha lo stesso risultato della decifratura con l'altro elemento, $K_{2}$:
    $E_{K_{1}}(E_{K_{2}}(P))=P$ o equivalentemente, $E_{K_{2}}=D_{K_{1}}$
È 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.
È stato dimostrato che il DES non è un gruppo o più precisamente, l'insieme $\{E_{K}\}$ (per tutte le possibili chiavi $K$) sotto la composizione funzionale non è un gruppo e neanche si avvicina a 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.

## Bibliografia

* Eli Biham, Adi Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer Verlag, 1993. ISBN 0-387-97930-1, ISBN 3-540-97930-1.
* Eli Biham, Alex Biryukov: An Improvement of Davies' Attack on DES. J. Cryptology 10(3): 195-206 (1997)
* Eli Biham, Orr Dunkelman, Nathan Keller: Enhancing Differential-Linear Cryptanalysis. ASIACRYPT 2002: pp254–266
* A.Biryukov, C.De Canniere, M.Quisquater, "On Multiple Linear Approximations", CRYPTO 2004 (to appear); preprint (PDF).
* Keith W. Campbell, Michael J. Wiener: DES is not a Group. CRYPTO 1992: pp512–520
* Don Coppersmith. (1994). The data encryption standard (DES) and its strength against attacks. IBM Journal of Research and Development, 38(3), 243–250.
* Witfield Diffie, Martin Hellman, "Exhaustive Cryptanalysis of the NBS Data Encryption Standard" IEEE Computer 10(6), June 1977, pp74-84
* John Gilmore, "Cracking DES: Secrets of Encryption Research, Wiretap Politics and Chip Design", 1998, O'Reilly, ISBN 1565925203.
* Pascal Junod, "On the Complexity of Matsui's Attack. Selected Areas in Cryptography", 2001, pp199-211.
* Burton S. Kaliski Jr., Matthew J. B. Robshaw: Linear Cryptanalysis Using Multiple Approximations. CRYPTO 1994: pp26–39
* Lars R. Knudsen, John Erik Mathiassen: A Chosen-Plaintext Linear Attack on DES. FSE 2000: pp262–272
* Susan K. Langford, Martin E. Hellman: Differential-Linear Cryptanalysis. CRYPTO 1994: 17–25
* Steven Levy, Crypto: How the Code Rebels Beat the Government Saving Privacy in the Digital Age (ISBN 0140244328)
* Mitsuru Matsui: Linear Cryptanalysis Method for DES Cipher. EUROCRYPT 1993: pp386-397
* Mitsuru Matsui: The First Experimental Cryptanalysis of the Data Encryption Standard. CRYPTO 1994: pp1-11
* National Bureau of Standards, Data Encryption Standard, FIPS-Pub.46. National Bureau of Standards, U.S. Department of Commerce, Washington D.C., January 1977.

## Collegamenti esterni

* FIPS 46-3: The official document describing the DES standard (PDF); An older version in HTML.
* The EFF DES cracker project
* Cryptography pointers for DES
* John Savard's description of DES
* A worked example of the DES algorithm
* A Javascript DES calculator showing intermediate values