Reti di calcolatori
Prof. Alfredo Petrosino
DES: applicazioni ed evoluzioni
Calzetta Emilia
Cervone Vincenzo
Programmazione didattica
Titolo: DES: evoluzioni ed applicazioni
Classe: 5^ I.T.I.
Contenuti:
Cenni sulla crittografia; DES: Introduzione storica; La Struttura del DES: codifica
e decodifica; Le modalità operative ed applicative del DES: Electronic Codebook
Chaining, Cipher Block Chaining, Cipher Feedback, Output Feedback;
Crittoanalisi del DES; Esercizi.
Obiettivi:
 Comprendere la struttura e l’utilizzo degli algoritmi crittografici a chiave
privata
 Comprendere l’importanza della sicurezza in un sistema informatico
 Demotivare gli alunni a intraprendere azioni di intrusione nei sistemi
informatici
2
Programmazione didattica
Prerequisiti e verifica:
Il prerequisito richiesto è la conoscenza di base della crittografia. La verifica sarà
svolta durante il corso sia sotto forma di dialogo e sperimentazione e sia mediate
esercizi, prove pratiche e tesine sia di gruppo che individuali.
Modalità di lavoro:
lezioni frontali
utilizzo del laboratorio
Riferimenti:
Eli Biham, Adi Shamir, Differential Cryptanalysis of the Data Encryption Standard,
Springer Verlag, 1993.
Cryptography and Network Security: Principles and Practice (3rd Edition)
by William Stallings, 2003
Don Coppersmith. (1994). The data encryption standard (DES) and its strength
against attacks. IBM Journal of Research and Development, 38(3), 243–250.
Joan Daemen and Vincent Rijmen, "The Design of Rijndael: AES - The Advanced
Encryption Standard." Springer-Verlag, 2002
3
Crittografia: cenni storici
Crittografia
“cryptos" = segreto
“grafien” = scrittura
La crittografia tratta i metodi per rendere un messaggio “segreto” in modo
da non essere comprensibile a persone non autorizzate, è una scienza antica
nata dall’esigenza di riservare solo al destinatario la facoltà di comprendere
il significato di un messaggio.
Nel corso della storia la crittografia è stata usata per scopi civili e militari e
oggi assume importanza ancor maggiore con l’espansione delle reti.
Si hanno traccia di applicazioni di crittografia (in special modo sulle
comunicazioni) risalenti persino agli antichi egizi.
Uno dei più antichi cifrari che si conoscano è il "Cifrario di Cesare",
utilizzato dagli imperatori romani e basato sulla trasposizione delle lettere.
4
Crittografia: cenni storici
Codice di Cesare
"… se vi era qualche questione riservata egli usava scrivere in cifra, e questa cifra
consisteva in una disposizione apparentemente caotica delle lettere, sicché era
impossibile ricostruire la parola originale. Chi voglia scoprirne il senso e decifrarla
sappia che bisogna sostituire a ogni lettera la terza che segue nell'alfabeto; vale a dire
dove è scritto A bisogna leggere D e così di seguito." Svetonio - Vita del Divo Giulio
A
B
C
D
E
F
G
H
I
L
M
N
…
D
E
F
G
H
I
L
M
N
O
P
Q
…
Per cifrare: chiave = 3
CADE  FDGH
5
Crittografia: cenni storici
Il cifrario ebraico (ATBASH)
La prima lettera dell'alfabeto ebraico ‘aleph’ viene sostituita con l'ultima ‘taw’
e la seconda ‘beth’ con la penultima ‘shin’. Da qui il nome Atbash.
Esempio: nella Bibbia, Geremia, 25:
“… il re di Sesac”; si tratta invece del re di Babel.
6
Crittografia: cenni storici
Il cifrario Albam (ROT-13)
Ad ogni lettera si sostituisce quella che la segue 13 posti più avanti
nell'alfabeto.
A B C D E F G H I
J
K L M N O P Q R …
|
|
|
| |
|
| |
N O P Q R S
|
|
|
|
|
|
|
|
|
|
T U V W X Y Z A B C D E …
I cifrari Albam e Atbash, sono reversibili, cioè, se sono applicati due (o un
numero pari di) volte di seguito ad un testo, si ottiene il testo originale.
ESERCIZIO
7
Crittografia moderna
Bob
Alice
Carmen
Gli antichi cifrari sono stati sostituiti nel corso della storia dai sistemi
crittografici, ma il problema da risolvere non è cambiato:
Bob e Alice vogliono comunicare in modo “sicuro”
Carmen (l’intrusa) può intercettare, rimuovere o aggiungere messaggi
Carmen vuole modificare, conoscere o impedire la comunicazione
8
Crittografia moderna
Un sistema crittografico è un sistema in grado di cifrare e decifrare un
messaggio attraverso l’uso di un algoritmo e di una chiave (una stringa
alfanumerica). Il messaggio che dovrà essere cifrato viene chiamato testo
in chiaro (plaintext) mentre il risultato dell’algoritmo crittografico testo
cifrato (ciphertext).
Il sistema crittografico deve soddisfare i seguenti requisiti di sicurezza:
 Disponibilità
 Riservatezza
 Integrità
 Autenticazione
 Non ripudiazione
