INFORMATICA - HASH MD5
(COLLISIONI E PROBABILITA')

Nella certificazione delle copie forensi di memorie di massa l'impiego dell'hash MD5 è consolidato e massivo, quali problemi si possono determinare? esistono veramente questioni di affidabilità?

Gennaio 2007

Riferimenti tecnici a fondo pagina

In  maniera piuttosto semplificata una funzione di hash è una funzione univoca operante in un solo senso (one-way, ossia, che non può essere invertita) atta alla trasformazione di un testo in chiaro e di lunghezza arbitraria in una stringa di lunghezza stabilita e generalmente piuttosto limitata. Si lascia ovviamente al lettore l’eventuale approfondimento di natura matematica di questa definizione negli ampi riferimenti a fine pagina.

In particolare, prendiamo in considerazione una particolare funzione di hash detta MD5 molto impiegata in diversi settori della sicurezza informatica e del FC:

“In cryptography, MD5 (Message-Digest algorithm 5) is a widely used cryptographic hash function with a 128-bit hash value. As an Internet standard (RFC 1321), MD5 has been employed in a wide variety of security applications, and is also commonly used to check the integrity of files. An MD5 hash is typically a 32-character hexadecimal number.” From www.wikipedia.org

Data l’univocità della funzione di hash la determinazione di due stringhe di dati A e B diverse tra loro tali che hash(A) = hash(B) non dovrebbe essere possibile per definizione ed invece sfortunatamente, con le funzioni ad oggi conosciute ed implementate negli elaboratori (MD5 incluso) tale fatto si verifica determinando quella che tecnicamente viene indicata come collisione.

Dal punto di vista tecnico/legale una collisione del MD5 è davvero preoccupante (vedere riferimento) 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 nulla assicura con certezza circa la 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 (riferimento esteso http://eprint.iacr.org/). Essi precisamente trovarono due sequenze diverse di 128 byte con lo stesso valore di MD5 associato (sono riportate di seguito per i curiosi):

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.

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) con lo stesso valore di MD5 ma contenuti piuttosto diversi (rif. https://www.mscs.dal.ca/~selinger/md5collision/);

- E' stato realizzato un metodo mediante il quale è possibile costruire due programmi con funzionalità molto diverse ma aventi lo stesso valore di  hash MD5
(rif. http://www.codeproject.com/dotnet/HackingMd5.asp).

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 (compreso lo scrivente). Sulle debolezze (relative) di MD5 e SHA-1 (un altro algoritmo di hashing) eravamo infatti tutti consci (sebbene la citata scoperta abbia ufficializzato la criticità). Ora è chiaro che tali protocolli possono infatti essere ingannati facilmente studiando due stringhe di partenza praticamente random (con un alto grado di disordine) oppure aggiungendo in coda ad una stringa un’altra particolare di lunghezza fissa (vengono sfruttate “criticità” molto specifiche dell’algoritmo),  ma:

(a) ad oggi non è possibile (per quanto presente nella letteratura scientifica) determinare una metodologia deterministica per modificare un generico file non specificamente progettato a priori (es. modificare una parola, alterare una foto, fare scomparire un settore di un hard disk, ecc.) per poi riottenere lo stesso hash MD5;

(b) è praticamente impossibile che un’alterazione casuale di un file ne determini un altro, diverso dal primo, con lo stesso valore di MD5.

Ciò deve essere tenuto accuratamente in considerazione quando ci si spinge a dire che MD5 non è affidabile per la certificazione delle copie forensi delle memorie di massa. Né Wang, Kaminski, Yu e tutti gli altri che hanno contribuito al grande risultato delle collisioni di MD5 e SHA-1 si sono mai sognati di scrivere nei loro documenti ufficiali che in generale MD5 e SHA-1 sono non affidabili.

Essi hanno solo dimostrato che in determinate particolari condizioni sono inaffidabili. Ad esempio, non ha senso usare MD5 quando l’utente può definire tutti i dati su cui poi verrà applicata la funzione (al momento, una situazione di questo tipo è praticamente impossibile da riprodurre nel repertamento dati su un hard disk).

Per finire, a coloro che chiedono, soprattutto in ambito forense la probabilità che MD5 entri in collisione sulla copia di una memoria di massa di un computer riporto i risultati di [40] e [41]:

Per una funzione di hash ideale a 128 bit il numero approssimativo di tentativi da fare prima di ottenere almeno una collisione è:
N1 = 1,26 × 2^64 ~ 10.000.000.000.000.000.000

Per un MD5 nelle condizioni che i dati da sottoporre al calcolo non possano essere scelti arbitrariamente (situazione del repertamento dati su una memoria di massa) il numero approssimativo di tentativi da fare prima di ottenere almeno una collisione è:
N ~ 2^42 = 4.398.046.511.104

Questo vuole dire che bisognerà analizzare 4mila miliardi circa di memorie prima di giungere ad una possibile collisione. Ammesso di impiegare 1 minuto a memoria repertata (spesso si impiegano ore...) il tempo da attendere è di circa 8 milioni di anni!!!!

 

Diversi riferimenti sull’argomento (aggiornati nei limiti delle mie conoscenze):

Vlastimil Klima: Tunnels in Hash Functions: MD5 Collisions Within a Minute (extended abstract), IACR ePrint archive Report 2006/105 , 18 March, 2006, pdf: English ,Czech , the source code version 0 (non optimized), the source code version 1 (a collision in 31 seconds on a notebook).

Daniel Joscak: Finding Collisions in Cryptographic Hash Functions, diploma work, MFF UK, Prague, April 21, 2006. Abstract: The main interest of this paper is finding collisions in the hash function MD5. We present our new algorithm based on Wangs et al. methods of finding collisions in MD5. While writing this thesis Stevens and Klima published their fast algorithms for nding collisions. We give a description of these algorithms and the calculation of computianal complexity of all three algorithms.

Give me any three files and I will give you another three with the same MD5 hash... More info The program pack3 was written by Ondrej Mikle. It is based on MD5 collision program by Vlastimil Klima. Usage: pack3 file1 file2 file3 file4 file5 file6 will create two packages, package1.exe and package2.exe. Both will have the same MD5 sum, while package1.exe will extract files 1-3 and package2.exe will extract files 4-6.

Marc Stevens, "Fast Collision Attack on MD5", 17 March 2006, IACR ePrint archive Report 2006/104 , pdf and source code .

Quick test of both Klima and Stevens programs is here .

Pavel Dufek: Modification of Klima´s program (version 1), this modified program enables to choose the initialization value as a program parameter. It creates new text and binary files, also. The source code and executable program is here . NEW

J. Black, M. Cochran, T. Highland: "A Study of the MD5 Attacks: Insights and Improvements", FSE 2006, pdf (March 3, 2006) , toolkit .

Jun Yajima and Takeshi Shimoyama: Wang’s sufficient conditions of MD5 are not sufficient, Cryptology ePrint Archive: Report 2005/263, 10 Aug 2005, http://eprint.iacr.org/2005/263.pdf .

Yu Sasaki and Yusuke Naito and Noboru Kunihiro and Kazuo Ohta: Improved Collision Attack on MD5, Cryptology ePrint Archive: Report 2005/400, 7 Nov 2005, http://eprint.iacr.org/2005/400.pdf .

Liang J. and Lai X.: Improved Collision Attack on Hash Function MD5, Cryptology ePrint Archive: Report 425/2005, 23 Nov 2005, http://eprint.iacr.org/2005/425.pdf .

Vlastimil Klima: Finding MD5 Collisions on a Notebook PC Using Multi-message Modifications, IACR ePrint archive, Report 2005/102, pdf: English, Czech, March 31, 2005, 3rd Int. Conference Security and Protection of Information 2005, Brno, Czech Republic, May 3 - 5, 2005, powerpoint presentation.

Vlastimil Klima: Finding MD5 Collisions – a Toy For a Notebook, Cryptology ePrint Archive, Report 2005/075, pdf: English, Czech, March 5, 2005.

Ondrej Mikle: Practical Attacks on Digital Signatures Using MD5 Message Digest, Cryptology ePrint Archive, Report 2004/356, 2nd December 2004, homepage.

Xiaoyun Wang, Hongbo Yu: How to Break MD5 and Other Hash Functions, pdf, published on the web on March 6, 2005.

Xiaoyun Wang, Xuejia Lai, Dengguo Feng, Hui Chen, Xiuyuan Yu: Cryptanalysis of the Hash Functions MD4 and RIPEMD, pdf, published on the web on March 6, 2005

Arjen Lenstra, Xiaoyun Wang, Benne de Weger: Colliding X.509 Certificates, homepage, report.

Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu: Collision Search Attacks on SHA1, report.

marcomattiucci.it

Informatica:

Digital Forensics - articoli:

Digital forensics: