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

Toutes les méthodes de piratage MD5

Par 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 des mots de passe utilisateur chiffrés avec divers algorithmes dans leurs bases de données.

Bien entendu, l'algorithme le plus populaire aujourd'hui est MD5.

Sur les méthodes de piratage et sera discuté.

Un peu de cryptographie

La cryptographie moderne comprend trois domaines: le cryptage avec une clé privée, le cryptage avec une 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 est compris comme la conversion de données d'entrée de longueur arbitraire en une chaîne de bits de sortie de longueur fixe. Le plus souvent, les fonctions de hachage sont utilisées dans le processus d'authentification de l'utilisateur (un hachage de 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.

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

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 un CMS à la création de signatures numériques et de certificats SSL.

Le fait que l’algorithme MD5 puisse être piraté a été évoqué pour la première fois en 1993. Les chercheurs Bert den Boer et Anton Bossilaris ont montré que les pseudocollisions sont possibles dans l'algorithme. Trois ans plus tard, en 1996, Hans Dobbertin publiait un article dans lequel il prouvait l'existence de collisions et décrivait la possibilité théorique de pirater MD5. Ce n'était pas encore un hack, mais le monde entier a commencé à parler de la nécessité de passer à des algorithmes de hachage plus fiables, tels que SHA1 (au moment d'écrire ces lignes, il était déjà prouvé qu'il existait des collisions dans cet algorithme, je recommande donc d'utiliser SHA2) ou RIPEMD-160.

Premières attaques

La fissuration immédiate du MD5 a débuté le 1er mars 2004. CertainKey Cryptosystems a lancé le projet MD5CRK, un système de détection de collision distribué. L'objectif du projet était de trouver deux messages avec des codes de hachage identiques. Le projet a pris fin le 24 août 2004, lorsque quatre chercheurs indépendants - Wang Xiaoyun, Feng Denguo, Lai Xuejia et Yu Hongbo - ont découvert la vulnérabilité de l'algorithme, ce qui permet de détecter des collisions par une méthode analytique dans un délai plus ou moins raisonnable. Grâce à cette méthode, il est possible d’identifier les collisions sur le cluster IBM p690 en une heure à peine (il est dommage que je n’ai pas une telle maison).

Все методы взлома MD5
Un exemple de collision de hachages MD5

Le 1 er mars 2005, la première utilisation de cette vulnérabilité dans la pratique a été démontrée. Une équipe de chercheurs 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 pour détecter les collisions sur un ordinateur portable ordinaire en quelques heures. En 2006, il est allé plus loin. 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 génération de faux certificats X.509 a été présenté à la conférence Chaos Communication Congress. En fait, il s’agissait du premier cas d’utilisation réelle de collisions dans l’algorithme MD5.

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

Beaucoup de travail a également été fait pour accélérer le piratage des hachages. En 2007, Kevin Breeze a lancé un programme utilisant la Sony PlayStation3 pour déchiffrer le 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 utilisé simultanément avec plusieurs cartes vidéo.

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

Est-ce la fin?

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

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

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

Ighashgpu: piratage GPU

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

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

Les processeurs graphiques modernes reposant sur une architecture légèrement différente de celle des processeurs classiques, ils traitent 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 ordinaire. Commencer avec le programme n’est pas facile, mais très simple: décompressez l’archive n'importe où sur le disque et lancez le 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 entrer dans un hachage spécifique généré à l'aide de l'algorithme MD5. La longueur maximale du mot de passe 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. Soit notre hachage sous la forme d11fd4559815b2c3de1b685bb78a6283, et comprend les lettres, les chiffres, le trait de soulignement et le suffixe "_admin". Dans ce cas, nous pouvons utiliser la force brute par masque 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 n'est également pas difficile.

Collisions - Les collisions cryptographiques font référence à deux blocs de données d'entrée différents qui, pour la même fonction de hachage, produisent le même hachage. Chaque fonction de sortie donne une séquence de bits d'une certaine longueur qui ne dépend pas 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 puissiez trouver une collision dans le "bon" algorithme tend presque à zéro. Malheureusement ou heureusement, les algorithmes de hachage peuvent contenir des erreurs, comme tout autre programme. De nombreuses fonctions de hachage ont été interrompues ou le seront bientôt. Dans ce cas, «décomposer» signifie trouver une collision dans un temps très inférieur à l'infini déclaré.

Ighashgpu: Listes

Essayons maintenant de déchiffrer plusieurs mots de passe à la fois. Supposons que nous ayons en main une base de données de mots de passe. On sait 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 apparaîtra dans le dossier Ighashgpu avec les mots de passe piratés:

f0b46ac8494b7761adb7203aa7776c2a:1rootxc00l
f2da202a5a215b66995de1f9327dbaa6:pwd12xc00l
c7f7a34bbe8f385faa89a04a9d94dacf:pwd34yc00l