9
Crittografia moderna
Requisiti di disponibilitá: Rendere disponibili a ciascun utente abilitato
le informazioni alle quali ha diritto di accedere, nei tempi e nei modi
previsti.
Requisiti di integrità: Impedire l’alterazione diretta o indiretta delle
informazioni, sia da parte di utenti e processi non autorizzati, che a
seguito di eventi accidentali. Se i dati vengono alterati e’ necessario
fornire strumenti per poterlo verificare facilmente.
10
Crittografia moderna
Requisiti di riservatezza: Nessun utente deve poter ottenere o dedurre
dal sistema informazioni che non è autorizzato a conoscere. Se una
informazione è protetta, o se esiste una comunicazione in atto fra due
utenti o processi in un certo contesto, il sistema non deve permettere di
dedurre informazioni riservate.
Requisiti di autenticazione: Ciascun utente
deve poter verificare
l’autenticità delle informazioni. Si richiede di poter verificare se una
informazione, non necessariamente riservata, e’ stata manipolata.
Requisiti di non ripudiazione: Nessun utente deve
Firmato
e
certificato
poter ripudiare o negare messaggi da lui spediti o
firmati. Questo evita che le informazioni e i messaggi
siano negati dal firmatario in tempi successivi (es.
firma di un contratto)
11
Crittografia moderna
I sistemi crittografici sono di 2 tipi:
 Sistemi crittografici Simmetrici (detti anche a chiave simmetrica o a
chiave segreta)
 Sistemi crittografici Asimmetrici (detti anche a chiave asimmetrica o
a chiave pubblica).
Simmetrici:
 permettono al mittente e al destinatario di usare la medesima chiave;
 l’operazione di decifratura è relativamente semplice nel caso in cui si
conosca la chiave.
Asimmetrici:
 Usano una chiave pubblica e una privata;
 Un messaggio viene cifrato con la chiave privata e decifrato con quella
pubblica;
12
Schema: algoritmi simmetrici
Bob
Alice
I’love
you
I’love
you
Bob
Bob
Carmen
13
DES: Data Encryption Standard (storia)
Il DES nasce nella metà degli anni 70 dai laboratori di ricerca dell’IBM.
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 in modo da favorire
la comunicazione protetta tra le varie organizzazioni governative
statunitensi. Dopo essersi consultata con l'NSA (National Security Agency) il
15 maggio 1972 venne presentata la prima richiesta pubblica di uno standard
di cifratura definito secondo criteri rigorosi.
Nessuno degli algoritmi presentati superò i test dell'NSA e quindi il 27 agosto
1974 fù diramato un secondo bando. L’IBM sottopose come candidato il suo
algoritmo di cifratura sviluppato tra il 1973 e il 1974. Questo algoritmo
chiamato Lucifer fù sviluppato da un team guidato da Horst Feistel e si
basava su una chiave da 128 bit. L'attività di ricerca continuò e la chiave fù
portata da 128 a 56 bit, i risultati raggiunti apparvero in una serie di
pubblicazioni e documenti ufficiali.
14
DES: Data Encryption Standard (storia)
Il 17 marzo 1975, il DES fu pubblicato nel Federal Register. Lo standard
proposto fù subito messo in discussione da Martin Hellman e Whitfield Diffie
che citavano 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, potessero
facilmente leggere messaggi cifrati.
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, "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".
15
DES: Data Encryption Standard (storia)
Nonostante le critiche, il DES fu approvato come standard federale nel
novembre 1976 e pubblicato il 15 gennaio 1977 come FIPS (Federal
Information Processing Standard) PUB 46. È stato in seguito riconfermato
come standard nel 1983, 1988 (riesaminato come FIPS-46-1), 1993 (FIPS-462) e nuovamente nel 1998 (FIPS-46-3), nel quale si introduce il "Triple DES".
Il 26 maggio 2002, il DES è stato finalmente rimpiazzato dall'AES, l'Advanced
Encryption Standard. Ancora oggi, ad ogni modo, il DES è ancora largamente
utilizzato.
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."
16
DES: Data Encryption Standard (storia)
Nel 1990 in seguito alla pubblicazione da parte di Eli Biham e Adi Shamir
della crittanalisi differenziale, un metodo per violare i cifrari a blocchi, si
scoprì che Le S-box del DES erano molto resistenti agli attacchi facendo
fortemente sospettare che l'IBM conoscesse le techiche di crittoanalisi
differenziale già negli anni '70.
Quando nel 1994, furono pubblicati i criteri di progetto originali delle Sbox si capì che l'IBM aveva scoperto la crittanalisi differenziale negli anni
'70 e che dopo aver reso sicuro il DES, gli fu richiesto dalla NSA di
mantenere segreta questa tecnica.
Questo accadde perché la crittanalisi differenziale può essere una
tecnica molto potente usata contro vari schemi e quindi avrebbe potuto
generare problemi di sicurezza nazionale.
17
DES: struttura generale
Il DES codifica blocchi di 64 bit e usa una chiave di 56 bit.
La chiave in realtà è lunga 64 bit ma solo 56 di questi sono effettivamente
utilizzati dall'algoritmo in quanto 8 bit sono utilizzati solo per il controllo
di parità
18
DES: struttura generale
La chiave (k) è memorizzata sfruttando 64 bit, dove l'ottavo, il 16-esimo, ... ,
il 64-esimo, sono i bit di parità per i sette bit precedenti. Possiamo
immaginare i 64 bit della chiave k divisi in 8 byte, dove per ognuno di questi
l'ottavo bit definisce la parità del byte.
Quindi concretamente ci sono solo 56 bit su cui può variare la chiave per un
totale di 256 possibili combinazioni
XOR (0+0=0, 1+0=1, 0+1=1, 1+1=0)
19
DES: struttura generale
permutazione iniziale di 64 bit
le
sedici
iterazioni
che
trasformano la stringa in input
sono uguali nel senso che la
funzione che le realizza è
sempre la stessa (ad ogni
iterazione cambia solo la chiave
utilizzata)
scambia i 32 bit più a sinistra con
quelli più a destra della stringa
prodotta come output alla 16esima iterazione
sfruttando la sola chiave k,
produce le chiavi k1, k2, ...,
k16 di 48 bit ciascuna, per
le iterazioni da 1 a 16.
20
DES: Permutazione IP
Sia x un testo in chiaro di 64 bit: l'algoritmo costruisce una stringa binaria
permutando la stringa iniziale mediante la permutazione iniziale fissata IP
Il primo valore della tabella specifica che il
primo bit della stringa permutata IP(x) è il 58esimo bit della stringa da permutare x; il
secondo elemento della tabella, 50, ne
specifica il secondo e così via.
58
50
bit iniziali
1 2
...
58
60
62
64
57
59
61
63
50
52
54
56
49
51
53
55
42
44
46
48
41
43
45
47
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
bit permutati
64
21
DES: permutazione inversa IP-1
Passo 3: L'output dell'algoritmo è ottenuto applicando la permutazione IP-1 a
R16L16. Si noti l'ordine inverso delle ultime due stringhe di bit R16 e L16 dovuto
allo scambio di 32 bit
Questa tabella si legge nello stesso modo della
precedente. Queste permutazioni sono solo una
scelta dello standard, potremmo infatti fare a
meno della permutazione iniziale e finale senza
perdere in sicurezza.
40
8
bit iniziali
1 2
...
40
39
38
37
36
35
34
33
8
7
6
5
4
3
2
1
48
47
46
45
44
43
42
41
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
bit permutati
64
22
DES: iterazioni
Il DES effettua 16 iterazioni. Per 1  i  16 l'input della i-esima iterazione è
una stringa di 64 bit divisa in due parti, Li-1 e Ri-1, ognuna di 32 bit (chiamate
rispettivamente parte sinistra e parte destra della stringa). I valori di output Li
e Ri sono prodotti in base alla seguente regola: Li=Ri-1 e Ri=Li-1 f(Ri-1 , ki)
L'operatore  denota la
funzione xor bit a bit delle
due stringhe, ed f è una
funzione che, data la
chiave ki e la sottostringa
Ri-1 , produce una stringa
lunga 32 bit.
k1, k2, ..., k16 sono le chiavi
prodotte dal processo di
schedulazione. All'i-esima
iterazione verrà usata la
sola chiave ki.
parte sinistra
parte destra
32 bit
32 bit
LLi-i-11
RRi-i-11
sottochiave
48 bit
ff
LLii
RRii
kkii
singola iterazione
23
DES: funzione di Feistel
La funzione f prende in input una stringa A di 32 bit, una stringa K di 48 bit, e
fornisce in output una stringa di 32 bit.
La stringa A di 32 bit viene espansa
dalla funzione E in una stringa 48
A
bit. Viene computato lo xor bit a
bit
EE
J tra K e E(A), che è una stringa di
K
48 bit. La sequenza viene divisa in
48 bit
E(A) 48 bit
8 sottosequenze di 6 bit ciascuna,
dette sottosequenze B1, B2, ..., B8.
B1 B2 B3 B4 B5 B6 B7 B8
S1
S1 S2
S2 S3
S3 S4
S4 S5
S5 S6
S6 S7
S7 S8
S8
C1 C2 C3 C4 C5 C6 C7 C8
PP
32 bit
L'S-box Si (per 1  i  8) prende in
input Bi (a 6 bit) e da in output una
sequenza a 4 bit, che chiamiamo Ci.
La stringa C1,C2,...,C8 (a 32 bit)
viene
permutata
tramite
la
permutazione P e questo è il valore
f(A, K).
24
Espansione (E) e permutazione (P)
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
La funzione E duplica e permuta 16 bit dei 32 di A
in base allo schema della tabella E
32
12
bit iniziali
bit dopo espansione
1 2 3
...
48
Tabella E
La tabella P specifica la permutazione P
Tabella P
25
DES: S-BOX
L'unico punto in cui il sistema DES non utilizza funzioni di tipo lineare (cioè
gli xor, le permutazioni e le espansioni) è nelle S-box, che costituiscono il
fulcro dell'algoritmo.
00
01
10
11
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 0110 0111 1111
14
4
13
1
2
15
11
8
3
10
6
12
5
9
0
7
0
15
7
4
14
2
13
1
10
6
12
11
9
5
3
8
4
1
7
8
13
6
2
11
15
12
9
7
3
10
5
0
15
12
10
2
4
9
1
7
5
11
3
14
10
0
6
13
S-BOX S1
Dato Bi (l'input a 6 bit dell‘S-box Si), il primo e l'ultimo bit di Bi vengono
interpretati come indice di riga, mentre i bit centrali come indice di colonna.
Si consulta la tabella Si alle coordinate prescritte e il valore trovato nell'Sbox è un decimale la cui conversione binaria dà i 4 bit output
26
DES: S-BOX (esempio)
primo ed ultimo bit
Input B1 = 101110
10
00
01
10
11
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 0110 0111 1111
14
4
13
1
2
15
11
8
3
10
6
12
5
9
0
7
0
15
7
4
14
2
13
1
10
6
12
11
9
5
3
8
4
1
7
8
13
6
2
11
15
12
9
7
3
10
5
0
15
12
10
2
4
9
1
7
5
11
3
14
10
0
6
13
Box S1
output S1= 11 ---> in binario = 1011
27
DES: proprietà delle S-box
I criteri di progettazione delle S-box non sono completamente noti. Si
conoscono solo alcune proprietà:
Ogni riga è una permutazione degli interi 0,..,15
Nessuna S-box è una funzione affine o lineare dei suoi input
Cambiando un solo bit di input ad una S-box variano almeno due bit
nell'output
Per ogni S-box S e per ogni input x a 6 bit:
differiscono in almeno due bit
S(x)
e
S(x001100)
Per ogni S-box, per ogni input x e per ogni bit d,g, S(x)  S(x11dg00)
Per ogni S-box, se fissiamo un bit di input e osserviamo il valore di un
fissato bit di output, il numero degli input per i quali il bit di output vale
0 è circa uguale al numero degli input per i quali tale bit vale 1
Verificare per esercizio queste proprietà sulla S-BOX S1
28
DES: schedulazione delle chiavi
Le chiavi usate durante i vari round sono ricavate dalla chiave k di 64 bit
escludendo gli 8 bit utilizzati per il controllo di parità e permutando i
rimanenti 56 bit tramite la permutazione PC1 che calcolerà PC1(k) = C0D0
dove C0 e D0 sono i primi e gli ultimi 28 bit di PC1(k).
chiave k
Sia Per 1  i  16 computiamo
PC1
PC1
Ci = LSi(Ci-1);
Di = LSi(Di-1);
C0
D0
Ki = PC2(CiDi)
LS
LS11
LS
LS11
C1
D1
LSi è uno shift ciclico a sinistra
di una o due posizioni a
seconda del valore di i.
PC2 infine è una compressione
di una stringa di input a
56 bit, in una stringa di
output a 48 bit.
48 bit
k1
..
.
48 bit
k16
PC2
PC2
PC2
PC2
56 bit
..
.
56 bit
..
.
LS
LS1616
LS
LS1616
C16
D16
29
Permutazione PC1
57 49 41 33 25
10 2 59 51 43
63 55 47 39 31
14 6 61 53 45
17 9 1
35 27 19
23 15 7
37 29 21
58 50 42 34 26 18
11 3 60 52 44 36
62 54 46 38 30 22
13 5 28 20 12 4
I bit in posizione 8, 16, 24, 32, 40, 48, 56, 64 sono di parità e non
compaiono, essi servono per rivelare un errore in ogni byte.
1
57
64
bit iniziali
bit dopo permutazione
1 2 3
...
56
30
La funzione shift a sinistra LSi
iterazione
shift
1
1
2
1
3
2
4
2
5
2
6
2
7
2
8
2
9 10 11 12 13 14 15 16
1 2 2 2 2 2 2 1
chiave k
PC1
PC1
Lo shift LSi riguarda una sola
posizione alle iterazioni 1, 2, 9 e 16,
e due posizioni a tutte le altre
iterazioni
48 bit
k1
Totale shift nelle 16 iterazioni = 28
posizioni
..
.
48 bit
k16
PC2
PC2
PC2
PC2
56 bit
..
.
56 bit
C0
D0
LS
LS11
LS
LS11
C1
D1
..
.
LS
LS1616
LS
LS1616
C16
D16
31
Compressione-permutazione PC2
14 17 11 24 1 5 3 28 15 6 21 10 23 19 12 4
26 8 16 7 27 20 13 26 41 52 31 37 47 55 30 40
51 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32
8 bit soppressi in posizione 9, 18, 22, 25, 35, 38, 43 e 54
1
14
56
bit iniziali
bit dopo compressione
1 2 3
...
48
32
Decifratura del DES
testo cifrato
Per decifrare si usa lo stesso algoritmo e la stessa
chiave K usati per cifrare, eccezion fatta per la
schedulazione delle chiavi ad ogni round, che è
invertita.
IP
iterazione 1
Chiave k
k16
schedulazione
chiave
...
iterazione 16
k1
scambio
IP -1
ESERCIZIO
33
Modalità del DES: ECB
l'ECB (Electronic Codebook chaining).
Un messaggio in chiaro x1x2…xn, dove ogni xi rappresenta un blocco di 64 bit)
viene cifrato applicando ripetutamente ad ogni blocco xi l'algoritmo DES,
sempre con la stessa chiave k, producendo un testo cifrato y1y2…yn.
Quindi i valori dei blocchi yi sono dati da: yi = DESk(xi)
34
Modalità del DES: ECB
L'unico problema con questo metodo si ha quando il messaggio è costituito da
un numero di bit che non è un multiplo di 64, cioè quando l'ultimo blocco
non contiene esattamente 64 bit, ma di meno. La soluzione per questo caso
non è definita dallo standard, ma bisogna convenire su come risolverlo.
L'idea potrebbe essere quella di inserire del testo opportuno alla fine del
blocco, in modo tale che, in fase di decifratura, possa essere semplice
distinguere il testo aggiunto da quello originale.
Una possibile soluzione è quella di aggiungere al messaggio originale la
sequenza 100...0, in modo da completare l'ultimo blocco a 64 bit.
Naturalmente, questa operazione deve essere fatta anche quando l'ultimo
blocco è già di 64 bit, in modo da stabilire un criterio generale.
Questo significa che, in fase di decifratura si sa con certezza che la stringa
finale del messaggio decifrato, cioè la stringa 100...0, è stata aggiunta in fase
di cifratura, e quindi non viene considerata come facente parte del
messaggio originario.
35
Modalità del DES: ECB
L'operazione di decifratura considera un blocco alla volta del messaggio, così
come accadeva per la cifratura, applicando però in questo caso l'algoritmo di
decifratura DES.
Il vantaggio di questo metodo sta nella
sua rapidità di esecuzione.
Lo svantaggio è dato dal fatto che,
durante la trasmissione del messaggio,
potrebbe verificarsi sia la perdita di un
blocco che l'attacco da parte di un
nemico.
In particolare, quest'ultimo potrebbe
sostituire un blocco con un altro, senza
la possibilità che colui che riceve il
messaggio possa accorgersene.
Per esempio egli potrebbe cambiare in
un messaggio il blocco "do" con "do not"
senza essere scoperto. Questo è dovuto
alla mancanza di dipendenza tra i vari
blocchi
36
Modalità del DES: CBC
CBC (Cipher Block Chaining)
Dato un messaggio in chiaro x1x2 ...xn ed una chiave nascosta k, in questa
modalità un generico yi è dato da:
yi = DESk(yi-1  xi), 1  i  n
con y0 = IV(vettore di inizializzazione a 64 bit).



Quest'ultimo
Il procedimento
vienedipoi
cifratura
utilizzato
considera
per fare
inizialmente
lo xor bit ail bit
vettore
col blocco
IV, di successivo
64 bit, quindi
del
messaggio
effettua lo
in xor
chiaro
bit ax2bit
, quindi
tra questi
si applica
ed i primi
alla 64
stringa
bit del
cosìmessaggio
ottenuta inl'algoritmo
chiaro, infine
DES
sempre
applicacon
alla la
stringa
stessacosì
chiave
ottenuta
k, ottenendo
l'algoritmoil diblocco
cifratura
cifrato
DES ycon
così via.
k, ottenendo
Con questo
il
2 e chiave
metodo,
blocco cifrato
si definisce
y1. in qualche modo un legame tra yi ed il blocco precedente yi-1.
37
Modalità del DES: CBC
Per decifrare operiamo all'inverso del caso della cifratura, cioè si applica y1
come input del DES-1 (algoritmo di decifratura) con la stessa chiave k,
ottenendo quindi la stringa che precedentemente definiva lo xor bit a bit tra
x1 ed IV, che costituiva l'input del DES. Ora poiché si vuole calcolare x1 si
effettua l'operazione inversa, cioè lo xor bit a bit del valore in output del DES1 con IV e ottenendo x1. In generale quindi:
xi = yi-1  DESk-1(yi) per 1  i  n
Il vantaggio di questo schema è che se si
cambia un solo bit del messaggio
originario cambia di conseguenza anche
la parte rimanente del messaggio.
Questa
caratteristica
elimina
la
possibilità di un attacco tramite
sostituzione di un blocco. Infatti, in una
tale evenienza il messaggio sarebbe
irrimediabilmente compromesso.
Lo svantaggio di tale metodo è che in
esso vengono eseguite più operazioni
rispetto all'ECB, e quindi rispetto ad esso
è più lento.
38
Modalità del DES: CFB
CFB (Cipher Feedback)
In questa modalità viene fornito un vettore di inizializzazione IV, che è una
stringa di 64 bit. Sia x1x2…xn il messaggio in chiaro. Allora il generico yi è
definito da:
yi = xi  DESk (yi-1) con 1  i  n
39
Modalità del DES: CFB j-bit
Esiste una versione più generale detta Cipher Feedback con j bit. Per essa si
considera inizialmente una stringa di 64 bit (costituita dal vettore IV), che si
può immaginare suddivisa in due parti, di 64-j bit a sinistra e j bit a destra.
Quindi si cifra tale stringa usando l'algoritmo di cifratura DES con chiave k.
Della stringa cifrata così ottenuta vengono considerati solo i j bit più a sinistra. Quindi
Adsiogni
passo,
bit adel
in chiaro
j bit
deldel
testo
cifrato.in chiaro,
effettua
lo da
xorj bit
bittesto
tra questi
j bit otteniamo
ed i prossimi
j bit
messaggio
ottenendo j bit del messaggio cifrato. Tali j bit così definiti rientrano nel circuito, in
quanto al passo successivo il vettore originale di 64 bit viene shiftato di j posizioni a
sinistra, e gli ultimi j bit di tale vettore diventano i j bit del messaggio cifrato.
40
Modalità del DES: CFB j-bit
La decifratura avviene in maniera analoga alla cifratura. E’ importante
osservare che per la decifratura viene usato ancora l’algoritmo DES e non il
DES-1.
L'unica variante significativa in tale schema è data dal fatto che i j bit del
messaggio cifrato, vengono utilizzati per effettuare lo xor bit a bit con i j bit
più a sinistra dell'output del DES, oltre a costituire in seguito i nuovi j bit più
a destra del vettore iniziale (su cui viene applicato l'algoritmo DES),
definendo così j bit del messaggio in chiaro.
Il vantaggio di questo schema è dato dal fatto che
il valore di j può essere scelto a piacimento.
Per esempio alcune applicazioni scelgono j = 8,
che significa cifrare 8 bit (1 byte) alla volta del
messaggio in chiaro. Questa scelta si presta
particolarmente alla cifratura on-line; infatti con
j = 8 può essere trasmesso un carattere alla
volta.
Lo svantaggio di questo metodo è che per valori
di j piccoli esso diventa sicuramente più oneroso
di quelli visti in precedenza.
41
Modalità del DES:
Output Feedback
Anche in questa modalità si utilizza una stringa iniziale di 64 bit (vettore IV).
Come primo passo viene costruita la sequenza: z0z1z2z3…. dove z0 = IV e zi =
DESk(zi-1) con chiave k segreta.
Come si può notare tale stringa è del tutto indipendente dal messaggio in
chiaro. Quindi sia x1x2...xn il messaggio in chiaro; il messaggio cifrato è
definito da y1y2…yn dove: yi = xi  zi
Anche per tale metodo c'è la variante
a j bit, che è analoga a quella del
CFB, l'unica diversità sta nel fatto che
il feed-back (cioè il riutilizzo di una
certa parte dell'informazione) non
riguarda j bit del testo cifrato, ma i j
bit più a sinistra della stringa in
output prodotta dal DES.
42
Modalità del DES:
Output Feedback
Per la decifratura si può notare che la prima parte del metodo è uguale a
quello che viene utilizzata per effettuare la cifratura (ciò è valido dal
momento che la sequenza del messaggio in chiaro generata da questa prima
parte è indipendente dal messaggio in chiaro, così come dal messaggio
cifrato).
Quindi, ad ogni passo si considerano i j bit più a sinistra delle stringhe fornite
in output dall'algoritmo DES, e si effettua lo xor bit a bit con j bit del
messaggio cifrato, ottenendo così j bit del messaggio in chiaro.
ESERCIZIO
43
Applicazioni del DES
L'algoritmo DES può essere usato come standard sia per la cifratura che per
l'autenticazione dei dati.
Cifratura Dati: è semplice vedere come il DES può essere usato per cifrare
un testo in chiaro di 64 bit, tuttavia la lunghezza dei testi è raramente
limitata a 64 bit. Per testi più lunghi possono essere utilizzate le modalità di
operative viste in precedenza. Ognuna di tali modalità ha vantaggi e
svantaggi.
Per esempio l'ECB è eccellente per la cifratura delle chiavi; CFB è usato
tipicamente per cifrare caratteri individuali; OFB è tipicamente usato per
cifrare comunicazioni via satellite (in cui è necessario ridurre al minimo la
possibilità di errori alla stazione ricevente); ed infine entrambi CBC e CFB
possono essere usati per l'autenticazione di dati.
Tuttavia per essi non esistono delle analisi formali che dimostrino qual'è il
più sicuro, a meno che non si faccia uso di ipotesi molto restrittive.
44
Applicazioni del DES
Autenticazione Dati: Originariamente il DES fu introdotto per permettere la
cifratura e la decifratura di dati usati sul computer. Tuttavia la sua
applicazione si è estesa anche alla autenticazione dei dati.
Tale necessità è nata dalla difficoltà di riconoscere se in un messaggio c'erano
state delle modifiche o meno, durante la fase di trasmissione. Più in
particolare, nel caso in cui i dati erano cifrati con una delle due modalità CFB
o CBC, allora queste possono essere usate per produrre un Codice di
Autenticazione del Messaggio (MAC).
Il MAC viene posto alla fine del messaggio in chiaro, ed è usato per
convincere chi riceve il messaggio che esso non è stato alterato da nessuno.
Così il MAC garantisce l'integrità (o autenticità) del messaggio (ma non la sua
segretezza).
45
Applicazioni del DES: MAC
La modalità di operazione CBC viene usata per produrre un MAC (Message
Authentication Code) nel seguente modo:
x1,x2,…xn,yn
Bob
Alice
x1,x2,…xn,yn
x1,x2,…xn
y1,y2,…yn
MAC= yn
Carmen
Si noti che un nemico che vuole attaccare il sistema non può
produrre un MAC valido poiché non conosce la chiave di
cifratura. Quindi se Carmen intercetta il messaggio x1,x2...
xn,yn e cambia uno o più bit di tale messaggio, è altamente
improbabile che riesca a cambiare anche il MAC evitando che
Bob si accorga delle modifiche.
x1,x2,…xn
y1,y2,…yn
y
n
46
Applicazioni del DES
Cifratura ed Autenticazione dei Dati: è spesso desiderabile combinare
autenticità e segretezza. Questo potrebbe essere fatto usando due chiavi:
Bob
Alice
x1,x2,…xn,yn
x1,x2,…xn
y1,y2,…yn
MAC= yn
x1,x2,…xn,yn
Carmen
x1,x2,…xn
y1,y2,…yn
y
n
47
Applicazioni del DES
Trasferimento Elettronico di Fondi (EFT) (ANSI X9.9): probabilmente
l'uso più significativo del DES è quello riguardante la protezione dei messaggi
di trasferimento, relativi a vendite al dettaglio ed all'ingrosso. I dati protetti
tramite DES sono relativi a trasferimenti di fondi che variano da $50 a
svariati milioni di dollari.
In particolare il governo degli Stati Uniti è responsabile di trasferimenti di
miliardi di dollari al giorno. Per far sì che questi trasferimenti siano sicuri, il
Dipartimento del Tesoro Americano ha dato inizio alla politica
precedentemente citata sull'autenticazione dei messaggi EFT.
Anche la Banca federale coopera con il Tesoro per la buona riuscita di queste
operazioni. Uno dei sistemi che si sta considerando consiste di strumenti
manuali contenenti chiavi DES usati nella cifratura di messaggi finanziari.
Questi strumenti forniscono la chiave per l'autenticazione delle firme di
documenti cartacei.
48
Applicazioni del DES
Immagazzinamento Dati e Sistemi di Posta (ANSI X9.19): il DES viene
utilizzato per la cifratura di password per l'accesso a sistemi computerizzati.
L'algoritmo confronta la cifratura della stringa data in input come password
con quella conservata in memoria, ed attiva o nega l'accesso al sistema a
seconda che il match fra le due stringhe abbia o meno esito positivo.
Il DES può anche essere utilizzato per la protezione di file in memoria. Una
pubblicazione speciale dell'NBS descrive un sistema di notarizzazione di
chiavi che può essere integrato in un sistema computerizzato, per
proteggere file da modifiche e divulgazioni e per provvedere a una firma
digitale usando il DES.
Il sistema di notarizzazione che incorpora il DES può anche essere usato
congiunto ad un sistema di posta per provvedere della posta sicura. Un
software di cifratura/decifratura che contiene le informazioni necessarie a
decifrare ed autenticare un file di posta è automaticamente aggiunto al file
che è trasmesso al ricevente. Quest'ultimo in seguito potrà decifrare ed
autenticare il file facilmente sfruttando quest'informazione.
49
DES: Crittoanalisi
“La sicurezza di un sistema crittografico deve dipendere solo dalla
segretezza della chiave e non dalla segretezza del metodo”
Auguste Kerckhoffs von Nieuwenhof (1835-1903)
Per poter comprendere meglio l’aspetto della sicurezza di un sistema
crittografico dobbiamo metterci nei panni della «spia» che intercetta il
messaggio. La spia cercherà di decrittare (questo è il termine esatto) il
messaggio e quindi dovrà conoscere l’algoritmo utilizzato per la cifratura e
la chiave. Un principio fondamentale della crittologia moderna afferma che:
La sicurezza di un crittosistema non deve dipendere dalla segretezza
dell’algoritmo usato, ma solo dalla segretezza della chiave
Questo principio, apparso per la prima volta nel 1883 nel libro «La
criptographie militarie» di Kerckhoffs un filologo olandese, è fondamentale
per una corretta visione del problema sicurezza.
50
DES: Crittoanalisi
Un primo semplice attacco è quello di forza bruta: provare tutte le possibili
chiavi. La lunghezza della chiave determina il numero di chiavi possibili e
quindi la fattibilità dell'attacco.
Lo spazio delle chiavi del DES è formato da 256 elementi, che in notazione
decimale equivale a circa 72 milioni di miliardi di combinazioni distinte, per
cui un ipotetico computer a 500 MHz che può sondare una chiave ad ogni ciclo
di clock impiegherebbe 144 milioni di secondi ad esaminarle tutte.
Tuttavia, a dispetto delle 256 chiavi possibili, in media bastano 255 tentativi.
Questo consegue dalla proprietà di complementazione del DES:
C = DESK(M) allora ¬C = DES¬K(¬M).
Ma anche supponendo che sia sufficiente
esaminare solo la metà delle chiavi
occorrerebbero comunque ben 834 giorni,
pari a 2 anni e 3 mesi di lavoro
continuativo!
51
DES: Crittoanalisi
A livello teorico, furono avanzate varie proposte per un computer in grado di
violare il DES.
Nel 1977, Diffie ed 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-Crack dall‘ Electronic Frontier Foundation
(EFF), un gruppo per la difesa dei diritti civili nel ciberspazio, del costo di
circa 250.0000 dollari. Fu costruita per dimostrare che il DES era violabile in
pratica, non solo in teoria. Questa macchina violò con la sola forza bruta una
chiave in pochi giorni di ricerca.
Inoltre è stata pubblicata la documentazione completa del progetto DES-Crack
in modo da consentire ad altri gruppi di scienziati di riprodurre e di
migliorare la macchina realizzata dall'EFF.
52
DES: Crittoanalisi
Il miglior attacco al DES conosciuto è senza dubbio quello definito dal metodo
della Crittoanalisi differenziale, introdotto da E. Biham e A. Shamir.
Esso defininisce un attacco 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.
Per violare tutti i 16 cicli,
la crittanalisi differenziale
richiede 247 testi in chiaro
scelti (chosen plaintext)
ESERCIZIO
53
Weak-Key
Tra le 256 chiavi possibili ve ne sono di particolari per le quali le sottochiavi
prodotte dalla fase di schedulazione sono tutte uguali. Queste chiavi sono
dette weak key (chiavi deboli). Quindi se cifriamo un testo cifrato con una
weak key otteniamo il testo in chiaro.
Questo succede perché, visto che le sottochiavi prodotte dal processo di
schedulazione sono le stesse sia nel caso della cifratura che della decifratura,
queste due operazioni coincidono.
Le weak key sono quelle
composte da tutti 0, tutti 1,
oppure da una metà da tutti 0
e l'altra da tutti 1.
Tali chiavi diminuiscono la
sicurezza del sistema in quanto
basta
trovare
una
sola
sottochiave ki per scoprire
tutte le altre.
Le quattro weak key in rappresentazione esadecimale
54
Critiche al DES
 L'algoritmo di per sé è molto semplice e tutte le funzioni sono funzioni
lineari (gli xor e le permutazioni) tranne le S-box, esse infatti rispondono a dei
criteri che non sono completamente noti, ed è per questo che si teme che
l'NSA abbia nascosto in esse delle trapdoor in modo tale da poter decifrare
facilmente messaggi intercettati.
 Perché solo 16 iterazioni e non 24 o 32? Fu dimostrato che con 8
iterazioni, il testo cifrato era una funzione random di ogni bit del testo in
chiaro e di ogni bit della chiave. Perché allora non fermare DES dopo 8
iterazioni? E. Biham e A. Shamir hanno dimostrato nel 1990 che con meno di
16 iterazioni si può rompere il DES con un attacco più efficiente di un attacco
brute force che esamina 256 chiavi. Con 16 iterazioni i due attacchi sono
equivalenti.
 La maggiore critica al DES è che la dimensione delle chiavi, 256, è troppo
piccolo per essere realmente sicuro. Ci si chiede quindi: perché DES usa una
chiave a 56 bit mentre LUCIFER ne usava 128? Un attacco brute force su una
chiave a 128 bit non è nemmeno immaginabile mentre sono noti attacchi brute
force con chiave a 64 bit.
55
Esercizi
Siano x1…xn n blocchi di 64 bit e siano y1…yn gli n blocchi ottenuti cifrando
x1…xn con DES. Si supponga che a causa di un errore di trasmissione, il
blocco y1 non sia trasmesso correttamente (alcuni 0 diventano 1 o
viceversa). Analizzare quanti e quali blocchi sono decifrati non
correttamente se la modalità operativa utilizzata per la cifratura è:
a. ECB
b. CBC
c. CFB
d. OFB
Soluzione: per le modalità ECB e OFB, soltanto il primo blocco sarà decifrato
non correttamente; per le modalità CBC e CFB, i primi due blocchi saranno
decifrati non correttamente.
56
Electronic codebook chaining (ECB)
cifratura
x
1
DES
y1
x2
xn
DES
…
DES
y2
yn
Non corretto
y1
decifratura
DES
-1
x1
Non corretto
y2
DES
yn
-1
…
DES
x2
-1
xn
corretti
57
Cipher Block Chaining CBC
cifratura
x1
x2
IV
k
Non corretto
decifratura
k
…
DES
k
y1
y2
y1
y2
DES-1
k
x1
k
DES
DES-1
IV
Non corretti
xn
…
DES
yn
yn
…
k
…
x2
DES-1
xn
corretti
58
Cipher feedback CFB
cifratura
IV
x1
x2
DES
y1 DES
k
k
Non corretto
decifratura y1
IV
y2 …
x1 DES
k
k
yn
DES
k
y2
DES
Non corretti
xn
yn
x2 …
DES
xn
k
corretti
59
64-bit Output feedback
shift di 64 bit
k
64 bit del
testo
in chiaro
shift di 64 bit
k
DES
64 bit testo cifrato
Cifratura
y1 non corretto
DES
64 bit del
testo
in chiaro
64 bit testo cifrato
Decifratura
x 1 x 2 … xn
non corretto
corretti
60
Esercizi
Si consideri il crittosistema DES. E’ possibile utilizzare la proprietà del
complemento per migliorare il running time della ricerca esaustiva in un
attacco known plaintext? E in un attacco chosen plaintext? Giustificare le
risposte.
Soluzione: Non è noto come sia possibile utilizzare la proprietà del
complemento per migliorare il running time della ricerca esaustiva in un
attacco known plaintext.
Invece, tale proprietà consente il miglioramento del running time della
ricerca esaustiva di un fattore ½ nel caso di un attacco chosen plaintext.
Infatti, supponiamo che k sia la chiave segreta da trovare. In un attacco
chosen plaintext, si considerino due coppie (m, c1) e (m’, c2), dove m’ indica
il complemento di m. Per la proprietà del complemento, per ogni possibile
chiave h si ha c=DES(h,m) e c’=DES(h’,m’), dove c’ e h’ indicano il
complemento di c e h, rispettivamente. Pertanto, se cc1, allora kh e se
c’c2 allora kh’. Quindi le due chiavi candidate h e h’ possono essere
eliminate mediante una singola cifratura DES durante la ricerca esaustiva.
61
Esercizi
Dimostrare che la decifratura DES può essere effettuata applicando
l’algoritmo di cifratura DES al testo cifrato con le chiavi schedulate in ordine
inverso.
Soluzione: Nella fase di cifratura DES dopo avere effettuato lo scambio di 32
bit successivo alla sedicesima iterazione, abbiamo la stringa di 64 bit R16L16,
dove
L16= R15
R16=L15  f(R15,k16)
da cui otteniamo:
R15= L16
L15=R16  f(R15,k16) = R16  f(L16,k16).
Quindi dalla stringa R16L16 possiamo risalire alla stringa R15L15 utilizzando la
sottochiave k16. Questo è vero per tutte le iterazioni, quindi utilizzando lo
stesso algoritmo di cifratura DES, con le sottochiavi schedulate in ordine
inverso, possiamo effettuare la decifratura DES.
62