Il miglior attacco al DES conosciuto è senza dubbio quello definito dal metodo della Crittoanalisi differenziale, introdotto da E. Biham e A. Shamir [4]. Esso, come vedremo, definisce un attacco di tipo Chosen Plaintext, che si presta con successo alla rottura del DES nell'ipotesi che il numero di iterazioni sia ridotto (il DES a 8 iterazioni puó essere rotto in un paio di minuti su un personal computer).
Tuttavia quando il numero di iterazioni sale a 16 o piú, attacchi di questo tipo hanno complessità uguale a quella che si avrebbe con un algoritmo di ricerca nello spazio delle chiavi.
Questa potrebbe essere una motivazione al fatto che siano state scelte proprio 16 iterazioni nel DES standard e non meno. Si dice infatti che i due ideatori della crittoanalisi differenziale -- di cui uno è proprio lo Shamir noto per l'RSA -- quando pubblicarono questo tipo di attacco si consultarono con uno degli ideatori del DES. Quest'ultimo dichiarò poi che il sistema fu progettato in modo da resistere a questo tipo di attacco.
Nella nostra analisi ci limiteremo quindi ad illustrare un attacco con sole tre
iterazioni. In esso supporremo per semplicità che le permutazioni, iniziale IP
e finale 
, non vengano considerate in quanto esse non hanno effetto sulla
crittoanalisi.
Si considererà inizialmente un attacco di tipo Known Plaintext, cioè si considereranno note delle coppie, testo in chiaro - testo cifrato, con chiave segreta K uguale per tutte.
Una versione piú semplice si ha quando è possibile scegliere quelli che
sono i testi da cifrare in modo da velocizzare l'attacco. In mancanza di tale
possibilità, bisogna aspettare che vengano scelti un maggior numero di testi
affinché vengano scoperte certe proprietà (con un peggioramento di un
fattore di circa 
per la velocità dell'attacco).
Ciò su cui si basa la crittoanalisi differenziale è il confronto tra lo xor bit a bit di due testi in chiaro e lo xor bit a bit dei corrispondenti testi cifrati, o meglio delle differenze (da cui deriva anche il nome di questo tipo di attacco), al fine di scoprire la chiave utilizzata.
Nel testo che segue ci riferiremo a stringhe binarie; in particolare quelle
marcate con un apice indicheranno lo xor bit a bit di altre due stringhe, ad esempio
.
Per illustrare la crittoanalisi differenziale ci serviremo delle seguenti definizioni:
Tale insieme ha cardinalità 
, cioè uguale alla cardinalità di 
.
Infatti, considerando fissata la prima componente 
, l'altra 
(dove 
)
è definita in maniera univoca (dato che entrambi gli operandi sono a loro volta
fissati). Quindi poiché le possibili stringhe a 6 bit sono , risulta che
.
Consideriamo quindi due coppie 
, 
con 
, 
testi in chiaro
e 
, 
i corrispondenti testi cifrati, cioè:
consideriamo per la nostra analisi le stringhe
e
Testiamo quindi le differenze (xor) tra le coppie di testi considerando una singola iterazione dell'algoritmo DES (Figura 4).
Riportiamo quindi lo schema della funzione f in Figura 10.
Figura 10: Schema della funzione f.
L'attacco differenziale si concentra sulle S-box, che rappresentano l'unico punto non lineare dell'algoritmo.
Supponiamo di considerare una particolare S-box 
, con 
.
Dati quindi due possibili input ad essa, definiti da e (di 6 bit ciascuno), avremo un
input xor definito da: 
; considerando invece gli
output all'S-box , cioè 
e 
avremo un output xor
definito da: 
.
A questo punto per ogni coppia in 
possiamo calcolare l'output xor
di , ,
determinando cosí una distribuzione del numero di occorrenze per l'output xor
, cioè possiamo determinare quante coppie
in hanno output xor uguale a
y con 
.
Ad esempio consideriamo la prima S-box 
e supponiamo 
. Avremo che
Per ogni coppia in 
calcoliamo quindi l'output xor relativamente a .
Considerando per esempio la coppia (000000,110100), abbiamo:
e
allora l'output xor per la coppia (000000,110100) è data da:
Se tali operazioni vengono eseguite per tutte le 64 coppie in
si ottiene la seguente distribuzione del numero di occorrenze
per l'output xor:
| 0000 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 |
| 0 | 8 | 16 | 6 | 2 | 0 | 0 | 12 |
Come si puó notare, per alcuni valori di output xor (0000, 0101, etc.)
non vi sono coppie corrispondenti in . La cosa importante mostrata
dalla Tabella 11 è che in realtà non tutte le possibili stringhe
di 4 bit sono possibili come valori di output xor. Nell'esempio
considerato solo la metà dei valori sono possibili (anche se
questo rappresenta un caso estremo), tuttavia in generale solo il
75-80 % dei possibili output xor si possono effettivamente
presentare.
Cerchiamo ora di sfruttare la non uniforme distribuzione degli
output xor, ed in particolare il fatto che alcuni di tali valori
sono possibili ed altri no. L'idea è quella di collezionare
abbastanza statistiche in modo da conoscere poi i valori possibili
degli output xor relativi ad una particolare stringa 
, e
cosí per ogni altra stringa.
Diamo ora alcune definizioni per meglio descrivere queste distribuzioni:
rappresenta, relativamente alla S-box j, l'insieme
delle stringhe binarie di lunghezza sei tali che l'input xor di tale stringa
con un'altra è 
e l'output xor da 
.
Fissati i valori e , la definizione data sarà utile per
cercare le coppie di stringhe 
che godono della proprietà
che il loro input xor è , ed il loro output xor è
, senza dover analizzare necessariamente tutte le coppie possibili.
Infatti dalla definizione, basterà effettuare la ricerca sul solo valore
, in quanto fissato un tale che 
, la seconda componente della coppia che si vuole trovare
è univocamente determinata da .
Ad esempio, con i valori:
e
si ottengono i valori di 
riportati in Tabella 12 (con 
).
Ci chiediamo a questo punto quante diverse tabelle di questo
tipo si possono avere.
Consideriamo l'insieme definito da IN(z,x),
abbiamo già visto che per un fissato valore di z, al variare
di x, otteniamo una particolare tabella. Sapendo che il valore
z puó essere scelto in modi diversi ( 
), si
possono costruire tabelle di questo tipo per ogni S-box .
Ripetendo quindi il discorso fatto per tutte le 8 S-box si ottengono
tabelle totali (distribuzioni), che possono essere
calcolate agevolmente anche con un PC.
Cerchiamo ora di trovare quelle che sono le possibili stringhe B che
possono presentarsi come input alle S-box.
| output xor | possibili input |
| 0000 | |
| 0001 | 000011, 001111, 011110, 011111 |
| 101010, 101011, 110100, 111011 | |
| 0010 | 000100, 000101, 001110, 010001 |
| 010010, 010100, 011010, 011011 | |
| 100000, 100101, 010110, 101110 | |
| 101111, 110000, 110001, 111010 | |
| 0011 | 000001, 000010, 010101, 100001 |
| 110101, 110110 | |
| 0100 | 010011, 100111 |
| 0101 | |
| 0110 | |
| 0111 | 000000, 001000, 001101, 010111 |
| 011000, 011101, 100011, 101001 | |
| 101100, 110100, 111000, 111100 | |
| 1000 | 001001, 001100, 011001, 101101 |
| 111000, 111101 | |
| 1001 | |
| 1010 | |
| 1011 | |
| 1100 | |
| 1101 | 000110, 010000, 010110, 011100 |
| 100010, 100100, 101000, 110010 | |
| 1110 | |
| 1111 | 000111, 001010, 010110, 011100 |
| 111110, 111111 |
Ricordiamo che l'input alle S-box, per una qualunque iterazione i, è
definito da 
, dove 
E 
rappresenta
l'espansione della stringa 
e J=k (vedi Figura 5),
quindi l'input xor a tutte le S-box puó essere calcolato
come segue:
Si vede che l'input xor non dipende dai valori della chiave mentre l'output xor sí, come si puó notare dalla sua definizione:
Scriviamo ora B, E e J come concatenazione di stringhe binarie di lunghezza sei cioè:
cosí come
Supponiamo ad un certo punto dell'algoritmo di conoscere: 
e 
per
qualche j (j è l'indice della S-box su cui stiamo lavorando),
e supponiamo che sia noto anche il valore
dell'output xor per , cioè:
Si possono fare ora delle considerazioni circa la chiave.
Innanzitutto si puó calcolare:
da cui
Quindi dalla definizione (1) e dalle relazioni definite dalla (2) e (3), si puó concludere che
dove in realtà è ottenuto come lo xor bit a bit dei valori e
(vedi Figura 5), e quindi abbiamo:
L'idea dell'algoritmo che andremo a definire è quella di sfruttare
proprio quest'ultima relazione per arrivare a scoprire i bit della chiave
. In particolare:
si determina l'insieme
corrispondente , che definisce anche dei possibili valori
di chiavi come si puó notare dalla (4); (costituente il j-esimo blocco, di 6 bit,
della chiave J); 
Introduciamo a questo punto la seguente:
Questo insieme altro non è che un insieme di possibili
chiavi (dato che 
) per le quali, supponendo di partire dai valori 
, si
ottiene un output xor che vale , cioè:
Supponendo quindi che: e siano due input all'S-box
; l'output xor per è ; e conoscendo
l'insieme 
da cui prendere i valori ,
utili al calcolo delle chiavi ( 
);
allora si ha che:
cioè
Quest'insieme definisce i possibili valori che puó assumere
relativamente alla
tripla 
. Al variare della tripla avremo
un altro insieme di possibili valori per .
Tuttavia poiché la chiave J usata è sempre la stessa, allora il j-esimo
blocco dovrà appartenere
a tutti gli insiemi corrispondenti alle varie triple, e quindi alla loro
intersezione.
È da notare che in ognuno degli insiemi sopra definiti solo un blocco è realmente utilizzato, e quindi dall' intersezione degli insiemi si otterrà sempre un solo valore.
Ad esempio siano:
allora 
e i valori di sono quelli
che si possono leggere in Tabella 12, cioè
Quindi risulta che:
Con diverse triple possiamo determinare i valori di .
Poiché i possibili valori di sono 64 utilizziamo allora un array di 64
contatori, e ogni volta che calcoliamo i valori nell'insieme 
incrementiamo i contatori
corrispondenti a tali valori nell'array definito.
Dopo t tentativi (t scelte di triple)
il contatore che assume valore t (cioè che appartiene a tutti gli insiemi)
ci indicherà il valore di .
Se, ad esempio, il secondo
contatore dell'array vale t allora il valore 000001 è il vero valore di
corrispondente all'intersezione dei vari insiemi .
Poiché è solo un blocco della sottochiave, con 8 array
riusciamo a calcolare l'intera sottochiave.
