MD5

MD5 (Message Digest algorithm 5) è un algoritmo di hashing che produce una stringa univoca di 128 bit; un caratteristico hash MD5 è formato da 32 caratteri esadecimali.

Fu creato nel 1991 da Ronald Rivest, per sostituire il precedente MD4 (a sua volta preceduto da MD3, MD2, MD), considerato oramai insicuro. Tuttavia, nel 1996 venne trovata un'imperfezione nell'MD5, cosicché i crittografi cominciarono a consigliare di utilizzare altri sistemi di hashing, come SHA-1 o WHIRPOOL.
Come detto sopra, l'MD5 prende in input una stringa di lunghezza arbitraria e la trasforma in una stringa a 128 bit da 32 caratteri esadecimali, qualunque sia la lunghezza della stringa iniziale. A livello teorico l'output dovrebbe (Chiamato hash o MD5 checksum) una stringa univoca, ovvero dovrebbe essere impossibile trovare due hash uguali date due stringhe di partenza diverse; allo stesso modo, dovrebbe essere impossibile risalire alla stringa che ha generato l'hash, se non per tentativi. Ad ogni modo, in alcune occasioni sono stati trovati hash uguali con stringhe diverse di partenza, e creati alcuni algoritmi con lo scopo di cercare collisioni che sono riusciti a trovare anche una collisione al minuto.

Algoritmo

MD5 elabora una stringa di variabile lunghezza affinché questa generi un output di 128 bit. La stringa iniziale viene divisa in blocchi da 512 bit (ovvero sedici linee da 32 bit ciascuna), in modo che la stringa sia divisibile per 512. Si procede in questo modo: per prima cosa viene aggiunto in fondo alla stringa un bit singolo, 1. Questo viene seguito da tanti 0 quanti ne servono perché la lunghezza della stringa diventi minore di 64 bit rispetto ad un multiplo di 512. I rimanenti bit sono dati da un intero di 64 bit che rappresenta la lunghezza della stringa originale in bit.
L'algoritmo principale di MD5 opera sulla stringa a 128 bit, divisa in quattro stringhe da 32 bit, chiamate A, B, C e D. Il procedimento dell'algoritmo si struttura in quattro rounds; ogni round è composto da 16 operazioni simili basate su una funzione F non lineare, addizione modulare e rotazione a sinistra. Nell'immagine si vede il possibile funzionamento di un round. Ci sono quattro possibili funzioni F, che variano ad ogni round:

Dove

rappresentano rispettivamente gli operatori XOR, AND, OR e NOT.

Pseudocodice

Ecco un po' di pseudo codice per l'algoritmo MD5:

//Note: All variables are unsigned 32 bits and wrap modulo 2^32 when calculating

var int[64] r, k

//r specifies the per-round shift amounts

r[ 0..15] := {7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22}

r[16..31] := {5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20}

r[32..47] := {4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23}

r[48..63] := {6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21}

//Use binary integer part of the sines of integers (Radians) as constants:

for i from 0 to 63

k[i] := floor(abs(sin(i + 1)) × (2 pow 32))

//Initialize variables:

var int h0 := 0x67452301

var int h1 := 0xEFCDAB89

var int h2 := 0x98BADCFE

var int h3 := 0x10325476

//Pre-processing:

append "1" bit to message

append "0" bits until message length in bits ≡ 448 (mod 512)

append bit (bit, not byte) length of unpadded message as 64-bit little-endian integer to message

//Process the message in successive 512-bit chunks:

for each 512-bit chunk of message

break chunk into sixteen 32-bit little-endian words w[i], 0 ≤ i ≤ 15

//Initialize hash value for this chunk:

var int a := h0

var int b := h1

var int c := h2

var int d := h3

//Main loop:

for i from 0 to 63

if 0 ≤ i ≤ 15 then

f := (b and c) or ((not b) and d)

g := i

else if 16 ≤ i ≤ 31

f := (d and b) or ((not d) and c)

g := (5×i + 1) mod 16

else if 32 ≤ i ≤ 47

f := b xor c xor d

g := (3×i + 5) mod 16

else if 48 ≤ i ≤ 63

f := c xor (b or (not d))

g := (7×i) mod 16

temp := d

d := c

c := b

b := b + leftrotate((a + f + k[i] + w[g]) , r[i])

a := temp

//Add this chunk's hash to result so far:

h0 := h0 + a

h1 := h1 + b

h2 := h2 + c

h3 := h3 + d

var int digest := h0 append h1 append h2 append h3 //(expressed as little-endian)

//leftrotate function definition

leftrotate (x, c)

return (x << c) or (x >> (32-c));

Esempi di funzionamento

Vediamo la generazione di hash MD5 in Python, fattibile con poche righe di codice:

import md5

m = md5.new()

m.update("testo da criptare")

test = m.hexdigest()

print test

References

http://en.wikipedia.org