Dal 2004 il blog di Antonio Troise

Su internet molto spesso veniamo a contatto con gli HASH MD5 senza neanche accorgersene. Nell’ambito informatico, la crittografia tramite algoritmo MD5 viene applicata in tutti i settori dell’informatica che lavorano con il supporto delle firme digitali o che comunque trattano dati sensibili, per cui una delle funzionalità più usate è quella di verifica di originalità di un documento, di una foto o di un file eseguibile, attraverso il rilascio di una firma digitale.

Ad esempio, la funzione di HASH come l’MD5:

• viene utilizzata per controllare che uno scambio di dati sia avvenuto senza perdite, semplicemente attraverso il confronto della stringa prodotta dal file inviato con quella prodotta dal file ricevuto;
• con lo stesso metodo si può verificare se il contenuto di un file è cambiato (funzione utilizzata dai motori di ricerca per capire se una pagina deve essere nuovamente indicizzata);
• addirittura, anche nell’ambito P2P è molto usato per identificare univocamente i file che possono assumere anche nomi diversi.
• Per finire è anche molto diffuso come supporto per l’autenticazione degli utenti attraverso i linguaggi di scripting Web server-side (PHP in particolare): durante la registrazione di un utente su un portale internet, la password scelta durante il processo verrà codificata tramite MD5 e la sua firma digitale verrà memorizzata nel database (o in unfile di dati). Successivamente, durante il login la password immessa dall’utente subirà lo stesso trattamento e verrà confrontata con la copia in possesso del server, per avere la certezza dell’autenticità del login.

Che cosa è la funzione di HASH?

Ma cosa è l’hash di un documento? Su Wikipedia, leggiamo che l’hash è una funzione univoca operante in un solo senso (ossia, che non può essere invertita), atta alla trasformazione di un testo di lunghezza arbitraria in una stringa di lunghezza fissa, relativamente limitata. In poche parole, l’hash altro non è che una particolare trasformazione matematica che, applicata al documento da firmare, ne genera la cosiddetta impronta, ovvero un “riassunto” costituito da un numero assai ridotto (e costante) di bit, che rappresenta univocamente il documento di partenza.
Tale riassunto, o più propriamente stringa, rappresenta una sorta di “impronta digitale” del testo in chiaro, e viene anche chiamata valore di hash, checksum crittografico o message digest.

La lunghezza dei valori di hash varia a seconda degli algoritmi utilizzati. Il valore più comunemente adottato è di 128 bit (MD5), che offre una buona affidabilità in uno spazio relativamente ridotto.

Quindi, come si è potuto capire, la forza di questo sistema consiste in 3 importanti fattori:

• L’algoritmo restituisce una stringa fissa di un numero di bit fisso, a prescindere dalla mole di bit elaborati
• L’algoritmo non è invertibile, ossia non è possibile ricostruire il documento originale a partire dalla stringa che viene restituita in output.
• La stringa è, teoricamente, univoca per ogni documento e ne è un identificatore (ovvero è priva di collisioni)

Come è intuibile, il fatto che non sia possibile ricavare il documento da cui deriva una hash e il fatto che non sia teoricamente possibile che documenti diversi producano la medesima impronta (quindi che la firma sia “non invertibile” e “priva di collisioni”), rende la funzione di hash, a ragione, una candidato ideale per essere uno strumento essenziale che ha piena validità legale!

Le collisioni delle funzioni di hash

Il problema, però, sorge proprio sull’ultima caratteristica, forse la più importante, ovvero quella in cui l’hash è solo teoricamente univoco, mentre, come è facilmente intuibile, non lo è affatto. Infatti dato che i testi possibili, con dimensione finita maggiore dell’hash, sono più degli hash possibili, per il Principio dei cassetti (se n oggetti sono messi in m cassetti, e n > m, allora almeno un cassetto deve contenere più di un oggetto) ad almeno un hash corrisponderanno più testi possibili.
Quando due testi producono lo stesso hash, si parla di collisione, e la qualità di una funzione di hash è misurata direttamente in base alla difficoltà nell’individuare due testi che generino una collisione.

Tuttavia, ciò non deve trarre in inganno! Infatti scegliendo adeguatamente un algoritmo in modo che il numero di possibili impronte sia estremamente elevato, e dunque la probabilità di una collisione, voluta o casuale, sia ridotta tanto da diventare del tutto trascurabile., allora si può benissimo affermare che queste auspicate “impossibilità”, se intese in senso pratico e non teorico, siano praticamente reali.

Pensate che, con un’impronta di 160 bit, la funzione di hash è in grado di discriminare fra 2¹⁶⁰ documenti, che equivale ad un numero con un 1 seguito da 48 zeri!

Naturalmente però non basta che la funzione produca un valore di questa lunghezza, occorre anche che essa effettivamente generi valori diversissimi tra loro al variare del documento in ingresso, e soprattutto che tali valori non siano “facilmente” riconducibili al documento di partenza. In pratica la funzione deve essere tale da far risultare “praticamente impossibile” sia creare ad arte un documento che produca proprio un determinato hash noto a priori, sia creare ad arte due documenti diversi che producano lo stesso hash (collisione). Se così non fosse, le conseguenze sarebbero davvero molto gravi.

Se infatti fosse possibile trovare facilmente collisioni nella funzione hash utilizzata in un dato sistema di firma digitale, allora un malintenzionato potrebbe “falsificare” un documento mantenendone apparentemente valida la firma, e per di più questa truffa non sarebbe rivelabile né tantomeno dimostrabile. Inutile dire che ciò, ovviamente, minerebbe alla base tutto il meccanismo della firma digitale.

Quando sono state create due firme MD5 uguali da documenti diversi

Per scongiurare questo rischio, le funzioni hash solitamente utilizzate nella pratica sono accuratamente progettate e controllate affinché risultino quanto più possibile prive di collisioni. Il che non significa che non ne possano produrre in assoluto: ma solo che la probabilità che ciò avvenga per caso sia infinitesimale, e che inoltre risulti estremamente difficile produrre collisioni in modo intenzionale.

Per sconsigliare l’utilizzo di algoritmi di hashing in passato considerati sicuri è stato infatti sufficiente che un singolo gruppo di ricercatori riuscisse a generare una collisione. Questo è quello che è avvenuto ad esempio per gli algoritmi SNEFRU, MD2, MD4 ed MD5.

Dal punto di vista tecnico/legale una collisione del MD5 è davvero preoccupante perché il codice MD5 calcolato si fa portatore dell’integrità e correttezza della copia svolta su una memoria di massa e quindi se possono esistere due memorie dotate di contenuti diversi con lo stesso codice MD5 questo vorrebbe dire che la funzione non può dare alcuna assicurazione sulla certezza di non modificazione dei dati dopo il repertamento.

Dalla letteratura specifica è ben noto che MD5 è stato portato alla collisione ufficialmente nel 2005 da Xiaoyun Wang e Hongbo Yu della Shandong University cinese. Essi precisamente trovarono due sequenze diverse (ma molto simili) di 128 byte con lo stesso valore di MD5 associato:

d131dd02c5e6eec4693d9a0698aff95c 2fcab58712467eab4004583eb8fb7f89
55ad340609f4b30283e488832571415a 085125e8f7cdc99fd91dbdf280373c5b
d8823e3156348f5bae6dacd436c919c6 dd53e2b487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080a80d1e c69821bcb6a8839396f9652b6ff72a70

e

d131dd02c5e6eec4693d9a0698aff95c 2fcab50712467eab4004583eb8fb7f89 55ad340609f4b30283e4888325f1415a 085125e8f7cdc99fd91dbd7280373c5b d8823e3156348f5bae6dacd436c919c6 dd53e23487da03fd02396306d248cda0 e99f33420f577ee8ce54b67080280d1e c69821bcb6a8839396f965ab6ff72a70

il cui comune valore di hash MD5 è 79054025255fb1a26e4bc422aef54eb4.

Se volete verificare voi stessi, potete calcolare l’MD5 di questa sequenza esadecimale con l’Online Hash Value Calculator (inserendo i valori nel campo di Hex bytes) o con un tool per Windows come HashOnClick.

Quello che il team di ricerca riuscì a dimostrare è di possedere un metodo generale per generare facilmente collisioni in alcune fra le più note e diffuse funzioni hash, in particolare quelle denominate MD5.

