Main /

Hash dei file MD5

Calcolare un hash di un file significa generare un riassunto del file. Il sistema MD5 ottiene sempre una riga di 128 bit riassuntiva per qualunque file, a prescindere dalla lunghezza del file. Chiaramente 128 bit significa le combinazioni possibili sono ` 2^127 +1 ` cioe' solo:

170141183460469231731687303715884105729

combinazioni (è un numero formato da 39 cifre)., circa 1.7 * 10³⁸. Quindi e' possibile che file completamente diversi abbiamo lo stesso hash.

Ecco un esempio di due file diversi con lo stesso hash MD5, che sembrano uguali ma differiscono di qualche valore opportunamente qui e lì:

 d131dd02c5e6eec4 693d9a0698aff95c 2fcab58712467eab 4004583eb8fb7f89
 55ad340609f4b302 83e488832571415a 085125e8f7cdc99f d91dbdf280373c5b
 d8823e3156348f5b ae6dacd436c919c6 dd53e2b487da03fd 02396306d248cda0
 e99f33420f577ee8 ce54b67080a80d1e c69821bcb6a88393 96f9652b6ff72a70


 d131dd02c5e6eec4 693d9a0698aff95c 2fcab50712467eab 4004583eb8fb7f89
 55ad340609f4b302 83e4888325f1415a 085125e8f7cdc99f d91dbd7280373c5b
 d8823e3156348f5b ae6dacd436c919c6 dd53e23487da03fd 02396306d248cda0
 e99f33420f577ee8 ce54b67080280d1e c69821bcb6a88393 96f965ab6ff72a70

L'hash MD5 di entrambi e' : 79054025255fb1a26e4bc422aef54eb4. Questo fenomeno e' chiamato collisione, ed e' sempre presente in tutti i sistemi di hash. Piu' la riga riassuntiva e' lunga, piu' le probabilita' di avere lo stesso hash diminuiscono, ma non possono mai sparire. Questo perche' l'hash non e' una forma di compressione dei dati, ma un sistema per associare un numero di una lista predefinita al contenuto del file.

Il sistema di hash di solito serve a capire se un file e' cambiato, corrotto o si e' degradato nel tempo. Il riassunto di hash ha sempre una proprieta' molto interessante, anche una piccola modifica cambia notevolmente il valore riassunto. Facciamo un esempio:

Immaginiamo che Mario voglia mandare un messaggio a Luisa, Mario manda il messaggio e il suo hash; Luisa riceve il messaggio e calcola l'hash del messaggio. Se l'hash di Mario e' uguale al hash di Luisa, il messaggio non e' stato modificato; altrimenti qualcuno ha fatto uno scherzo a Luisa modificando il messaggio.

Questo e' in sintesi il senso dell'hash. Ora andremo a vedere come e' matematicamente implementato.

Per vedere praticamente come si fa un hash MD5 (esistono anche altri tipi di hash, come SHA-1) prenderemo ad esempio una frase semplice:

 Ciao

Gia' con una fase cosi' corta i conti saranno tantissimi. Trasformiamo la frase in una sequenza di bit usando il codice ASCII, quindi la parola "Ciao" diventa:

 01000011011010010110000101101111

Questo perche' ogni lettera e' un numero, C e' il numero 67 in ASCII e in bit il numero si scrive 01000011.

Poi si aggiunge un 1 al messaggio e tanti zeri fino a far diventare la sua lunghezza un multiplo di 512:

 01000011011010010110000101101111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

poi si sostituiscono gli ultimi 64 bit con la lunghezza del messaggio originale espressa in 64bit. Per messaggi cosi' grandi che 64 bit non bastano (quindi maggiori di 2⁶⁴), si mettono solo i primi 64 bit (quelli meno significativi). Il nostro messaggio originale e' lungo solo 32 bit, quindi ci basta sostituite gli ultimi sei zeri con 100000 (32 in codice binario):

 01000011011010010110000101101111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000

Il messaggio ottenuto è lungo un multiplo di 512 bit (nel nostro caso solo 512 bit esatti) , quindi puo' essere diviso in parti esatte da 32 bit.

Prima di cominciare ad operare, prepariamo quattro variabili temporanee da 32 bit (A,B,C,D) con i seguenti valori esadecimali:

A: 01 23 45 67
B: 89 ab cd ef
C: fe dc ba 98
D: 76 54 32 10

che in bit si scrivono, considerando 8 bit per numero: (ho lasciato degli spazio per far capire la conversione)

A: 00000001 00100011 01000101 01100111
B: 10001001 10101011 11001101 11101111
C: 11111110 11011100 10111010 10011000
D: 01110110 01010100 00110010 00010000

Poi definiamo le quattro funzioni che saranno applicate al messaggio:

F(B,C,D) = (B and C) or ((not B) and D )
G(B,C,D) = (B and D) or (C and (not D) )
H(B,C,D) = B xor C xor D
I(B,C,D) = C xor ( B or ( not D) )

queste funzioni si applicheranno a numeri di 32 bit. Facciamo in esempio chiarificatore con numeri piccoli (4 bit):

 1100 OR 0011 = 1111
 1010 AND 1111 = 1010
 NOT  1010 = 0101
 1100 XOR 0011 = 0000

creiamo un vettore di 64 elementi seguendo questa formula (le strane parentesi a forma di L significano solo la parte intera del risultato):

` T[i] = |__ 4294967296 * |sin(i)| __| `

ottenendo questi numeri:

 [3614090360.0 3905402710.0 606105819 3250441966.0 4118548399.0 1200080426 2821735955.0 4249261313.0 1770035416 2336552879.0 4294925233.0 2304563134.0 1804603682 4254626195.0 2792965006.0 1236535329 4129170786.0 3225465664.0 643717713 3921069994.0 3593408605.0 38016083 3634488961.0 3889429448.0 568446438 3275163606.0 4107603335.0 1163531501 2850285829.0 4243563512.0 1735328473 2368359562.0 4294588738.0 2272392833.0 1839030562 4259657740.0 2763975236.0 1272893353 4139469664.0 3200236656.0 681279174 3936430074.0 3572445317.0 76029189 3654602809.0 3873151461.0 530742520 3299628645.0 4096336452.0 1126891415 2878612391.0 4237533241.0 1700485571 2399980690.0 4293915773.0 2240044497.0 1873313359 4264355552.0 2734768916.0 1309151649 4149444226.0 3174756917.0 718787259 3951481745.0]

Ora possiamo cominciare a fare i conti; come gia' descritto il nostro messaggio e' stato trasformato in una sequenza di lunga 512 bit o un multiplo di 512. Il seguente ciclo descritto si applica a tronconi esatti di 512 bit alla volta. Per ogni pezzo da 512 bit bisogna eseguire la seguente procedura.

Si spezzetta il blocco da 512 bit in 16 pezzetti da 32 bit.

Si mettono i primi 16 pezzetti da 32 bit in un vettore X. Quinid X[1] sara il primo pezzetto da 32bit, X[2] il secondo e cosi' via.

Si copiano A, B, C, D nelle variabili temporanee AA, BB, CC, DD.

Poi si eseguono le seguenti operazioni (il simbolo <<< significa spostamento di bit a sinistra aritmetico ):

A = B + F( B , C , D ) + X[ 1 ] + T[ 1 ] <<< 7
D = A + F( A , B , C ) + X[ 2 ] + T[ 2 ] <<< 12
C = D + F( D , A , B ) + X[ 3 ] + T[ 3 ] <<< 17
B = C + F( C , D , A ) + X[ 4 ] + T[ 4 ] <<< 22
A = B + F( B , C , D ) + X[ 5 ] + T[ 5 ] <<< 7
D = A + F( A , B , C ) + X[ 6 ] + T[ 6 ] <<< 12
C = D + F( D , A , B ) + X[ 7 ] + T[ 7 ] <<< 17
B = C + F( C , D , A ) + X[ 8 ] + T[ 8 ] <<< 22
A = B + F( B , C , D ) + X[ 9 ] + T[ 9 ] <<< 7
D = A + F( A , B , C ) + X[ 10 ] + T[ 10 ] <<< 12
C = D + F( D , A , B ) + X[ 11 ] + T[ 11 ] <<< 17
B = C + F( C , D , A ) + X[ 12 ] + T[ 12 ] <<< 22
A = B + F( B , C , D ) + X[ 13 ] + T[ 13 ] <<< 7
D = A + F( A , B , C ) + X[ 14 ] + T[ 14 ] <<< 12
C = D + F( D , A , B ) + X[ 15 ] + T[ 15 ] <<< 17
B = C + F( C , D , A ) + X[ 16 ] + T[ 16 ] <<< 22
A = B + G( B , C , D ) + X[ 2 ] + T[ 17 ] <<< 5
D = A + G( A , B , C ) + X[ 7 ] + T[ 18 ] <<< 9
C = D + G( D , A , B ) + X[ 12 ] + T[ 19 ] <<< 14
B = C + G( C , D , A ) + X[ 1 ] + T[ 20 ] <<< 20
A = B + G( B , C , D ) + X[ 6 ] + T[ 21 ] <<< 5
D = A + G( A , B , C ) + X[ 11 ] + T[ 22 ] <<< 9
C = D + G( D , A , B ) + X[ 16 ] + T[ 23 ] <<< 14
B = C + G( C , D , A ) + X[ 5 ] + T[ 24 ] <<< 20
A = B + G( B , C , D ) + X[ 10 ] + T[ 25 ] <<< 5
D = A + G( A , B , C ) + X[ 15 ] + T[ 26 ] <<< 9
C = D + G( D , A , B ) + X[ 4 ] + T[ 27 ] <<< 14
B = C + G( C , D , A ) + X[ 9 ] + T[ 28 ] <<< 20
A = B + G( B , C , D ) + X[ 14 ] + T[ 29 ] <<< 5
D = A + G( A , B , C ) + X[ 3 ] + T[ 30 ] <<< 9
C = D + G( D , A , B ) + X[ 8 ] + T[ 31 ] <<< 14
B = C + G( C , D , A ) + X[ 13 ] + T[ 32 ] <<< 20
A = B + H( B , C , D ) + X[ 6 ] + T[ 33 ] <<< 4
D = A + H( A , B , C ) + X[ 9 ] + T[ 34 ] <<< 11
C = D + H( D , A , B ) + X[ 12 ] + T[ 35 ] <<< 16
B = C + H( C , D , A ) + X[ 15 ] + T[ 36 ] <<< 23
A = B + H( B , C , D ) + X[ 2 ] + T[ 37 ] <<< 4
D = A + H( A , B , C ) + X[ 5 ] + T[ 38 ] <<< 11
C = D + H( D , A , B ) + X[ 8 ] + T[ 39 ] <<< 16
B = C + H( C , D , A ) + X[ 11 ] + T[ 40 ] <<< 23
A = B + H( B , C , D ) + X[ 14 ] + T[ 41 ] <<< 4
D = A + H( A , B , C ) + X[ 1 ] + T[ 42 ] <<< 11
C = D + H( D , A , B ) + X[ 4 ] + T[ 43 ] <<< 16
B = C + H( C , D , A ) + X[ 7 ] + T[ 44 ] <<< 23
A = B + H( B , C , D ) + X[ 10 ] + T[ 45 ] <<< 4
D = A + H( A , B , C ) + X[ 13 ] + T[ 46 ] <<< 11
C = D + H( D , A , B ) + X[ 16 ] + T[ 47 ] <<< 16
B = C + H( C , D , A ) + X[ 3 ] + T[ 48 ] <<< 23
A = B + I( B , C , D ) + X[ 1 ] + T[ 49 ] <<< 6
D = A + I( A , B , C ) + X[ 8 ] + T[ 50 ] <<< 10
C = D + I( D , A , B ) + X[ 15 ] + T[ 51 ] <<< 15
B = C + I( C , D , A ) + X[ 6 ] + T[ 52 ] <<< 21
A = B + I( B , C , D ) + X[ 13 ] + T[ 53 ] <<< 6
D = A + I( A , B , C ) + X[ 4 ] + T[ 54 ] <<< 10
C = D + I( D , A , B ) + X[ 11 ] + T[ 55 ] <<< 15
B = C + I( C , D , A ) + X[ 2 ] + T[ 56 ] <<< 21
A = B + I( B , C , D ) + X[ 9 ] + T[ 57 ] <<< 6
D = A + I( A , B , C ) + X[ 16 ] + T[ 58 ] <<< 10
C = D + I( D , A , B ) + X[ 7 ] + T[ 59 ] <<< 15
B = C + I( C , D , A ) + X[ 14 ] + T[ 60 ] <<< 21
A = B + I( B , C , D ) + X[ 5 ] + T[ 61 ] <<< 6
D = A + I( A , B , C ) + X[ 12 ] + T[ 62 ] <<< 10
C = D + I( D , A , B ) + X[ 3 ] + T[ 63 ] <<< 15
B = C + I( C , D , A ) + X[ 10 ] + T[ 64 ] <<< 21
A = A + AA
B = B + BB
C = C +CC
D = D + DD

E si ripete il tutto finche' non sono finiti tutti i blocchi da 512 bit.

Otterrete cosi' 4 numeri da 32 bit (A,B,C,D), nel nostro caso:

 00010110001001110010101001011101
 11011000001111000110001100000001
 00001110100111110110011110010111
 01111001010000001110100001110001

che potete convertire in esadecimale:

 16272a5d   d83c6301    0e9f6797    7940e871

Quindi se tutto e' andato bene l'hash MD5 di "Ciao" e':

 16272a5dd83c63010e9f67977940e871