This page has been robot translated, sorry for typos if any. Original content here.

Toutes les techniques de piratage MD5

Sur le sujet:


Все методы взлома MD5

Ce n'est un secret pour personne que la cryptographie est fermement entrée dans nos vies. Les services Internet, les réseaux sociaux, les appareils mobiles - tous stockent les mots de passe des utilisateurs chiffrés à l'aide de divers algorithmes dans leurs bases de données.

De nos jours, l'algorithme le plus populaire est de loin MD5.

Nous allons parler de méthodes pour le pirater.

Un peu de cryptographie

La cryptographie moderne comprend trois domaines: le cryptage à clé privée, le cryptage à clé publique et le hachage. Aujourd’hui, nous allons parler de ce qu’est le hachage et de quoi il se mange.

En général, le hachage fait référence à la conversion de données d'entrée d'une longueur arbitraire en une chaîne de bits de sortie d'une longueur fixe. Le plus souvent, les fonctions de hachage sont utilisées dans le processus d'authentification de l'utilisateur (le hachage du mot de passe est généralement stocké dans la base de données au lieu du mot de passe lui-même) et pour calculer les sommes de contrôle des fichiers, des paquets de données, etc.

L'un des algorithmes de hachage les plus connus et les plus largement utilisés est MD5.

Début

L'algorithme MD5 est un algorithme de hachage de 128 bits. Cela signifie qu'il calcule un hachage de 128 bits pour un ensemble arbitraire de données arrivant à son entrée. Cet algorithme a été développé par le professeur Ronald Rivest du Massachusetts Institute of Technology en 1991 pour remplacer le prédécesseur moins fiable - MD4. L'algorithme a été publié pour la première fois en avril 1992 dans le document RFC 1321. Après cela, MD5 a été utilisé pour résoudre diverses tâches, allant du hachage de mots de passe dans le CMS à la création de signatures numériques et de certificats SSL.

Le fait que l’algorithme MD5 puisse être piraté a été abordé pour la première fois en 1993. Les chercheurs Bert den Boer et Anton Bossilaris ont montré que des pseudo-collisions sont possibles dans l'algorithme. Trois ans plus tard, en 1996, Hans Dobbertin publiait un article dans lequel il prouvait la présence de collisions et décrivait la possibilité théorique de piratage du MD5. Ce n'était pas encore un hack, mais on parlait dans le monde de la nécessité de passer à des algorithmes de hachage plus fiables, par exemple SHA1 (au moment de la rédaction de cet article, il était déjà prouvé qu'il existait des collisions, donc je recommande d'utiliser SHA2) ou RIPEMD-160.

Premières attaques

Le piratage direct de MD5 a commencé le 1 er mars 2004. CertainKey Cryptosystems a lancé le projet MD5CRK, un système de détection de collision distribué. L'objectif du projet était de rechercher deux messages avec des codes de hachage identiques. Le projet a été achevé le 24 août 2004, lorsque quatre chercheurs indépendants - Wang Xiaoyun, Feng Denguo, Lai Xuejia et Yu Hongbo - ont découvert une vulnérabilité d'algorithme permettant de détecter des collisions à l'aide d'une méthode analytique dans un délai plus ou moins acceptable. En utilisant cette méthode, vous pouvez identifier les collisions sur un cluster IBM p690 en une heure à peine (il est dommage que je ne dispose pas d’une telle maison).

Все методы взлома MD5
Exemple de collision de hachage MD5

Le 1 er mars 2005, la première utilisation de cette vulnérabilité a été démontrée dans la pratique. L'équipe de recherche a présenté deux certificats X.509 avec différents jeux de clés, mais avec des sommes de contrôle identiques. La même année, Vlastimil Klima a publié un algorithme permettant de détecter les collisions sur un ordinateur portable ordinaire en quelques heures. En 2006, il a continué. Le 18 mars 2006, le chercheur a dévoilé un algorithme permettant de détecter les collisions en une minute! Cette méthode s'appelle tunneling. En 2008, un article sur la méthode de génération de faux certificats X.509 a été présenté au Chaos Communication Congress. En fait, il s'agissait du premier cas d'utilisation réelle de collisions dans l'algorithme MD5.

Все методы взлома MD5
Masque Brute MD5

