Data Encryption Standard
Monica Bianchini
[email protected]
Dipartimento di Ingegneria dell’Informazione
Università di Siena
Introduzione
• Il 15 Maggio 1973, il National Bureau of Standards
(NBS) pubblicò un invito, nel Registro Federale, per
l’emissione di un crittosistema standard
 nasce DES  Data Encryption Standard, che è
divenuto il crittosistema più usato nel mondo
• DES fu sviluppato alla IBM, come evoluzione di un
crittosistema più antico, LUCIFER, e fu pubblicato sul
Registro Federale il 17 Marzo 1975
• La definizione di DES è riportata nel Federal
Information Processing Standards Publication 46, del
15 Gennaio 1977
• DES viene revisionato con frequenza quinquennale da
NBS
DES  1
•
•
DES codifica una stringa di plaintext, x, di 64 bit,
utilizzando una chiave k di 56 bit, ed ottenendo un
testo cifrato rappresentato da una stringa di 64 bit
L’algoritmo si compone di tre passi:
1. Dato il plaintext x, si costruisce la stringa x0,
permutando i bit di x secondo una permutazione iniziale
(fissata) IP. In particolare, x0=IP(x)=L0R0, dove L0
comprende i primi 32 bit di x0 e R0 gli ultimi 32
2. LiRi, per 1i16, viene calcolato come
Li=Ri-1
Ri=Li-1  (Ri-1,ki)
dove  è l’operatore di XOR,  è una funzione che verrà
descritta nel seguito, e k1,k2,…,k16 sono stringhe di 48 bit
calcolate in funzione di k. k1,k2,…,k16 formano il key
schedule
3. Si applica la permutazione inversa IP-1 alla stringa di bit
R16L16, ottenendo il testo cifrato y, cioè y=IP-1(R16L16)
DES  2
Li-1
Ri-1
ki


Li
Ri
Un passo di codifica di DES
DES  3
•
La funzione  ha come primo argomento la stringa A di 32
bit, come secondo argomento la stringa J di 48 bit, e
produce in output una stringa di bit di lunghezza 32
•
A viene “espanso” in una stringa di 48 bit in base ad una
funzione di espansione E(A) fissata. E(A) consiste dei 32
bit di A permutati, 16 dei quali compaiono due volte
•
Si calcola E(A)  J e si scrive il risultato come
la
concatenazione di otto stringhe di 6 bit B=B1B2B3B4B5B6B7B8
•
Si utllizzano gli Si, 1i8, che sono array 416 i cui
elementi sono interi compresi fra 0 e 15. Data una stringa
di 6 bit Bj=b1b2b3b4b5b6, Sj(Bj) viene calcolata come segue:
i due bit b1 e b6 determinano la rappresentazione binaria di
una riga r di Sj (0r3), ed i quattro bit b2b3b4b5
determinano la rappresentazione binaria di una colonna c di
Sj (0c15). Pertanto Sj(Bj) è l’elemento Sj(r,c), scritto in
binario sotto forma di stringa di 4 bit  Cj=Sj(Bj), 1j8
•
La stringa di 32 bit C= C1C2C3C4C5C6C7C8 viene permutata in
accordo ad una permutazione P fissata. La stringa
risultante P(C) è (A,J )
A
DES  4
E
E(A )

B1 B 2 B3 B 4 B 5 B 6 B 7 B 8
S1 S2 S3 S4 S5 S6 S7 S8
Realizzazione
della
funzione
 in DES
