Funzioni di hash sicure: MD5 e SHA-1
POLITECNICO
DI MILANO
Funzioni di hash sicure:
MD5 e SHA-1
Davide Cerri
CEFRIEL - Politecnico di Milano
[email protected]
http://www.cefriel.it/~cerri/
Funzioni di hash
Una funzione di hash (o message digest) è una
funzione H che, dato un input M di dimensione
qualsiasi, produce un output h (l’hash) di
dimensione fissa:
fissa
h = H(M)
Lo scopo di una funzione di hash è di creare
un’impronta
impronta (fingerprint) del messaggio.
Dato che l’output ha lunghezza fissa (in genere
dell’ordine di una o poche centinaia di bit),
esisteranno necessariamente diversi messaggi che
generano lo stesso hash... ma non è detto che si
riesca a trovarli...
Funzioni di hash sicure: MD5 e SHASHA-1
Davide Cerri
-2-
Davide Cerri
1
Funzioni di hash sicure: MD5 e SHA-1
Unidirezionalità
Una funzione di hash sicura deve essere
unidirezionale (one-way), cioè:
dato un qualsiasi M, deve essere computazionalmente
semplice calcolare H(M);
dato un qualsiasi h, deve essere computazionalmente
impraticabile calcolare un M tale che h = H(M);
L’idea è che l’hash di un messaggio sia in sostanza
una corrispondenza pseudocasuale, per cui non è
possibile prevedere in alcun modo il risultato se non
calcolando l’hash.
Messaggi diversi, anche per un solo bit, devono
generare hash non correlati.
correlati
Funzioni di hash sicure: MD5 e SHASHA-1
-3-
Davide Cerri
Assenza di collisioni (1)
Una funzione di hash sicura deve essere senza
collisioni (collision-resistant):
dato un qualsiasi M, deve essere computazionalmente
impraticabile trovare un M’≠ M tale che H(M’) = H(M)
(funzione debolmente senza collisioni);
collisioni
deve essere computazionalmente impraticabile
trovare una coppia (M, M’), con M’≠ M, tale che
H(M) = H(M’) (funzione fortemente senza collisioni).
collisioni
L’idea è che, anche se necessariamente esistono
messaggi diversi che producono lo stesso hash, non
è praticabile trovarli.
Funzioni di hash sicure: MD5 e SHASHA-1
Davide Cerri
-4-
Davide Cerri
2
Funzioni di hash sicure: MD5 e SHA-1
Assenza di collisioni (2)
Le due proprietà sull’assenza di collisioni (debole e
forte), corrispondono a due diversi tipi di attacchi a
forza bruta:
attacco a forza bruta “semplice”:
“semplice” trovare un
messaggio che produca un dato hash (cioè un hash
uguale a quello di un messaggio dato);
attacco del compleanno (birthday attack): trovare
due messaggi che producano lo stesso hash,
indipendentemente dal valore di questo hash.
La complessità dei due attacchi è molto diversa!
se l’hash è lungo m bit, la complessità del primo è 2m,
quella del secondo è 2m/2.
Funzioni di hash sicure: MD5 e SHASHA-1
-5-
Davide Cerri
Che cosa NON è un hash
Un hash non è né una firma né un MAC (Message
Authentication Code), di per sè non garantisce
autenticazione e/o integrità.
Nel calcolo di un hash non si inserisce nessuna
informazione segreta, per cui chiunque può generare
l’hash corretto di qualunque messaggio.
Una funzione di hash non è un algoritmo di
cifratura.
cifratura
Calcolare l’hash di un messaggio non equivale a
cifrarlo: il calcolo di un hash non include nessuna
chiave, e soprattutto è un’operazione non
invertibile.
invertibile
Funzioni di hash sicure: MD5 e SHASHA-1
Davide Cerri
-6-
Davide Cerri
3
Funzioni di hash sicure: MD5 e SHA-1
MD5 e SHA-1
Le due funzioni di hash sicure attualmente più
diffuse sono MD5 e SHASHA-1, che hanno una struttura
simile.
messaggio (+ padding)
costante
hash
512 bit
hash
512 bit
hash
512 bit
message digest
Funzioni di hash sicure: MD5 e SHASHA-1
-7-
Davide Cerri
MD5
MD5 (Message Digest 5) è stato progettato da Ron
Rivest, ed è definito in RFC 1321 (1992).
Il messaggio viene elaborato a blocchi di 512 bit.
L’hash è di 128 bit.
bit
Ad ogni iterazione si calcola una funzione che
prende in ingresso il blocco corrente del messaggio
e il valore dell’hash all’iterazione precedente.
L’hash finale è quello risultante dall’ultima
iterazione.
Non è più considerato molto sicuro (128 bit di hash
non sono molti).
Funzioni di hash sicure: MD5 e SHASHA-1
Davide Cerri
-8-
Davide Cerri
4
Funzioni di hash sicure: MD5 e SHA-1
MD5: padding
Prima di iniziare l’elaborazione, si aggiunge al
messaggio un padding in modo che la lunghezza
totale risulti un multiplo di 512 bit:
si aggiunge un bit a 1 e poi tanti bit a 0 quanto basta
perché la lunghezza risulti di 64 bit minore rispetto a
un multiplo di 512 bit (se la lunghezza originale è già
corretta si aggiungono comunque 512 bit);
si aggiungono 64 bit contenenti la lunghezza originale
del messaggio (modulo 264). 1-512 bit
64 bit
messaggio originale
1000............0 lunghezza
multiplo di 512 bit
Funzioni di hash sicure: MD5 e SHASHA-1
-9-
Davide Cerri
Elaborazione MD5 (1)
Un’iterazione MD5 (cioè l’elaborazione su un blocco
del messaggio) è composta da 4 passi.
passi
Indichiamo con:
di: i-esima parola (32 bit) del digest (i=0-3);
mi: i-esima parola di un blocco di messaggio (i=0-15);
Ti = 232 sen i , (i=1-64);
↵x: rotazione sinistra di x posizioni (su 32 bit);
+: somma modulo 232;
∧, ∨, ∼, ⊕: rispettivamente AND, OR, NOT, XOR
(calcolati bit a bit).
Funzioni di hash sicure: MD5 e SHASHA-1
Davide Cerri
- 10 -
Davide Cerri
5
Funzioni di hash sicure: MD5 e SHA-1
Elaborazione MD5 (2)
Il valore del digest viene così inizializzato:
inizializzato
d0 = 0x67452301, d1 = 0xEFCDAB89,
d2 = 0x98BADCFE, d3 = 0x10325476.
Ogni passo prende in ingresso il valore corrente del
digest e il blocco corrente del messaggio,
messaggio e
modifica (fornendolo in uscita) il valore corrente del
digest.
Il valore del digest in uscita dal quarto passo viene
poi sommato (indipendentemente per le 4 parole
d0, d1, d2, d3) al valore di ingresso al primo passo
dell’iterazione corrente; il risultato è il valore di
uscita dell’iterazione.
Funzioni di hash sicure: MD5 e SHASHA-1
- 11 -
Davide Cerri
Elaborazione MD5 (3)
Ogni passo è composto da 16 operazioni.
operazioni
La i-esima (i=0-15) operazione ha la forma:
d(-i) mod 4 = d(1-i) mod 4 + (d(-i) mod 4 + fp(d(1-i) mod 4 ,
d(2-i) mod 4 , d(3-i) mod 4) + mj + Tk)↵Sp(i mod 4)
ogni operazione:
aggiorna uno dei 4 blocchi del digest (in ogni passo
ogni blocco del digest viene aggiornato 4 volte);
utilizza uno dei 16 blocchi del messaggio mj (in ogni
passo ogni blocco viene usato una volta);
utilizza una delle 64 costanti Tk;
utilizza una funzione fp diversa per ogni passo;
effettua una rotazione il cui valore è determinato da
una funzione Sp diversa per ogni passo;
Funzioni di hash sicure: MD5 e SHASHA-1
Davide Cerri
- 12 -
Davide Cerri
6
Funzioni di hash sicure: MD5 e SHA-1
Elaborazione MD5 (4)
A (e.g. d0)
B (e.g. d1)
C (e.g. d2)
+
mj
+
Tk
+
D (e.g. d3)
fp
schema di una
operazione MD5
↵Sp(i mod 4)
+
A’ (e.g. d3)
B’ (e.g. d0)
Funzioni di hash sicure: MD5 e SHASHA-1
C’ (e.g. d1)
D’ (e.g. d2)
- 13 -
Davide Cerri
Elaborazione MD5: passo 1
Definiamo F(x,y,z) = (x ∧ y) ∨ (∼x ∧ z).
Per i=0-15 si esegue:
d(-i) mod 4 = d(1-i) mod 4 + (d(-i) mod 4 + F(d(1-i) mod 4 ,
d(2-i) mod 4 , d(3-i) mod 4) + mi + Ti+1)↵S1(i mod 4)
dove S1(0) = 7, S1(1) = 12, S1(2) = 17, S1(3) = 22.
Le prime 5 di 16 operazioni sono quindi:
d0 = d1 + (d0 + F(d1, d2, d3) + m0 + T1)↵7
(i=0)
d3 = d0 + (d3 + F(d0, d1, d2) + m1 + T2)↵12 (i=1)
d2 = d3 + (d2 + F(d3, d0, d1) + m2 + T3)↵17 (i=2)
d1 = d2 + (d1 + F(d2, d3, d0) + m3 + T4)↵22 (i=3)
(i=4)
d0 = d1 + (d0 + F(d1, d2, d3) + m4 + T5)↵7
Funzioni di hash sicure: MD5 e SHASHA-1
Davide Cerri
- 14 -
Davide Cerri
7
Funzioni di hash sicure: MD5 e SHA-1
Elaborazione MD5: passo 2
Definiamo G(x,y,z) = (x ∧ z) ∨ (y ∧ ∼z).
Per i=0-15 si esegue:
d(-i) mod 4 = d(1-i) mod 4 + (d(-i) mod 4 + G(d(1-i) mod 4, d(2-i) mod 4,
d(3-i) mod 4) + m(5i+1) mod 16 + Ti+17)↵S2(i mod 4)
dove S2(0) = 5, S2(1) = 9, S2(2) = 14, S2(3) = 20.
Le prime 5 di 16 operazioni sono quindi:
d0 = d1 + (d0 + G(d1, d2, d3) + m1 + T17)↵5 (i=0)
d3 = d0 + (d3 + G(d0, d1, d2) + m6 + T18)↵9 (i=1)
d2 = d3 + (d2 + G(d3, d0, d1) + m11 + T19)↵14 (i=2)
d1 = d2 + (d1 + G(d2, d3, d0) + m0 + T20)↵20 (i=3)
d0 = d1 + (d0 + G(d1, d2, d3) + m5 + T21)↵5 (i=4)
Funzioni di hash sicure: MD5 e SHASHA-1
- 15 -
Davide Cerri
Elaborazione MD5: passo 3
Definiamo H(x,y,z) = x ⊕ y ⊕ z.
Per i=0-15 si esegue:
d(-i) mod 4 = d(1-i) mod 4 + (d(-i) mod 4 + H(d(1-i) mod 4, d(2-i) mod 4,
d(3-i) mod 4) + m(3i+5) mod 16 + Ti+33)↵S3(i mod 4)
dove S3(0) = 4, S3(1) = 11, S3(2) = 16, S3(3) = 23.
Le prime 5 di 16 operazioni sono quindi:
d0 = d1 + (d0 + H(d1, d2, d3) + m5 + T33)↵4 (i=0)
d3 = d0 + (d3 + H(d0, d1, d2) + m8 + T34)↵11 (i=1)
d2 = d3 + (d2 + H(d3, d0, d1) + m11 + T35)↵16 (i=2)
d1 = d2 + (d1 + H(d2, d3, d0) + m14 + T36)↵23 (i=3)
d0 = d1 + (d0 + H(d1, d2, d3) + m1 + T37)↵4 (i=4)
Funzioni di hash sicure: MD5 e SHASHA-1
Davide Cerri
- 16 -
Davide Cerri
8
Funzioni di hash sicure: MD5 e SHA-1
Elaborazione MD5: passo 4
Definiamo I(x,y,z) = y ⊕ (x ∨ ∼z).
Per i=0-15 si esegue:
d(-i) mod 4 = d(1-i) mod 4 + (d(-i) mod 4 + I(d(1-i) mod 4, d(2-i) mod 4,
d(3-i) mod 4) + m(7i) mod 16 + Ti+49)↵S4(i mod 4)
dove S4(0) = 6, S4(1) = 10, S4(2) = 15, S4(3) = 21.
Le prime 5 di 16 operazioni sono quindi:
d0 = d1 + (d0 + I(d1, d2, d3) + m0 + T49)↵6
(i=0)
d3 = d0 + (d3 + I(d0, d1, d2) + m7 + T50)↵10 (i=1)
d2 = d3 + (d2 + I(d3, d0, d1) + m14 + T51)↵15 (i=2)
d1 = d2 + (d1 + I(d2, d3, d0) + m5 + T52)↵21 (i=3)
d0 = d1 + (d0 + I(d1, d2, d3) + m12 + T53)↵6 (i=4)
Funzioni di hash sicure: MD5 e SHASHA-1
- 17 -
Davide Cerri
SHA-1
SHASHA-1 (Secure Hash Algorithm 1) è stato progettato
dal NIST (l’algoritmo SHA originale è stato sostituito
con SHA-1 dal NIST stesso per via di una
vulnerabilità non pubblicata).
Il messaggio (che deve essere di lunghezza inferiore
a 264 bit) viene elaborato a blocchi di 512 bit.
L’hash è di 160 bit.
bit
Ad ogni iterazione si calcola una funzione che
dipende dal blocco corrente del messaggio e dal
valore dell’hash all’iterazione precedente; il
risultato viene sommato (per singola parola) al
valore dell’iterazione precedente.
Funzioni di hash sicure: MD5 e SHASHA-1
Davide Cerri
- 18 -
Davide Cerri
9
Funzioni di hash sicure: MD5 e SHA-1
SHA-1: inizializzazione
Al messaggio viene aggiunto un padding (uguale a
quello di MD5)
Le 5 parole di 32 bit del digest (A, B, C, D, E)
vengono inizializzate con: A = 0x67452301,
B = 0xEFCDAB89, C = 0x98BADCFE, D = 0x10325476,
E = 0xC3D2E1F0.
Ogni iterazione calcola dei valori di A, B, C, D, E
che vengono sommati ai precedenti prima di
passare all’iterazione successiva.
Alla fine, la concatenazione di A, B, C, D, E
costituisce il digest del messaggio.
Funzioni di hash sicure: MD5 e SHASHA-1
- 19 -
Davide Cerri
SHA-1: schema iterazione (1)
Il blocco corrente di messaggio (512 bit) viene
utilizzato per costruire una stringa di 5 x 512 bit (80
parole di 32 bit).
Le prime 16 parole coincidono con il blocco del
messaggio, le successive sono calcolate così:
Wi = (Wi-3 ⊕ Wi-8 ⊕ Wi-14 ⊕ Wi-16)↵1 (i=16-79)
la rotazione di un bit è stata aggiunta in SHA-1
(è l’unica differenza tra SHA e SHA-1).
Si scorre la stringa di 80 parole una parola alla volta
(80 operazioni), calcolando i nuovi valori A’, B’, C’,
D’, E’. Alla fine, i nuovi valori verranno aggiunti agli
A, B, C, D, E precedenti.
Funzioni di hash sicure: MD5 e SHASHA-1
Davide Cerri
- 20 -
Davide Cerri
10
Funzioni di hash sicure: MD5 e SHA-1
SHA-1: schema iterazione (2)
Ogni iterazione è composta da 80 operazioni.
Per i=0-79:
B’, C’, D’, E’ sono calcolati così:
B’ = A
C’ = B↵30
D’ = C
E’ = D
A’ viene calcolato così:
A’ = E + (A↵5) + Wi + Ki + fi(B, C, D)
dove Ki vale: 230 2 (i = 0 − 19 )
 
