next up previous contents
Successivo: Modalità operative del DES Su: Possibili attacchi al DES Precedente: Crittoanalisi differenziale

Un attacco al DES a 3 iterazioni

Vediamo ora come applicare concretamente il discorso fatto fino ad ora nell'ipotesi di usare il DES a 3 iterazioni.

Supponendo che tex2html_wrap_inline3570 e tex2html_wrap_inline3572 siano due testi in chiaro, e tex2html_wrap_inline3574 il loro or esclusivo; applicando ad entrambe l'algoritmo DES con chiave K, definito dallo schema in Figura 11, otteniamo le stringhe cifrate tex2html_wrap_inline3578 e tex2html_wrap_inline3580 .

   figure1310
Figura 11: Schema del DES a tre iterazioni.

Sfruttando quindi le operazioni definite dal DES a tre iterazioni, posso esprimere tex2html_wrap_inline3582 e tex2html_wrap_inline3584 come segue:

eqnarray1316

e analogamente

displaymath3586

Da queste otteniamo l'espressione per tex2html_wrap_inline3588

displaymath3590

Quindi scegliamo i testi in chiaro tali che tex2html_wrap_inline2564 = tex2html_wrap_inline3594 (ad esempio tex2html_wrap_inline3596 ). Ed ecco perché questo è definito come un chosen plaintext attack. Allora:

displaymath3598

e quindi

displaymath3600

o anche

displaymath3602

Ricordiamo ora che

displaymath3604

e

displaymath3606

dove C e tex2html_wrap_inline3610 rappresentano l'output delle 8 S-box alla terza iterazione (vedi Figura 5), e P è la permutazione definita nella funzione f, che è conosciuta pubblicamente. Quindi

eqnarray1396

da cui

displaymath3616

Ricordiamo ora che per calcolare il valore della stringa E, all'ultima iterazione del DES, si applicava alla stringa A ( tex2html_wrap_inline3622 in questo caso) la funzione di espansione E, ottenendo E = E(A). Si effettuava poi lo xor bit a bit tra quest'ultimo valore e la stringa J (in questo caso tex2html_wrap_inline3630 ) ottenendo quindi l'input delle 8 S-box. Sapendo inoltre che nell'ultima iterazione il valore di tex2html_wrap_inline3632 è definito essere uguale al valore tex2html_wrap_inline3622 , cioè tex2html_wrap_inline3636 come pure tex2html_wrap_inline3638 , e poiché i valori di tex2html_wrap_inline3632 e tex2html_wrap_inline3642 sono noti, conosciamo di conseguenza anche i valori di tex2html_wrap_inline3622 e tex2html_wrap_inline3646 da cui, per quanto detto sopra, anche i valori di E per la terza iterazione. Infatti: E= E tex2html_wrap_inline3650 E tex2html_wrap_inline3652 , E= E tex2html_wrap_inline3656 E tex2html_wrap_inline3658 (Si ricordi che le permutazioni sono operatori lineari e sono noti).

A questo punto conosciamo E, tex2html_wrap_inline3662 e tex2html_wrap_inline3664 per la terza iterazione e quindi siamo nelle ipotesi precedenti e possiamo quindi procedere come visto, costruendo gli insiemi tex2html_wrap_inline3666 e calcolando i valori tex2html_wrap_inline3668 della chiave tex2html_wrap_inline3630 .

Dalla conoscenza di questa chiave tex2html_wrap_inline3630 possiamo poi ricavare 48 bit della chiave K. Basta infatti osservare l'algoritmo di schedulazione alla terza iterazione.

I rimanenti 8 bit della chiave vengono trovati mediante una ricerca esaustiva delle tex2html_wrap_inline3676 possibilità di completare la chiave K.

L'algoritmo che calcola gli insiemi tex2html_wrap_inline3680 con input

displaymath3682

dove tex2html_wrap_inline3684 è il seguente [27]:

tex2html_wrap3754

Questo algoritmo puó essere ripetuto per n volte (dove n è scelto opportunamente), al variare dell'input, ottenendo una sequenza di insiemi tex2html_wrap_inline3700 , tex2html_wrap_inline3702 , tex2html_wrap_inline3704 . L'intersezione tex2html_wrap_inline3706 fornisce tex2html_wrap_inline3708 .

Similmente possiamo ottenere tex2html_wrap_inline3710 . La sottochiave J è uguale a tex2html_wrap_inline3714 .

Nella Tabella 13 riportiamo il numero di attacchi necessari per rompere il sistema DES: si noti come per un attacco chosen plaintext il numero di tentativi da effettuare sia sempre minore rispetto a quelli per un attacco known plaintext [11].

 

num. round chosen plaintext known plaintext
8 tex2html_wrap_inline3716 tex2html_wrap_inline3718
9 tex2html_wrap_inline3720 tex2html_wrap_inline3722
10 tex2html_wrap_inline3720 tex2html_wrap_inline3726
11 tex2html_wrap_inline3728 tex2html_wrap_inline3730
12 tex2html_wrap_inline3728 tex2html_wrap_inline3730
13 tex2html_wrap_inline3736 tex2html_wrap_inline3738
14 tex2html_wrap_inline3736 tex2html_wrap_inline3742
15 tex2html_wrap_inline3730 tex2html_wrap_inline2532
16 tex2html_wrap_inline3730 tex2html_wrap_inline2858
Tabella 13: Tentativi necessari per rompere il DES.

 


next up previous contents
Successivo: Modalità operative del DES Su: Possibili attacchi al DES Precedente: Crittoanalisi differenziale

Aniello Castiglione e Gerardo Maiorano < anicas,germai@zoo.diaedu.unisa.it >