lundi, 18 décembre 2006

Reverse MD5

La fonction MD5 est une fonction dit à sens unique, c'est-à-dire que ne connaissant que la sortie, il est difficile de trouver l'entrée qui a produit cette sortie.

C'est pourquoi des reverse md5 databases sont apparues sur Internet. Leur principe est tout simple : c'est une grande base de données contenant la pair (texte, hash). Ainsi on peut la questionner du hash recherché et elle nous retourne le texte correspondant si il est connu.

La base de données doit donc être remplie avant de pouvoir produire des réponses, mais une fois qu'elle contient suffisamment de données, les recherches peuvent commencer à être intéressantes. Les techniques des remplissages sont simples, elles vont du parcours de pages web ou de dictionnaires pour rechercher des mots quelconques à l'ajout manuel par des utilisateurs.

J'ai rapidement fait une petite application qui questionne plusieurs des ces reverse md5 databases, qui elle est disponible à l'addresse http://md5.noisette.ch/form.php

Elle se base sur la toute petite API suivante : http://md5.noisette.ch/?hash=<le_hash_en_hex> qui retourne du XML

<md5lookup>
  <hash><!--[CDATA[2a0231531bc1a7fc29e2fa8d64352ae9]]--></hash>
  <string><!--[CDATA[noisette]]--></string>
</md5lookup>


L'approche est très alléchante car une fois le hash dans la base de données, les réponses sont fournies en O(1). Les mots de passe stockés en md5 peuvent donc être retrouvés extrèmenent rapidement.
La contre-partie de cette approche est qu'elle nécessite beaucoup de hash précalculé avant d'être utilisable, et donc produira une énorme base de données :
Le md5 étant sur 128 bits, on pourrait avoir une table de 2^^128 entrées, pour peu qu'on ne prenne pas en compte les doublons. Donc rien que pour les hash, il nous faudrait ~5*10^^39 bytes de stockage = ~5000 téra de téra de téra bytes. Enfin juste pas possible quoi. Si on fait le raisonnement inversion on se dit que notre serveur a 200Gb d'espace disque, on peut donc stocker 12.5 milliards de hash, donc 12.5 milliards de possibilités de mots de passe = un peu plus de 2^^33 possibilités. On est loin des 2^^128...

En résumé, c'est une approchoe time / memory tradoff 100% mémory :)

2 commentaires:

MY a dit…

Si on stocke tous les hashes, pourquoi les stocker? On aurait non plus pas idée de les numéroter :)

Sinon il faut aussi mentionner qu'il existe des techniques pour réduire de pas mal la taille mémoire nécessaire, mais la recherche est un peu moins efficace (rainbow table).

KillerWhile a dit…

> Pourquoi les stocker

Les analystes affirment que des GB de GB de GB de data sont générés chaque jour dans le monde, alors je m'efforce aide à leur donner raison.

> Rainbow table.

Effectivement, j'aurais dû commencer par là : j'ai fait mon travail de master avec Philippe Oechslin, l'inventeur des Rainbow tables, qui est un "time-memory tradeoff" entre brute force et stocker tous les hashes comme cette DB. L'idée initiale était bien de générer des Rainbow tables de bonnes qualités.