230 3  (i = 20 − 39)
2
30
5  (i = 40 − 59 )
e fi(B, C, D) vale:
(B ∧ C ) ∨ (~ B ∧ D )
30
10  (i = 60 − 79 )
(i = 0 − 19 )
(i = 20 − 39,
(B ∧ C ) ∨ (B ∧ D ) ∨ (C ∧ D )
B⊕C ⊕ D
Funzioni di hash sicure: MD5 e SHASHA-1
2
i = 60 − 79 )
(i = 40 − 59 )
- 21 -
Davide Cerri
SHA-1: schema operazione
A
B
C
D
schema di una
operazione SHA-1
fi
+
↵30
B’
Funzioni di hash sicure: MD5 e SHASHA-1
Davide Cerri
+
↵5
A’
E
C’
- 22 -
D’
+
Wi
+
Ki
E’
Davide Cerri
11
Funzioni di hash sicure: MD5 e SHA-1
MD5 vs. SHA-1
MD5
SHA-1
128 bit
160 bit
lunghezza massima
messaggio
illimitata
264 -1 bit
dimensione blocco
messsaggio
512 bit
512 bit
numero operazioni
64
80
numero costanti additive
64
4
numero funzioni primitive
4
4 (di cui 2 uguali)
lunghezza hash
Funzioni di hash sicure: MD5 e SHASHA-1
Davide Cerri
- 23 -
Davide Cerri
12