C1 C2 C3 C4 C5 C6 C7 C8
P
(A,J )
J
DES  5
• Le funzioni utilizzate in DES sono…
58
60
62
64
57
59
61
63
50
52
54
56
49
51
53
55
42
44
46
48
41
43
45
47
IP
34
36
38
40
33
35
37
39
26
28
30
32
25
27
29
31
18
20
22
24
17
19
21
23
10
12
14
16
9
11
13
15
2
4
6
8
1
3
5
7
40
39
38
37
36
35
34
33
8
7
6
5
4
3
2
1
48
47
46
45
44
43
42
41
IP-1
16
15
14
13
12
11
10
9
56
55
54
53
52
51
50
49
24
23
22
21
20
19
18
17
64
63
62
61
60
59
58
57
32
31
30
29
28
27
26
25
E
bit-selection table
32
4
8
12
16
20
24
28
1
5
9
13
17
21
25
29
2
6
10
14
18
22
26
30
3
7
11
15
19
23
27
31
4
8
12
16
20
24
28
32
5
9
13
17
21
25
29
1
…ciò significa, ad esempio, che il 58-esimo bit di x è
il primo bit di IP(x), il 50-esimo bit di x è il secondo
di IP(x), etc.
DES  6
•
Inoltre…
14
0
4
15
4
15
1
12
13
7
14
8
1
4
8
2
S2
15
3
0
13
1
13
14
8
8
4
7
10
14
7
11
1
6
15
10
3
S3
10
13
13
1
0
7
6
10
9
0
4
13
14
9
9
0
6
3
8
6
3
4
15
9
15
6
3
8
5
10
0
7
S4
7
13
10
3
13
8
6
15
14
11
9
0
3
5
0
6
0
6
12
10
6
15
11
1
9
0
7
13
10
3
13
8
S1
2
14
13
4
15
2
6
9
11
2
4
15
11
13
2
1
3
8
13
4
8
1
11
7
3
10
15
5
4
14
1
2
10
6
12
11
6
12
9
3
12
11
7
14
5
9
3
10
9
5
10
0
0
3
5
6
7
8
0
13
7
0
8
6
2
1
12
7
13
10
6
12
12
6
9
0
0
9
3
5
5
11
2
14
10
5
15
9
1
2
11
4
13
8
1
15
12
5
2
14
7
14
12
3
11
12
5
11
4
11
10
5
2
15
14
2
8
1
7
12
1
4
15
9
2
7
1
4
8
2
3
5
9
12
5
11
5
12
14
11
11
1
5
12
12
10
2
7
4
14
8
2
15
9
4
14
DES  7
10
7
13
14
11
13
7
2
6
1
8
13
8
5
15
6
3
15
12
0
5
0
9
15
2
14
4
11
12
11
2
8
4
2
1
12
1
12
11
7
7
4
10
1
S6
12
19
9
4
1
15
14
3
10
4
15
2
15
2
5
12
9
7
2
9
2
12
8
5
6
9
12
15
8
5
3
10
0
6
7
11
13
1
0
14
3
13
4
1
S7
4
13
1
6
11
0
4
11
2
11
11
13
14
7
13
8
15
4
12
1
0
9
3
4
8
1
7
10
13
10
14
7
3
14
10
9
12
3
15
5
9
5
6
0
S8
13
1
7
2
2
15
11
1
8
13
4
14
4
8
1
7
6
10
9
4
15
3
12
10
11
7
14
8
1
4
2
13
10
12
0
15
9
5
6
12
3
6
10
9
S5
15
10
5
9
5
2
0
14
14
11
13
0
0
9
3
4
10
15
5
2
5
0
15
3
14
8
0
5
5
3
11
8
7
11
13
0
14
0
1
6
4
14
10
7
7
12
8
15
13
3
6
10
6
8
9
3
0
14
3
5
9
6
14
3
11
8
6
13
1
6
2
12
12
9
5
6
7
2
8
11
16
29
1
5
2
32
19
22
7
12
15
18
8
27
13
11
P
20
28
23
31
24
3
30
4
21
17
26
10
14
9
6
25
DES  8
• Infine, occorre descrivere il calcolo della succesione di
chiavi, a partire dalla chiave k
• k è una stringa di 64 bit, di cui 56 costituiscono la
chiave vera e propria, mentre i rimanenti 8 sono bit di
parità (per il rilevamento di errori)
• I bit di parità occupano le posizioni 8,16,…,64 ed
assumono valore tale che ogni byte abbia un numero
dispari di bit a 1. Il bit di parità può servire a rilevare
errori su un singolo bit del byte relativo
• I bit di parità non vengono utilizzati nel calcolo del key
schedule
DES  9
•
Calcolo della succesione di chiavi ki, 1i16
1. Data la chiave k a 64 bit, si tralasciano i bit di parità,
mentre si permutano i rimanenti 56 bit, in base alla
permutazione PC1, fissata a priori. Sia PC1(k)=C0D0, dove
C0 comprende i primi 28 bit di PC1(k) e D0 gli ultimi 28
2. Per i compreso fra 1 e 16 si calcolano
Ci=LSi(Ci-1)
Di=LSi(Di-1)
e ki=PC2(CiDi). LSi è uno shift ciclico a sinistra, di una o
due posizioni in funzione del valore di i: si scorre di una
posizione per i=1,2,9,16, di due in tutti gli altri casi.
PC2 è una permutazione fissata
57
1
10
19
63
7
14
21
49
58
2
11
55
62
6
13
41
50
59
3
47
54
61
5
PC1
33
42
51
60
39
46
53
28
25
34
43
52
31
38
45
20
17
26
35
44
23
30
37
12
9
18
27
36
15
22
29
4
14
3
23
16
41
30
44
46
17
28
19
7
52
40
49
42
PC2
11
15
12
27
31
51
39
50
24
6
4
20
37
45
56
36
1
21
26
13
47
33
34
29
5
10
8
2
55
48
53
32
DES  10
•
Il calcolo della successione di chiavi viene effettuato
secondo il seguente schema
k
PC1
C0
D0
LS1
LS1
C1
D1
LS2
LS2
LS16
LS16
C16
D16
PC2
PC2
k1
k2
DES  11
• Mostriamo adesso come viene generata la serie delle
chiavi utilizzate nelle 16 iterate di DES. Gli elementi
nelle tabelle seguenti indicano i bit di k che vengono
utilizzati ai vari passi
Passo 1
Passo 5
10
3
22
61
51
35
28
21
34
26
39
38
60
25
54
63
49
44
37
15
17
58
4
20
33
59
47
45
57
1
30
14
2
36
5
13
9
27
53
62
19
18
23
55
42
41
29
31
19
41
29
5
60
44
39
63
43
35
46
45
33
34
61
7
58
17
12
22
26
2
15
31
42
3
54
20
1
10
37
21
11
9
47
55
18
36
28
6
57
27
30
62
51
50
4
38
2
60
14
53
43
27
20
13
26
18
31
30
51
17
46
55
41
36
29
7
9
50
63
12
25
51
39
37
49
58
22
6
59
57
28
5
1
19
45
54
11
10
15
47
34
33
21
23
3
25
13
20
44
57
23
47
27
19
30
29
17
18
45
54
42
1
63
6
10
51
62
15
26
52
38
4
50
59
21
5
60
58
31
39
2
49
12
53
41
11
14
46
35
34
55
22
51
44
61
37
27
11
4
28
10
2
15
14
36
1
30
39
25
49
13
54
58
34
47
63
9
35
23
21
33
42
6
53
43
41
12
20
50
3
29
38
60
59
62
31
18
17
5
7
52
9
28
4
57
41
7
31
11
3
14
13
1
2
29
38
26
50
47
53
59
35
46
62
10
36
22
55
34
43
5
20
44
42
15
23
51
33
63
37
25
60
61
30
19
18
39
6
35
57
45
21
11
60
55
12
59
51
62
61
49
50
14
23
9
33
28
38
42
18
31
47
58
19
7
5
17
26
53
37
27
25
63
4
34
52
13
22
44
43
46
15
2
1
20
54
36
58
12
55
41
25
64
15
60
52
51
28
50
51
13
22
10
34
31
37
43
19
30
46
59
49
6
39
18
27
20
4
57
26
62
7
35
17
47
21
9
44
45
14
3
2
23
53
Passo 2
Passo 3
Passo 4
Passo 6
Passo 7
Passo 8
DES  12
Passo 9
35
11
22
28
Passo 13
57
50
4
47
33
17
46
7
52
44
53
20
42
43
5
14
2
26
23
29
51
41
61
31
10
19
12
63
49
18
54
62
27
9
39
13
1
36
37
6
60
59
15
45
58
51
7
46
34
18
45
6
17
9
20
23
43
44
39
13
3
27
22
63
36
41
21
37
52
42
28
30
11
49
15
62
50
19
53
61
57
10
38
47
2
1
4
5
41
34
55
31
17
1
30
54
36
57
37
4
26
27
20
61
51
10
7
13
35
25
45
15
59
3
63
47
33
2
38
46
11
58
23
28
50
49
31
53
44
43
62
29
42
35
54
30
18
2
29
53
1
58
4
7
27
57
23
28
52
11
6
47
49
25
5
21
36
26
12
14
60
33
62
46
34
3
37
45
41
59
22
31
51
50
55
20
9
44
61
63
25
18
39
15
1
50
14
38
49
41
21
55
10
11
4
45
35
59
54
28
3
44
53
6
19
9
29
62
43
52
47
31
17
51
22
30
60
42
7
12
34
33
5
37
57
27
46
13
26
19
38
14
2
51
13
37
50
42
55
54
11
41
7
12
36
60
53
31
33
9
20
5
49
10
63
61
44
17
46
39
18
52
21
29
25
43
6
15
35
34
39
4
58
57
45
47
9
2
23
62
50
34
61
22
33
25
5
39
59
60
55
29
19
43
38
12
52
57
37
53
3
58
13
46
27
36
31
15
1
35
6
14
44
26
54
63
18
17
20
21
41
11
30
28
18
11
30
6
59
43
5
29
42
34
47
46
3
33
62
4
57
52
45
23
25
1
12
28
41
2
55
53
36
9
38
22
10
44
13
21
17
35
61
7
27
26
31
63
50
49
37
39
Passo 10
19
60
6
22
Passo 11
Passo 12
Passo 14
Passo 15
Passo 16
25
60
14
12
• La fase di decodifica viene realizzata utilizzando lo
stesso algoritmo, con y per input, e key schedule
k16,k15,…,k1. L’output è il plaintext x
Un esempio di codifica con DES  1
• Supponiamo di voler codificare il plaintext esadecimale
0123456789ABCDEF