Beaucoup de travail a également été fait pour accélérer la fissuration des hachages. En 2007, Kevin Breeze a lancé un programme utilisant la Sony PlayStation3 pour pirater MD5. Il a réussi à obtenir de très bons résultats: 1,4 milliard de hachages MD5 ont été générés en une seconde! Deux ans plus tard, en 2009, BlackHat USA publiait un article sur l’utilisation du GPU pour la recherche de collisions, ce qui permettait d’augmenter sa vitesse plusieurs fois, en particulier s’il était exécuté simultanément sur plusieurs cartes vidéo.

La carte graphique ATI Radeon HD 4850 X2 peut générer jusqu'à 2,2 milliards de hachages par seconde! L'utilisation de l'algorithme MD5 dans EDS est inacceptable en raison de la stabilité insuffisante de cet algorithme pour la recherche de collisions.

Est-ce la fin?

En 2011, l'IETF a accepté de modifier les documents RFC 1321 (MD5) et RFC 2104 (HMAC-MD5). Voici comment est né le RFC 6151, qui reconnaît l'algorithme de chiffrement MD5 comme non sécurisé et recommande de ne pas l'utiliser. A mon avis, ce document a officiellement mis fin au MD5.

Cependant, malgré le fait que l’algorithme MD5 ait été officiellement reconnu dangereux, des milliers, voire des dizaines, des centaines de milliers d’applications l’utilisent pour stocker des mots de passe, des signatures électroniques et calculer des sommes de contrôle de fichiers.

En passant, le 31 octobre 2008, le NIST a annoncé un concours entre les cryptographes. Le but du concours est de développer un algorithme de hachage pour remplacer les SHA1 et SHA2 obsolètes. Pour le moment, les finalistes ont déjà été identifiés: BLAKE, Gostl, JH, Keccak et Skein.

Ighashgpu: piratage GPU

Mais assez de théorie. Passons aux affaires et parlons directement du piratage de notre algorithme préféré. Supposons que nous ayons un hachage de mot de passe: d8578edf8458ce06fbc5bb76a58c5ca4.

Pour résoudre ce problème, je suggère d'utiliser le programme Ighashgpu, qui peut être téléchargé à partir de www.golubev.com ou disponible sur notre disque. L'utilitaire est distribué gratuitement et fonctionne tranquillement sous Windows. Pour accélérer le processus de piratage du hachage, Ighashgpu utilise un processeur graphique. Vous devez donc disposer d'au moins une carte graphique nVidia ou ATI prenant en charge CUDA / ATI Stream.

Les GPU modernes reposent sur une architecture légèrement différente de celle des processeurs classiques. Ils traitent donc les informations graphiques de manière beaucoup plus efficace. Bien que les GPU soient conçus pour gérer les graphiques en trois dimensions, on a eu tendance ces dernières années à les utiliser pour l’informatique classique. Commencer avec le programme n’est pas simple, mais très simple: décompressez l’archive n'importe où sur le disque et procédez au piratage à l'aide de la ligne de commande Windows:

ighashgpu.exe -t:md5 \
-h:d8578edf8458ce06fbc5bb76a58c5ca4 -max:7

Nous utilisons la méthode ci-dessus pour déchiffrer un hachage spécifique généré à l'aide de l'algorithme MD5. Le mot de passe maximum possible est de sept caractères. Après un certain temps, le mot de passe sera trouvé (qwerty). Essayons maintenant de craquer un autre hash, mais avec des conditions légèrement différentes. Laissez notre hash ressembler à d11fd4559815b2c3de1b685bb78a6283, mais il comprend des lettres, des chiffres, un trait de soulignement et porte le suffixe "_admin". Dans ce cas, nous pouvons utiliser le masquage de mot de passe pour simplifier la tâche du programme:

ighashgpu.exe -h:d11fd4559815b2c3de1b685bb78a6283 -t:md5
-u:[abcdefghijklmnopqrstuwvxyz1234567890_] -m:??????_admin

Ici, le paramètre '-u' vous permet de spécifier le jeu de caractères utilisé dans la recherche et le paramètre '-m' définit le masque de mot de passe. Dans notre cas, le masque est composé de six caractères arbitraires, suivis de la combinaison "_admin". La sélection du mot de passe est également facile.