In realtà la funzione MD5 era già da tempo sul banco degli imputati: infatti già da diversi anni altri ricercatori avevano pubblicato dei lavori di analisi teorica che gettavano seri dubbi sull’affidabilità di tali funzioni, pur senza dimostrare in modo certo la loro effettiva debolezza. Inoltre la scarsa lunghezza dell’impronta da esse generata (128 bit per entrambe) era già da parecchio tempo giudicata insufficiente a prevenire efficacemente quegli attacchi “a forza bruta” resi ormai possibili dalle enormi potenze di calcolo dei moderni computer. Il team cinese, dunque, non ha fatto altro che produrre una prova pratica ed incontrovertibile di quanto già si sospettava, peraltro senza fornire alcuna descrizione del metodo di attacco da essi sviluppato.

A seguito di questa scoperta sono state individuate metodologie per creare file ed eseguibili di lunghezza arbitraria che hanno lo stesso MD5 ma possono differire al massimo per 128 byte. Alcuni esempi sono disponibili in rete:

• Sono stati creati due file .ps (PostScript) (file1, file2) con lo stesso valore di MD5 ma contenuti piuttosto diversi (rif. http://www.cits.rub.de/MD5Collisions/);
• E’ stato realizzato un metodo mediante il quale è possibile costruire due programmi (es. prog1, prog2) con funzionalità molto diverse ma aventi lo stesso valore di hash MD5
  (rif. http://www.codeproject.com/dotnet/HackingMd5.asp).

La firma digitale è a rischio?

La funzione MD5, pur essendo da anni uno standard Internet (RFC1321) era già da tempo “sconsigliata”; essa dunque, benché ancora largamente diffusa ed utilizzata in molti ambiti, non viene praticamente più impiegata in applicazioni realmente critiche, come quelle legali e forensi.

Tali evidenti collisioni hanno preoccupato i matematici e gli studiosi di crittografia ma scarsamente coloro che normalmente si affidano al MD5 per le loro attività pratiche quotidiane. Sulle debolezze (relative) di MD5 e SHA-1 (un altro algoritmo di hashing) erano infatti tutti consci (sebbene la citata scoperta abbia ufficializzato la criticità). Ma affermare MD5 non è affidabile per la certificazione delle copie di memorie di massa non è esatto perché il metodo di generazione delle collisioni messo a punto dai ricercatori cinesi non potrebbe comunque portare a truffe come quella delineata in precedenza: esso infatti non consente affatto di produrre un documento di senso compiuto avente un hash desiderato, che è ciò che serve per “falsificare” una firma. Al contrario, esso permette solo di generare simultaneamente una coppia di documenti “privi di senso” (ossia costituiti da sequenze caotiche di bit) e per di più assai simili tra loro (con soli pochi bit di differenza situati in posizioni critiche predeterminate), i quali producono sì un medesimo hash, ma che non può essere in alcun modo essere scelto a priori. Ciò conferma ancora una volta come la scoperta dei ricercatori cinesi, pur assumendo un grande valore sul piano della teoria, non abbia praticamente quasi alcuna rilevanza su quello della pratica.

In effetti né Wang, Kaminski, Yu e tutti gli altri che hanno contribuito al grande risultato delle collisioni di MD5 e SHA-1 non si sono mai sognati di scrivere nei loro documenti ufficiali che in generale questi algoritmi non sono affidabili. Essi hanno solo dimostrato che in determinate particolari condizioni la struttura matematica di MD5 (e di molte altre funzioni hash ad essa simili) è intrinsecamente debole, e di questo si deve tenere conto nella progettazione delle nuove e future funzioni hash.

Come scoprire una password codificata in MD5

Esistono vari modi per decifrare un codice MD5:

• Cercare in database di codici MD5 già decodificati.
  MD5()
  passcracking
  gdataonline
  MD5OnlineCracking
  Milw0rm
• Usare il software Cain scaricabile all’indirizzo http://www.oxid.it/cain.html . Per comprenderne il suo utilizzo vi rimando a questo video http://www.irongeek.com/i.php?page=videos/md5-password-cracking

  Potete trovare un generatore di collisioni MD5 scritto in C nella sezione download di http://nerd.altervista.org