0000000100100011010001010110011110001001101010111100110111101111
utilizzando la chiave esadecimale
133457799BBCDFF1
La corrispondente chiave binaria, senza bit di parità, è
00010010011010010101101111001001101101111011011111111000
• Applicando IP si ottengono L0 ed R0, come…
L0=11001100000000001100110011111111
L1=R0=11110000101010101111000010101010
Un esempio di codifica con DES  2
• I 16 passi della codifica calcolano…
E(R0)=011110100001010101010101011110100001010101010101
k1=000110110000001011101111111111000111000001110010
E(R0)k1=011000010001011110111010100001100110010100100111
C=01011100100000101011010110010111
(R0,k1)=00100011010010101010100110111011
L2=R1=11101111010010100110010101000100
E(R1)=011101011110101001010100001100001010101000001001
k2=011110011010111011011001110110111100100111100101
E(R1)k2=000011000100010010001101111010110110001111101100
C=11111000110100000011101010101110
(R1,k2)=00111100101010111000011110100011
L3=R2=11001100000000010111011100001001
Un esempio di codifica con DES  3
E(R14)=111000000101010001011001010010101100000001011011
k15=101111111001000110001101001111010011111100001010
E(R14)k15=010111111100010111010100011101111111111101010001
C=10110010111010001000110100111100
(R14,k15)=01011011100000010010011101101110
L16=R15=01000011010000100011001000110100
E(R15)=001000000110101000000100000110100100000110101000
k16=110010110011110110001011000011100001011111110101
E(R15)k16=111010110101011110001111000101000101011001011101
C=10100111100000110010010000101001
(R15,k16)=11001000110000000100111110011000
R16=00001010010011001101100110010101
•
Infine, applicando IP-1 a R16L16, si ottiene la stringa
100001011110100000010011010101000000111100001011011010000000101
ovvero, in esadecimale
85E813540F0AB405
La controversia del DES  1
•
•
•
•
•
Quando DES fu proposto come standard, furono
sollevate numerose critiche relative alle S-box.
Infatti, tutti i calcoli effettuati in DES, ad eccezione
delle S-box, sono lineari, poiché calcolare l’XOR di due
output equivale a calcolare l’output relativo all’XOR degli
stessi input
Le S-box, che costituiscono la nonlinearità del
crittosistema, sono fondamentali per la sua sicurezza: i
crittosistemi lineari (tipo Affine cipher) sono infatti
proni ad attacchi Known plaintext
Tuttavia, i criteri di costruzione delle S-box non sono
stati resi pubblici
C’è chi sostiene che le S-box contengano delle trapdoor
(scorciatoie) che garantiscano alla National Security
Agency (NSA) la possibilità di decifrare messaggi,
mantenendo la sicurezza di DES
La controversia del DES  2
•
Nel 1976, la NSA rese pubbliche le
specifiche di progetto relative alle S-box:
1.
2.
3.
4.
•
•
Ciascuna riga di ciascuna S-box è una permutazione
degli interi 0,…,15
Nessuna delle S-box è una funzione lineare o affine
Il cambiamento di un bit in ingresso ad una S-box
provoca il cambiamento di al più due bit del risultato
Per ogni S-box e x, S(x) e S(x001100) differiscono
almeno per due bit (x è una stringa di 6 bit)
Due ulteriori proprietà
conseguenze progettuali:
5.
6.
seguenti
vennero
indicate
come
Per ogni S-box e x, per e,f {0,1}, S(x)S(x11ef00)
Per ogni S-box, se un dato bit di input è fissato, il
valore di un dato bit di output assume i valori 0 e 1 in
maniera equiprobabile
Unlteriori (eventuali) specifiche progettuali non sono
note
La controversia del DES  3
La critica più pertinente al DES riguarda la relativa
“ristrettezza” dello spazio delle chiavi, |K |=256, per
garantirne la sicurezza
• Sono state proposte una serie di apparecchiature
special-purpose in grado di sferrare a DES un attacco
Known plaintext, per mezzo di una ricerca esaustiva
nello spazio delle chiavi
•
o Data una stringa di 64 bit, il plaintext x, ed il
corrispondente testo cifrato y, dovrebbero essere
testate tutte le possibili chiavi fino a quando non viene
rilevata una chiave k tale che ek(x)=y (ce ne potrebbero
essere più di una)
Nel 1977, Diffie ed Helman progettarono un chip in
VLSI che poteva testare 106 chiavi al secondo
• Una macchina dotata di 106 chip poteva sondare
l’intero spazio delle chiavi in un giorno circa (ma
sarebbe costata 20 milioni di dollari!)
•
La controversia del DES  4
•
•
•
•
•
Al CRYPTO ’93, Michael Wiener descrisse molto
dettagliatamente una macchina per la ricerca nello
spazio delle chiavi
La macchina era basata su un chip pipelined dedicato, in
grado di realizzare concorrentemente i 16 passi di
codifica
Il chip poteva testare 5107 chiavi per secondo e
poteva essere realizzato (con la tecnologia dell’epoca)
ad un costo unitario $10,50
Una configurazione dotata di 5760 chip, del costo di
100 mila dollari, poteva sondare lo spazio delle chiavi in
circa un giorno e mezzo, mentre una macchina 10 volte
più potente (e più costosa) ci sarebbe riuscita in poco
più di tre ore
Ormai, DES trova rare utilizzazioni, data la sua
vulnerabilità, utilizzando le macchine attuali (in cui
tempi e costi non sono assolutamente proibitivi)
DES nelle applicazioni
•
Anche se descrivere DES a parole può risultare lungo e
noioso, DES può essere implementato in maniera molto
efficiente sia in hardware che in software:
o La sola operazione aritmetica necessaria è l’XOR fra
stringhe di bit
o La funzione di espansione E, le S-box, le permutazioni IP
e P, ed il calcolo delle chiavi k1, k2,…,k16 possono essere
tutte effettuate in tempo costante, attraverso look-up
table in software, o “bruciate” in un circuito in hardware
DES
ha
trovato
applicazioni
significative
nelle
transazioni bancarie: veniva utilizzato per codificare i
PIN (Personal Identification Number ) e le transazioni
su conto corrente per operazioni da ATM (Automated
Teller Machine )
• DES
è stato inoltre largamente impiegato da
organizzazioni
governative
americane,
quali
il
Department of Energy, il Justice Department ed il
Federal Reserve System
•
Modalità operative di DES  1
Per DES sono state definite quattro modalità operative
distinte: Electronic CodeBook (ECB), Cipher FeedBack
(CFB), Cipher Block Chaining (CBC) e Output FeedBack
(OFB)
• La modalità ECB corrisponde all’impiego classico dei cifrari
a blocchi: data una sequenza x1x2… di blocchi di
plaintext, ciascuno di 64 bit, ogni xi viene codificato per
mezzo della stessa chiave k, producendo una sequenza di
blocchi di testo cifrato y1y2…
• In modalità CBC, si effettua l’XOR fra il blocco corrente
di plaintext xi ed il blocco di testo cifrato al passo
precedente yi-1, prima di effettuare la codifica
utilizzando k. Occorre pertanto inizializzare y0=v e, per
i1, si ottiene yi=ek(yi-1  xi)
•
Modalità operative di DES  2
Modalità CBC
y0=v
x1
x2
y1
y2
+
+
dk
dk
ek
ek
+
+
y1
y2
x1
x2
Codifica CBC
y0=v
Decodifica CBC
Modalità operative di DES  3
Nelle modalità OFB e CFB viene generato un flusso di
chiavi che vengono successivamente poste in XOR con il
plaintext (tipo Stream cipher)
• OFB è uno stream cipher sincrono: il flusso di chiavi
viene prodotto iterativamente codificando un vettore v
di inizializzazione, lungo 64 bit
•
o Si definisce z0=v e quindi il keystream z1z2… viene
calcolato con la regola zi=ek(zi-1), i 1
o Infine, la sequenza plaintext x1x2… viene codificata
calcolando yi=xi  zi, i 1
In modalità CFB si inizializza y0=v e si produce il
keystream secondo la regola zi= ek(yi-1); si calcolano poi
yi= xi  zi, i 1 (come in OFB)
• In entrambe le modalità, OFB e CFB, la funzione ek di
codifica viene utilizzata anche in fase di decodifica
•
Modalità operative di DES  4
Modalità CFB
x2
x1
y0=v
y0=v
ek
ek
+
ek
+
y1
y2
y1
y2
+
x1
ek
+
x2
Codifica CFB
Decodifica CFB
Modalità operative di DES  5
•
Le quattro modalità
svantaggi diversi:
operative
hanno
vantaggi
e
o Nelle modalità ECB e OFB, il cambiamento di un blocco a
64 bit di plaintext, xi, altera il corrispondente blocco
cifrato, yi, ma non produce cambiamenti negli altri blocchi
o Può essere una caratteristica vantaggiosa: per esempio,
OFB viene usato per codificare le trasmissioni satellitarie
o Nelle modalità CBC e CFB, se un blocco, xi, di plaintext
cambia, vengono alterati dal cambiamento i blocchi cifrati
yi e successivi
o CBC e CFB sono utili nel caso dell’autenticazione. Più
specificamente, queste modalità possono essere usate per
produrre un Message Autentication Code (MAC)
o Il MAC viene accodato ad una sequenza di blocchi di
plaintext, e viene utilizzato per convincere Bob che il
messaggio proviene da Alice, senza interferenze da parte
di Oscar  MAC garantisce l’integrità del contenuto del
messaggio (ma non la sua segretezza)
DES per l’autenticazione  1
•
Descriviamo come la modalità CBC viene utilizzata per
produrre MAC:
o Il vettore di inizializzazione v viene posto a 0
o Viene costruito il testo cifrato y1,y2,…,yn, con la chiave k,
untilizzando CBC. Infine, viene definito MAC come yn
o Quindi Alice trasmette la sequenza di plaintext x1…xn e il
MAC
o Quando Bob riceve x1…xn può ricostruire y1…yn, utilizzando la
chiave segreta k, e verificare che yn coincide con il MAC che
ha ricevuto
o Oscar non può produrre un MAC valido perché non conosce k.
Inoltre, anche se intercetta il messaggio in plaintext e ne
altera il contenuto, è altamente improbabile che riesca a
modificare il MAC in modo tale da ingannare Bob
DES per l’autenticazione  2
•
In generale, è auspicabile abbinare la segretezza alla
garanzia di autenticità di un messaggio. In questo caso…
o Alice usa la chiave k1 per produrre un MAC per x1…xn;
quindi definisce MAC=xn+1 e codifica la sequenza x1…xn+1
utilizzando una seconda chiave, k2, ed ottenendo y1…yn+1
o Quando Bob riceve y1…yn+1 lo decodifica utilizzando k2 e
quindi controlla che xn+1 sia il MAC relativo al plaintext
x1…xn, con k1
o Altrimenti, Alice può usare k1 per codificare x1…xn,
ottenendo y1…yn, e quindi usare k2 per produrre il MAC=yn+1
per y1…yn
o Bob utilizzerà k2 per verificare il MAC e k1 per decifrare
y1…yn
Il trade-off tempo-memoria  1
Ricordiamo che, in un attacco Known plaintext, Oscar
ottiene
una
coppia
plaintext/ciphertext
prodotta
utilizzando una chiave k a lui sconosciuta
 Oscar conosce x e y=ek(x) e vuole determinare k