Collisions - une collision en cryptographie fait référence à deux blocs de données d'entrée différents qui donnent le même hachage pour la même fonction de hachage. Chaque fonction de la sortie donne une séquence de bits d'une certaine longueur, indépendante de la taille des données d'origine. Il s'ensuit que des collisions existent pour tout algorithme de hachage. Cependant, la probabilité que vous trouviez une collision dans un «bon» algorithme tend presque à zéro. Malheureusement ou heureusement, les algorithmes de hachage peuvent contenir des erreurs, comme n'importe quel programme. De nombreuses fonctions de hachage ont été interrompues ou le seront bientôt. Dans ce cas, "casser" signifie trouver une collision dans un temps beaucoup plus petit que l'infini déclaré.

Ighashgpu: annonces

Essayons maintenant de déchiffrer plusieurs mots de passe à la fois. Supposons que nous ayons une base de données de hachages de mots de passe. Il est également connu que chaque mot de passe se termine par des caractères c00l:

f0b46ac8494b7761adb7203aa7776c2a
f2da202a5a215b66995de1f9327dbaa6
c7f7a34bbe8f385faa89a04a9d94dacf
cb1cb9a40708a151e6c92702342f0ac5
00a931d3facaad384169ebc31d38775c
4966d8547cce099ae6f666f09f68458e

Enregistrez les hachages dans le fichier encrypted.dat et exécutez Ighashgpu comme suit:

ighashgpu.exe -t:md5 -u:[abcdefghijklmnopqrstuwvxyz1234567890_]
-m:??????c00l encrypted.dat

Une fois le programme terminé, le fichier ighashgpu_results.txt contenant des mots de passe fissurés apparaît dans le dossier Ighashgpu:

f0b46ac8494b7761adb7203aa7776c2a:1rootxc00l
f2da202a5a215b66995de1f9327dbaa6:pwd12xc00l
c7f7a34bbe8f385faa89a04a9d94dacf:pwd34yc00l

cb1cb9a40708a151e6c92702342f0ac5:pwd56yc00l
4966d8547cce099ae6f666f09f68458e:pwd98zc00l
00a931d3facaad384169ebc31d38775c:pwd78zc00l
Все методы взлома MD5
Hachage des hachages de crypted.dat

Ighashgpu: sel

Enfin, piratons un hachage "salé". Supposons qu'un hachage est généré en utilisant l'algorithme suivant:

var plain = password + "s41t";
var hash = md5(plain);

En conséquence, nous avons obtenu le hash suivant: 42151cf2ff27c5181bb36a8bcfafea7b. Ighashgpu vous permet de spécifier "salt" dans le paramètre "-asalt":

ighashgpu.exe -h:42151cf2ff27c5181bb36a8bcfafea7b \
-t:md5 -u:[abcdefghijklmnopqrstuwvxyz1234567890_] \
-asalt:s41t

Et nous avons à nouveau reçu le mot de passe requis facilement et rapidement.

Entertaining math - Pour un mot de passe de 8 caractères composé des 126 premiers caractères ASCII, 63 527 879 748 485 386 combinaisons possibles sont disponibles. Pour 254 caractères, le nombre de combinaisons possibles passe à 17 324 859 956 700 833 536, soit déjà 2,7 milliards de fois plus que les habitants de notre planète. Si vous créez un fichier texte contenant tous ces mots de passe, cela prendra des millions de téraoctets. Bien sûr, dans le monde moderne, cela est possible, mais le coût de stockage d'un tel fichier sera exorbitant.

Pirater MD5 en mode turbo

Le piratage par hachage par recherche exhaustive, même sur le meilleur matériel, prend beaucoup de temps, surtout si le mot de passe est supérieur à huit caractères. Le moyen le plus simple d'augmenter la vitesse de détection du mot de passe est de créer une base de données de tous les hachages pour un ensemble spécifique de caractères. Dans les années 80 du siècle dernier, les pirates informatiques pensaient que lorsqu'ils disposeraient d'un matériel plus puissant, de 640 Ko de mémoire et d'un disque dur de 10 Mo, une telle base de données deviendrait une réalité et la sélection d'un mot de passe ne prendrait plus que quelques minutes. Cependant, le fer se développa et le rêve resta un rêve. La situation n'a changé qu'en août 2003, après la publication par Philip Oeschlin, doctorat en réseaux informatiques de l'Institut suisse de technologie de Lausanne, de son travail sur le problème du choix du rapport temps / lieu optimal. Il décrit une méthode pour casser les fonctions de hachage à l'aide de tables arc-en-ciel.

