L'algoritmo MD5

L'algoritmo MD5 è stato disegnato da R. Rivest (la R nell'acronimo RSA) per produrre un digest, ossia una sequenza di byte unica per il messaggio fornito in input. La sigla MD sta per Message Digest. Qui spieghiamo cos'è MD5 in modo intuitivo ma dettagliato.

MD5 accetta in input un messaggio qualsiasi (anche binario) e di qualsiasi lunghezza; il testo può essere passato all'algoritmo un po' alla volta. L'output dell'algoritmo è costituito da una sequenza di 16 byte che si chiama il digest o hash MD5 del messaggio.

Dettaglio di un passaggio

Quelli che si vedono alla riga 0 del primo round sono i valori iniziali del digest. Nelle 16 righe successive ci sono i valori del digest durante le 16 operazioni che costituiscono il primo round.

Un passo dell'algoritmo consiste di quattro round, quindi 64 operazioni, per ogni blocco di 64 byte di testo del messaggio. Ma andiamo con ordine.

Che operazione viene fatta tra una riga e la successiva? Come si vede, cambiano quattro byte. In questo senso MD5 è un algoritmo a 32 bit: perché i byte vengono considerati a quattro per volta, interpretandoli come un numero tra 0 e 4294967295 (il più grande numero che si possa esprimere con quattro byte è 2³²-1).

Per ogni operazione vengono presi quattro byte di messaggio e sommati a un numero pseudo-casuale, i bit del risultato vengono ruotati e scambiati, anche a seconda dei valori correnti del digest. In questo modo, i nuovi quattro byte dipendono dal messaggio, ma dipendono anche da tutte le operazioni svolte sul digest fino a questo punto.

Durante il primo round i 64 byte del blocco corrente intervengono nel loro ordine naturale, ossia i primi 4 nella prima operazione, i secondi 4 nella seconda e così via. Nei tre round successivi l'ordine viene cambiato. I 64 numeri pseudo-casuali fissi (ricavati da π) che vengono sommati in ogni operazione vanificano la ricerca di collisioni basate su particolari regolarità del messaggio.

Quando tutto il messaggio è stato digerito, viene aggiunto un blocco di 64 byte che contiene la lunghezza del messaggio stesso.

Ricerca di collisioni

Due messaggi diversi danno luogo a una collisione quando generano un identico digest. Il numero di digest possibili, cioé le combinazioni di 16 byte diversi, sono 2^16x8, ossia circa 3x10³⁸. È chiaro che, dato che invece i messaggi possibili sono infiniti, anche le possibili collisioni con un dato messaggio sono infinite. Tuttavia 3x10³⁸ è un numero elevato: se ci limitiamo a considerare i messaggi scritti dall'uomo, bisognerebbe che un'umanità di 10 miliardi di individui in un periodo di 10'000 anni scriva centinaia di milioni di miliardi di messaggi al secondo per arrivare a quella cifra.

È relativamente più semplice trovare connessioni casuali: con circa 2x10¹⁹ messaggi casuali si ha una probabilità del 50% di trovare una collisione. Questo viene spiegato con lo stesso calcolo secondo cui è sufficiente raccogliere 23 persone per avere il 50% di probabilità che due di queste compiano gli anni lo stesso giorno. Questo tipo di ricerca di collisioni si chiama birthday attack.

Un perfezionamento di questa tecnica è stato messo a punto da Marc Stevens, che ha pubblicato un software, fastcoll, in grado di trovare collisioni tra due messaggi che condividono uno stesso prefisso. Il programma trova una collisione in pochi secondi, con un numero stimato di circa 10¹⁵ tentativi. Si veda Il progetto Chosen-prefix collisions (in inglese) dell'Università Tecnica di Eindhoven (NL)

Nel mezzo del cammin di nostra vita
Mi ritrovai per una selva os

Nel mezzo del cammin di nostra vita
mi ritrovai per una selva os

    c4 87 7f 10 79 ac 0e 3d 56 db 4a a6 11 37 85 94

  

 0: 01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 10
 1: 84 8e 52 db 89 ab cd ef fe dc ba 98 76 54 32 10
 2: 84 8e 52 db 89 ab cd ef fe dc ba 98 79 c2 15 b0
 3: 84 8e 52 db 89 ab cd ef a9 c6 a5 e3 79 c2 15 b0
 4: 84 8e 52 db 42 98 d8 27 a9 c6 a5 e3 79 c2 15 b0
 5: 3b 85 bf 86 42 98 d8 27 a9 c6 a5 e3 79 c2 15 b0
 6: 3b 85 bf 86 42 98 d8 27 a9 c6 a5 e3 34 dd b3 81
 7: 3b 85 bf 86 42 98 d8 27 be 2b ed 84 34 dd b3 81
 8: 3b 85 bf 86 84 a8 74 7f be 2b ed 84 34 dd b3 81
 9: c3 c0 fc 43 84 a8 74 7f be 2b ed 84 34 dd b3 81
10: c3 c0 fc 43 84 a8 74 7f be 2b ed 84 2b 85 9b 32
11: c3 c0 fc 43 84 a8 74 7f e2 0d 5a 7b 2b 85 9b 32
12: c3 c0 fc 43 4b 0c 31 32 e2 0d 5a 7b 2b 85 9b 32
13: cc 67 13 7f 4b 0c 31 32 e2 0d 5a 7b 2b 85 9b 32
14: cc 67 13 7f 4b 0c 31 32 e2 0d 5a 7b fa 3f 2d 66
15: cc 67 13 7f 4b 0c 31 32 9b 5c 85 23 fa 3f 2d 66
16: cc 67 13 7f 78 b7 60 4e 9b 5c 85 23 fa 3f 2d 66