• Una caratteristica del trade-off tempo-memoria è che
non dipende dalla “struttura” di DES. Il solo aspetto del
DES rilevante per l’attacco è che sia il plaintext che il
testo cifrato sono costituiti da 64 bit, contro i 56 della
chiave
• Si è già parlato della possibilità di effettuare una ricerca
esaustiva nello spazio delle chiavi, che ha cardinalità 256:
non richiede memoria ma, in media, 255 chiavi verranno
esaminate prima del reperimento di quella cercata
• D’altra parte, per un dato x, Oscar può calcolare
anticipatamente yk=ek(x) per ogni chiave e costruire una
tabella di coppie (yk,k), ordinate rispetto a yk
•
Il trade-off tempo-memoria  2
•
•
•
•
•
In un momento successivo, quando Oscar ottiene il testo
cifrato y, può confrontarlo con i valori della tabella, e
reperire immediatamente la chiave k
In questo caso, la determinazione del valore della chiave
richiede un tempo costante, ma per contro vi è un grosso
spreco di memoria e lunghi tempi di calcolo preliminari
Il trade-off tempo-memoria combina un tempo di calcolo
inferiore rispetto alla ricerca esaustiva, ed un’occupazione
di memoria inferiore rispetto ad una tavola di look-up
L’algoritmo può essere descritto in funzione di due
parametri interi positivi, m e t
L’algoritmo richiede inoltre una funzione di riduzione R,
che riduce una stringa di 64 bit ad una di lunghezza 56
Il trade-off tempo-memoria  3
Sia x una stringa di plaintext fissata, di lunghezza 64.
Si definisce la funzione g(k0)=R(ek0 (x)), con k0 stringa
di 56 bit
• Nella fase di preprocessing, Oscar sceglie m stringhe
casuali di lunghezza 56, X(i,0), 1i  m. Oscar calcola
X(i,j), 1jt, in base alla relazione di ricorrenza
X(i,j)=g(X(i,j-1)), 1im, 1jt
• Quindi Oscar costruisce una tabella di coppie
T=(X(i,t),X(i,0)), ordinate in base alla prima
coordinata
• Più tardi, Oscar ottiene un testo cifrato y, che è la
codifica del plaintext x, e di nuovo vuole identificare
k. Determinerà se k è nelle prime t colonne dell’array
X, ma lo farà consultando solo la tabella T
•
Il trade-off tempo-memoria  4
Supponiamo che k=X(i,t-j), per qualche j, 1jt; in
questo caso gj(k)=X(i,t), dove gj è la funzione ottenuta
iterando g j volte. Ora si osservi che
gj(k)= gj-1(g(k))= gj-1(R(ek(x)))= gj-1(R(y))
• Si calcolino yj, 1jt, dalla relazione di ricorrenza
•
yj =
{
R(y)
se j=1
g(yj-1) se 1jt
 yj=X(i,t) se k=X(i,t-j). Tuttavia, yj=X(i,t) è una
condizione
necessaria
ma
non
sufficiente
per
determinare k, perché R non è iniettiva
• È necessario verificare che y=eX(i,t-j)(x) per avere la
certezza di aver scoperto la chiave
Il trade-off tempo-memoria  5
Oscar agisce in accordo al seguente algoritmo…
1.
2.
3.
4.
5.
6.
7.
Si calcola y1=R(y)
for j=1 to t do
if yj=X(i,t) per qualche i then
si calcola X(i,t-j) da X(i,0), iterando la
funzione g j volte
if y=eX(i,t-j)(x) then
si pone k=X(i,t-j) e QUIT
si calcola yj+1=g(yj)
Il trade-off tempo-memoria  6
Analizzando la probabilità di successo dell’algoritmo, si
può dimostrare che se mt 2  N=256, la probabilità che
k=X(i,t-j), per qualche i,j, è circa 0.8mt/N. Il fattore
0.8 tiene conto del fatto gli X(i,t) possono non essere
tutti distinti
• Prendendo m t N1/3 e costruendo circa N1/3 tavole,
ciascuna utilizzando una diversa funzione di riduzione R,
la memoria necessaria è pari a 112  N1/3 bit
• Il tempo speso in calcoli preliminari è O (N)
• Il tempo di esecuzione dell’algoritmo è invece dell’ordine
di O (N2/3) nel caso peggiore (cioè quando la ricerca
fallisce)
•