L'essence de la nouvelle méthode est la suivante. Tout d'abord, vous devez sélectionner un mot de passe arbitraire, qui est ensuite haché et exposé à la fonction de réduction, qui convertit le hachage en un mot de passe possible (par exemple, il peut s'agir des 64 premiers bits du hachage d'origine). Ensuite, une chaîne de mots de passe possibles est construite, à partir de laquelle les premier et dernier éléments sont sélectionnés. Ils sont écrits à la table. Pour récupérer le mot de passe, appliquez la fonction de réduction au hachage d'origine et recherchez le mot de passe possible reçu dans le tableau. S'il n'y a pas de mot de passe de ce type dans la table, hachez-le et calculez le mot de passe suivant L'opération est répétée jusqu'à ce qu'un mot de passe soit trouvé dans la table arc-en-ciel. Ce mot de passe représente la fin d'une des chaînes. Pour trouver le mot de passe d'origine, vous devez exécuter à nouveau la chaîne entière. Une telle opération ne prend pas beaucoup de temps, en fonction de l'algorithme de construction de la chaîne, il s'agit généralement de quelques secondes ou minutes. Les tables "Rainbow" peuvent réduire considérablement la quantité de mémoire utilisée par rapport à la recherche classique. Le seul inconvénient de la méthode décrite est qu’il faut beaucoup de temps pour construire des tables.

Passons maintenant des mots aux actes et essayons de casser quelques hachages de mots de passe en utilisant cette méthode.

Tables Rainbow - Les tables «Rainbow» sont un type de dictionnaire spécial qui contient des chaînes de mots de passe et vous permet de choisir un mot de passe en quelques secondes ou minutes avec une probabilité de 85 à 99%.

Arc-en-ciel

Vous devez d’abord décider du programme. Personnellement, j'aime RainbowCrack, un logiciel gratuit fonctionnant sous Windows et Linux. Il prend en charge quatre algorithmes de hachage: LN / NTLM, MD5 et SHA1. Le programme ne nécessite pas d’installation, il suffit de le décompresser quelque part sur le disque. Après le déballage, vous devez trouver les tables arc-en-ciel pour l'algorithme MD5. Tout n'est pas si simple ici: ils peuvent être soit téléchargés gratuitement, soit achetés, ou générés indépendamment. Une des plus grandes archives de tables gratuites est disponible sur le site Web du projet Free Rainbow Tables.

À propos, vous pouvez également aider le projet si vous téléchargez un client du site et rejoignez un réseau international distribué générant des tables arc-en-ciel. Au moment de la rédaction du présent document, des tables de 3 To pour les algorithmes MD5, SHA1, LM et NTLM étaient déjà disponibles sur ce site. Si vous n'avez pas la possibilité de fusionner un tel volume d'informations, vous pouvez, sur le même site, commander des disques avec des tableaux arc-en-ciel. Actuellement, trois forfaits sont offerts: LN / NTLM, MD5 et SHA1 - 200 dollars chacun. Nous allons générer les tables nous-mêmes. Pour ce faire, vous devez utiliser le programme rtgen fourni avec RainbowCrack. Il accepte les paramètres d'entrée suivants:

  • hash_algorithm - algorithme de hachage (LM, NTLM, MD5 ou SHA1);
  • charset - un des jeux de caractères contenus dans le fichier charset.txt;
  • plaintextlenmin et plaintextlenmax - longueur minimale et maximale du mot de passe;
  • tableindex, chainlen, chainnum et partindex sont des «nombres magiques» décrits dans un article de Philipp Oashlin

Considérons les derniers paramètres plus en détail:

  1. table_index - l'index de la table rainbow, qui peut être utilisé pour diviser la table en plusieurs fichiers. J'ai utilisé 0, car ma table était composée d'un seul fichier.
  2. chain_len - le nombre de mots de passe uniques dans la chaîne.
  3. chain_num - le nombre de chaînes dans la table.
  4. Part_index est un paramètre qui définit le début de la chaîne. Les créateurs du programme demandent à n’utiliser qu’un nombre comme paramètre (j’ai utilisé 0). Maintenant, lancez la génération de la table arc-en-ciel pour MD5:
rtgen.exe md5 loweralpha-numeric 1 7 0 2000 97505489 0

Dans ce cas, nous créons une table de mots de passe composée de chiffres et de lettres majuscules de l'alphabet latin et d'une longueur de un à sept caractères. Sur mon Eee PC équipé d’un processeur Intel Atom N450, ce processus a pris presque deux jours. :) . En conséquence, j'ai reçu le fichier md5loweralpha-numeric # 1-702000? 975054890.rt d'une taille de 1,5 Go.

Ensuite, la table résultante doit être triée afin d'optimiser la recherche de la chaîne dont nous avons besoin. Pour ce faire, exécutez rtsort.exe:

rtsort.exe md5_loweralpha-numeric#1-7_0_2000x97505489_0.rt

Nous attendons quelques minutes et la table est prête! Maintenant, vous pouvez casser les mots de passe eux-mêmes. Premièrement, essayons de trouver un mot de passe pour un hachage: d8578edf8458ce06fbc5bb76a58c5ca4. Exécutez rcrack_gui.exe et sélectionnez Ajouter un hachage ... dans le menu Fichier. Dans la fenêtre qui apparaît, entrez le hachage et cliquez sur OK. Maintenant, sélectionnez le fichier avec la table arc-en-ciel. Pour ce faire, utilisez l’option Rechercher dans les tables Rainbow ... du menu Rainbow Table. Dans la fenêtre qui s'ouvre pour sélectionner un fichier, recherchez un fichier avec une table, je l'ai md5_loweralpha-numeric # 1-7_0_2000x97505489_0.rt, puis cliquez sur Ouvrir. Après quelques secondes, le mot de passe est entre nos mains! Une opération similaire peut être effectuée sur la liste de hachages du fichier.

Все методы взлома MD5
Je génère une table arc-en-ciel

Tables Rainbow vs. CPU vs. GPU

Je pense que vous avez fait attention à la rapidité avec laquelle Ighashgpu est capable de déchiffrer les hachages MD5 grâce à une recherche exhaustive et au fait que RainbowCrack le fait encore plus rapidement avec une bonne table arc-en-ciel. J'ai décidé de comparer la vitesse de ces programmes. Pour la pureté de l'expérience, j'ai utilisé le programme MDCrack, qui brute le mot de passe sur la CPU (et est l'un des meilleurs parmi les programmes de ce type). Voici le résultat pour le GPU (nVidia GeForce GT 220M), le processeur (Intel Atom N450, deux cœurs) et les tables arc-en-ciel:

Длина пароля | GPU | CPU | Таблицы
4 символа | 00:00:01 | 00:00:01 | 00:00:16
5 символов | 00:00:02 | 00:00:09 | 00:00:16
6 символов | 00:00:16 | 00:05:21 | 00:00:10
7 символов | 00:07:11 | 09:27:52 | 00:00:04

Comme vous pouvez le constater, la vitesse de recherche à l’aide du processeur est beaucoup plus lente que celle du GPU ou des tables arc-en-ciel. De plus, la plupart des programmes spécialisés vous permettent de créer un groupe de cartes vidéo, ce qui augmente considérablement la vitesse de recherche du mot de passe. Je pense que vous avez remarqué que la vitesse de correspondance des mots de passe de 4 et 5 caractères est inférieure à la vitesse de correspondance des mots de passe de six ou sept caractères. Cela est dû au fait que la recherche du mot de passe ne commence qu'après le chargement de la table en mémoire. Il se trouve que sur seize secondes, treize en moyenne sont consacrées au téléchargement et trois au piratage du hachage.

Все методы взлома MD5
Table Rainbow à l'intérieur

bit.ly/vEhdir - ajout d'un nouvel algorithme de hachage à RainbowCrack à l'aide de l'API.

bit.ly/vTSB9K - description du format de la table arc-en-ciel.

Au lieu d'une conclusion

En fin de compte, je voudrais parler un peu de la protection de vos mots de passe. Tout d'abord, n'utilisez pas d'algorithmes de hachage vulnérables tels que MD5 ou SHA1. À l’heure actuelle, il est utile d’envisager l’utilisation de l’une des fonctions de hachage cryptographique SHA2 ou SHA3 (dès que le standard correspondant est publié). Deuxièmement, n'utilisez pas directement les fonctions de hachage. Essayez toujours d'utiliser du sel et de combiner différents algorithmes. Et troisièmement, choisissez des mots de passe complexes aléatoires d'une longueur d'au moins huit caractères. Bien sûr, cela ne vous protégera pas du piratage à 100%, mais au moins compliquera la vie des attaquants.