cb1cb9a40708a151e6c92702342f0ac5:pwd56yc00l
4966d8547cce099ae6f666f09f68458e:pwd98zc00l
00a931d3facaad384169ebc31d38775c:pwd78zc00l
Все методы взлома MD5
Piratage du fichier encrypted.dat

Ighashgpu: sel

Enfin, craquons le hash "salé". Supposons que le hachage est généré par 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 de nouveau le mot de passe rapidement et facilement.

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 simplement transcendantal.

Piratage de MD5 en mode turbo

Le piratage des données en utilisant 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 consiste à 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 deviendrait une réalité et le choix 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 Oashlin, Ph.D., spécialiste des réseaux informatiques à l’Institut suisse de technologie de Lausanne, de son travail sur la problématique du choix du rapport temps-lieu optimal. Il décrivait la méthode de piratage des fonctions de hachage à l'aide de tableaux "arc-en-ciel".

L'essence de la nouvelle méthode est la suivante. Vous devez d’abord choisir un mot de passe arbitraire, qui est ensuite haché et affecté par une fonction de réduction qui convertit le hachage en tout mot de passe possible (par exemple, il peut s’agir des 64 premiers bits du hachage original). 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 enregistrés dans un tableau. Pour récupérer le mot de passe, appliquez la fonction de réduction au hachage d'origine et recherchez le mot de passe éventuel résultant dans le tableau. S'il n'y a pas de mot de passe de ce type dans la table, nous le hacherons et calculerons 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 est 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, selon l'algorithme de construction de la chaîne, elle prend généralement quelques secondes ou quelques 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 les 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 spécial de dictionnaire 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%.

"Rainbow" piratage

Vous devez d’abord décider du programme. Personnellement, j'aime bien RainbowCrack, qui est gratuit et fonctionne à la fois sous Windows et Linux. Il supporte quatre algorithmes de hachage: LN / NTLM, MD5 et SHA1. Le programme ne nécessite pas d'installation, décompressez-le simplement quelque part sur le disque. Après le déballage, il est nécessaire de trouver les tables arc-en-ciel pour l'algorithme MD5. Ici, tout n'est pas si simple: vous pouvez les télécharger gratuitement, les acheter ou les générer vous-même. Une des plus grandes archives de tables gratuites est disponible sur le site 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 de ce 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 cette quantité d'informations, vous pouvez, sur le même site, commander des disques avec des tables "arc-en-ciel". À l'heure actuelle, trois forfaits sont offerts: LN / NTLM, MD5 et SHA1 - pour 200 $ chacun. Nous allons générer les tables nous-mêmes. Pour ce faire, vous devez utiliser le programme rtgen, qui fait partie de RainbowCrack. Il prend les paramètres d'entrée suivants:

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

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

  1. index_table est l'index de la table "arc-en-ciel", qui peut être utilisé lors du fractionnement de la table en plusieurs fichiers. J'ai utilisé 0, parce que 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. index_partie est le paramètre qui définit le début de la chaîne. Les créateurs du programme sont invités à n'utiliser qu'un nombre comme paramètre (j'ai utilisé 0). Nous commençons maintenant 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 un tableau de mots de passe composé 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 fin de compte, j'ai reçu le fichier md5loweralpha-numeric # 1-702000? 975054890.rt 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 vous-même. Tout d'abord, 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, j'ai ce 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 d'un fichier.

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

Tables Rainbow vs. CPU contre GPU

Je pense que vous avez fait attention à la rapidité avec laquelle Ighashgpu est capable de percer brusquement le hachage MD5, et que RainbowCrack le fait encore plus rapidement si vous avez 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 exécute un mot de passe sur la CPU (et constitue l'un des meilleurs 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 bien inférieure à celle d’un GPU ou de tables "arc-en-ciel". De plus, la plupart des programmes spécialisés vous permettent de créer un groupe de cartes vidéo, grâce auquel la vitesse de recherche du mot de passe augmente plusieurs fois. Je pense que vous avez remarqué que la vitesse de saisie des mots de passe de 4 et 5 caractères est inférieure à celle d'un mot de passe de six ou sept caractères. Cela est dû au fait que la recherche de mot de passe ne commence que lorsque la table est chargée en mémoire. Il se trouve que sur seize secondes, en moyenne, treize sont consacrées au téléchargement et trois autres à la suppression d'un hachage.

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

bit.ly/vEhdir - ajoute 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 de 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. Pour le moment, il est utile d’envisager l’utilisation d’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 "salt" et de combiner différents algorithmes. Et troisièmement, choisissez des mots de passe arbitraires complexes comportant au moins huit caractères. Bien sûr, cela ne vous protège pas du piratage à 100%, mais au moins complique la vie des intrus.