Friday, February 12, 2010

MD5 : attacco a forza bruta

L'MD5 è un algoritmo crittografico di hashing (Wikipedia).

L'MD5 garantisce di non possedere una funzione inversa e di avere un hash univoco per ogni stringa, anche se con una grande potenza computazionale è possibile ottenere una stringa contraffatta A che abbia l'hash identico ad una stringa B, senza conoscere B.

L'MD5 è utilizzato in molti contesti, fra cui la criptazione di password e nella identificazione dei certificati di sicurezza.

Tuttavia, viste la sicurezza di MD5 non più considerata soddisfacente, l'algoritmo è in via di abbandono (i sistemi non utilizzano più md5 per crittografare password, i certificati con id generato da md5 stanno scomparendo...).

Tuttavia a livello di apprendimento ho realizzato un programma in c, che cerca di recuperare dall'MD5 la stringa che lo ha generato. Ovviamente l'unico modo è con un attacco brute force, ovvero provando tutte le combinazioni possibili.

Il programma è multithread sviluppato utilizzando le librerie pthread di c (quindi utilizzabili solo sotto sistemi unix/linux).

ISTRUZIONI:

$ tar -xvf MD5.tar.gz
$ cd MD5
$ make
$ cd bin

Ignorate i warning di compilazione.

Per fare dei test è possibile usare il programma gen

$ ./gen (string)

che restituisce l'MD5 del parametro string.
(i sorgenti di Md5.c, Md5.h gen.c sono sorgenti prelevati dal sito people.csail.mit.edu/rivest/Md5.c)

Per eseguire il programma:

$ ./tbrute (lunghezza-minima) (lunghezza-massima) (hash)

tbrute elabora tutte le stringhe possibili dalla lunghezza (lunghezza-minima) a (lunghezza-massima), ne calcola l'hash e lo confronta con il parametro (hash).

Trattandosi di un algoritmo brute force (testa tutte le possibilità), la complessità è fattoriale e quindi tende ad aumentare considerevolmente (si passa dai 3 minuti per trovare una stringa di 4 caratteri, alle oltre 3 ore per trovarne una da 5 (questi dati vengono dal mio portatile che un single core, provando su architetture multicore, le performance dovrebbero migliorare).

Vi lascio all'archivio: download

No comments: