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 pas un secret que la cryptographie est devenue une partie de notre vie. Les services Internet, les réseaux sociaux, les appareils mobiles - ils stockent tous dans leurs bases de données les mots de passe des utilisateurs, cryptés en utilisant divers algorithmes.

Le plus populaire de ces algorithmes aujourd'hui, bien sûr, est MD5.

Sur les moyens de sa rupture et il y aura un discours.

Un peu de cryptographie

La cryptographie moderne comprend trois directions: le cryptage avec une clé privée, le cryptage à clé publique et le hachage. Aujourd'hui, nous allons parler de ce qu'est le hachage et de ce qu'il 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 (la base de données stocke généralement un hachage du mot de passe au lieu du mot de passe lui-même) et pour le calcul des sommes de contrôle, paquets de données, etc.

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

Le commencement

L'algorithme MD5 est un algorithme de hachage 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 RFC 1321. Après cela, MD5 a été utilisé pour résoudre diverses tâches, depuis le hachage des mots de passe jusqu'au CMS en passant par la création de signatures numériques et de certificats SSL.

Le fait que l'algorithme MD5 puisse être fissuré a été mentionné pour la première fois en 1993. Les chercheurs Bert den Bauer et Anton Bossilaris ont montré que des pseudocollisions sont possibles dans l'algorithme. Trois ans plus tard, en 1996, Hans Dobbertin publie un article dans lequel il prouve l'existence de collisions et décrit la possibilité théorique de piratage de MD5. Il n'était pas encore piraté, mais le monde a commencé à parler d'algorithmes de hachage plus fiables, par exemple SHA1 (à l'heure où nous écrivons, il est déjà prouvé qu'il y a des collisions dans cet algorithme, je recommande SHA2) ou RIPEMD-160.

Premières attaques

La rupture directe de MD5 a commencé le 1er mars 2004. CertainKey Cryptosystems a lancé le projet MD5CRK, un système de recherche de collision distribuée. Le but du projet était de rechercher deux messages avec des codes de hachage identiques. Le projet s'est achevé 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, qui permet de trouver des collisions par méthode analytique pour un temps plus ou moins acceptable. Avec cette méthode, il est possible d'identifier les collisions sur un cluster IBM p690 en seulement une heure (c'est dommage que je n'ai pas une telle maison).

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

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

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

Beaucoup de travail a également été fait pour accélérer la fissuration des hachages. En 2007, Kevin Breeze a présenté un programme qui utilise Sony PlayStation3 pour le piratage MD5. Il a réussi à obtenir de très bons résultats: 1,4 milliard de hash 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 rechercher des collisions, ce qui permettait d'augmenter sa vitesse plusieurs fois, surtout si elle était exécutée à l'aide de plusieurs cartes vidéo simultanément.

La carte graphique 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 à la recherche de collisions.

Est-ce la fin?

En 2011, l'IETF a accepté de modifier la RFC 1321 (MD5) et la RFC 2104 (HMAC-MD5). Ainsi, le document RFC 6151 est apparu: il reconnaît que l'algorithme de chiffrement MD5 est dangereux et recommande de ne pas l'utiliser. À mon avis, ce document a officiellement mis fin à MD5.

Cependant, malgré le fait que l'algorithme MD5 ait été officiellement reconnu comme dangereux, il existe des milliers sinon des dizaines et des centaines de milliers d'applications qui l'utilisent pour stocker les mots de passe, les signatures numériques et calculer les sommes de contrôle des fichiers.

En passant, le 31 octobre 2008, le NIST a annoncé une compétition 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 sont déjà définis - c'est BLAKE, Gostl, JH, Keccak et Skein.

Ighashgpu: piratage en utilisant 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 hash de type de mot de passe: d8578edf8458ce06fbc5bb76a58c5ca4.

Pour casser ce hash, je suggère d'utiliser le programme Ighashgpu, qui peut être téléchargé sur www.golubev.com ou trouvé sur notre disque. L'utilitaire est distribué entièrement gratuitement et fonctionne tranquillement sous Windows. Pour accélérer le processus de piratage, Ighashgpu utilise un GPU, vous avez donc besoin d'au moins une carte vidéo nVidia ou ATI avec un support CUDA / ATI Stream.

Les processeurs graphiques modernes sont construits sur une architecture légèrement différente de celle des processeurs conventionnels, de sorte qu'ils sont beaucoup plus efficaces dans le traitement des informations graphiques. Bien que les GPU soient conçus pour gérer les graphiques 3D, leur utilisation pour les calculs conventionnels a connu une tendance au cours des dernières années. Commencez à travailler avec le programme n'est pas facile, mais très simple: décompressez l'archive à n'importe quel endroit sur le disque et commencer le cambriolage en utilisant la ligne de commande Windows:

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

Nous utilisons la méthode ci-dessus pour craquer un hachage spécifique généré par l'algorithme MD5. La longueur maximale d'un mot de passe possible est de sept caractères. Après un certain temps, le mot de passe sera trouvé (qwerty). Essayons maintenant de casser un autre hachage, mais avec des conditions légèrement différentes. Laissez notre hash a la forme d11fd4559815b2c3de1b685bb78a6283, mais comprend des lettres, des chiffres, des traits de soulignement et a le suffixe "_admin". Dans ce cas, nous pouvons utiliser la recherche par mot de passe 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é pour la force brute, et le paramètre '-m' spécifie le masque de mot de passe. Dans notre cas, le masque se compose de six caractères arbitraires, suivis d'une combinaison de "_admin". Le choix du mot de passe ne sera pas difficile non plus.

Collisions - une collision en cryptographie est appelée deux blocs de données d'entrée différents qui, pour une même fonction de hachage, donnent le même hachage. Chaque fonction de sortie produit 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 qu'il y a des collisions pour tout algorithme de hachage. Cependant, la probabilité que vous puissiez trouver une collision dans un "bon" algorithme tend pratiquement à zéro. Malheureusement, ou heureusement, les algorithmes de hachage peuvent contenir des erreurs, tout comme n'importe quel programme. Beaucoup de fonctions de hachage ont été brisées ou le seront bientôt. Dans ce cas, "casser" signifie trouver une collision dans un temps très inférieur à l'infini déclaré.

Ighashgpu: Listes

Essayons maintenant de casser plusieurs mots de passe à la fois. Supposons que nous ayons une base de données de hachages de mots de passe entre nos mains. On sait que chaque mot de passe se termine par les caractères c00l:

f0b46ac8494b7761adb7203aa7776c2a
f2da202a5a215b66995de1f9327dbaa6
c7f7a34bbe8f385faa89a04a9d94dacf
cb1cb9a40708a151e6c92702342f0ac5
00a931d3facaad384169ebc31d38775c
4966d8547cce099ae6f666f09f68458e

Enregistrez les hachages dans le fichier encrypted.dat et lancez Ighashgpu comme suit:

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

Une fois le programme terminé, le fichier ighashgpu_results.txt apparaît dans le dossier Ighashgpu avec les mots de passe bloqués:

f0b46ac8494b7761adb7203aa7776c2a:1rootxc00l
f2da202a5a215b66995de1f9327dbaa6:pwd12xc00l
c7f7a34bbe8f385faa89a04a9d94dacf:pwd34yc00l

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

Ighashgpu: sel

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

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

Par conséquent, nous avons reçu le hachage 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 obtenu le mot de passe requis facilement et rapidement.

Mathématiques amusantes - Pour le mot de passe à 8 caractères, composé des 126 premiers caractères ASCII, 63 527 879 748 485 376 combinaisons possibles sont disponibles. Pour 254 caractères, le nombre de combinaisons possibles augmente à 17 324 859 956 700 833 536, soit 2,7 milliards de fois plus que les personnes sur notre planète. Si vous créez un fichier texte contenant tous ces mots de passe, il faudra des millions de téraoctets. Bien sûr, dans le monde moderne c'est possible, mais le coût de stockage d'un tel fichier sera simplement transcendantal.

Cambriolage de MD5 en mode turbo

Pirater des hachages à travers une recherche complète même sur le meilleur matériel prend beaucoup de temps, surtout si le mot de passe comporte plus de huit caractères. Le moyen le plus simple d'augmenter la vitesse de correspondance des mots de passe est de créer une base de données de tous les hashs pour un ensemble de caractères particulier. Dans les années 80 du siècle dernier, les pirates croyaient que lorsqu'ils auront un matériel plus puissant, 640 Ko de mémoire et un disque dur de 10 Mo, alors une telle base deviendra une réalité et la sélection de tout mot de passe deviendra une affaire minutieuse. Cependant, le fer s'est développé, et le rêve est resté un rêve. La situation n'a changé qu'en août 2003, après que Philip Oeslin, Ph.D. en réseautage informatique de l'Institut suisse de technologie de Lausanne, ait publié son article sur le problème du choix du meilleur rapport temps-temps. Il a décrit la méthode de piratage des 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 soumis à une fonction de réduction qui convertit le hachage en 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 sur la table. Pour restaurer le mot de passe, nous appliquons la fonction de réduction au hachage source et recherchons le mot de passe possible dans la table. S'il n'y a pas de mot de passe dans la table, nous le hacherons et calculerons le prochain mot de passe possible. L'opération est répétée jusqu'à ce qu'un mot de passe soit trouvé dans la table rainbow. Ce mot de passe représente la fin de l'une des chaînes. Pour trouver le mot de passe d'origine, vous devez réexécuter la conversation entière. Une telle opération ne prend pas beaucoup de temps, en fonction de l'algorithme de construction de la chaîne, elle dure généralement quelques secondes ou minutes. Les tables "Rainbow" vous permettent de réduire considérablement la quantité de mémoire utilisée par rapport à la recherche conventionnelle. Le seul inconvénient de la méthode décrite est qu'il faut beaucoup de temps pour construire des tables.

Maintenant passons des mots aux actes et essayons de casser quelques hashs de mot de passe en utilisant cette méthode.

Rainbow tables - "Rainbow" tables - c'est un type spécial de dictionnaire, qui contient une chaîne de mots de passe et vous permet de sélectionner un mot de passe en quelques secondes ou minutes avec une probabilité de 85-99%.

Piratage "irisé"

Vous devez d'abord décider du programme. Personnellement, j'aime le RainbowCrack, qui est gratuit et fonctionne à la fois sur Windows et Linux. Il supporte 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. Ici tout n'est pas si simple: vous pouvez soit les télécharger gratuitement, soit les acheter, soit les générer vous-même. L'une des plus grandes archives de tableaux gratuits est disponible sur le site Web du projet Free Rainbow Tables.

En passant, vous pouvez aussi aider le projet si vous téléchargez le client depuis le site et rejoignez un réseau international distribué qui génère des tables "arc-en-ciel". Au moment de la rédaction de ce document, 3 tables TB 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 commander sur le même site des disques avec des tableaux "arc-en-ciel". À l'heure actuelle, il existe trois paquets: LN / NTLM, MD5 et SHA1 - 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);
  • jeu de caractères - 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 sont les "nombres magiques" décrits dans l'article de Philip Oeschlin

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

  1. table_index - l'index de la table "arc-en-ciel", qui peut être utilisé lors de la division de la table en plusieurs fichiers. J'ai utilisé 0, puisque ma table se composait 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 le paramètre qui détermine le début de la chaîne. Les créateurs du programme sont invités à utiliser uniquement ce nombre comme ce paramètre (j'ai utilisé 0). Exécutez 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 une table de mots de passe composée de chiffres et de majuscules de l'alphabet latin et ayant une longueur de un à sept caractères. Sur mon Eee PC avec le processeur Intel Atom N450, ce processus a pris presque deux jours :) . En conséquence, j'ai obtenu le fichier md5loweralpha-numeric # 1-702000? 975054890.rt dans la taille de 1,5 Go.

Ensuite, la table résultante doit être triée pour optimiser la recherche de la chaîne désirée. 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 le mot de passe lui-même. Tout d'abord, nous allons essayer de trouver le mot de passe pour un hachage: d8578edf8458ce06fbc5bb76a58c5ca4. Lancez rcrack_gui.exe et sélectionnez Ajouter un hachage ... dans le menu Fichier. Dans la fenêtre apparue, entrez un hachage et cliquez sur OK. Maintenant, sélectionnez le fichier avec la table arc-en-ciel. Pour ce faire, utilisez l'option Rechercher les tableaux Rainbow ... dans le menu Rainbow Table. Dans la fenêtre qui s'ouvre, pour sélectionner un fichier, recherchez le fichier avec la table, je l'ai md5_loweralpha-numeric # 1-7_0_2000x97505489_0.rt, puis cliquez sur Ouvrir. Quelques secondes plus tard, le mot de passe est entre nos mains! Une opération similaire peut être effectuée sur la liste de hachage à partir du fichier.

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

Tables "arc-en-ciel" vs. CPU vs. GPU

Je pense que vous avez remarqué à quelle vitesse Ighashgpu est capable de craquer les hachages MD5 par la force brute, et le fait que RainbowCrack le fait encore plus vite 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 brutes le mot de passe sur le processeur (et est l'un des meilleurs parmi les programmes de ce type). Voici ce qui s'est passé pour les tables GPU (nVidia GeForce GT 220M), CPU (Intel Atom N450, deux cœurs) et "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 voir, la vitesse de la recherche en utilisant le processeur est beaucoup moins que d'utiliser un 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, de sorte que la vitesse de l'énumération des mots de passe augmente plusieurs fois. Je pense que vous avez remarqué que la vitesse de correspondance des mots de passe à 4 et 5 caractères est inférieure à la vitesse de sélection d'un mot de passe de six ou sept caractères. Cela est dû au fait que la recherche de mot de passe commence seulement après le chargement de la table en mémoire. Il s'avère que sur treize secondes en moyenne treize est dépensé pour le téléchargement et trois - sur le hachage un hachage.

Все методы взлома MD5
Table irisée de l'intérieur

bit.ly/vEhdir - Ajout d'un nouvel algorithme de hachage à RainbowCrack en utilisant l'API.

bit.ly/vTSB9K - description du format de la table rainbow.

Au lieu de conclure

En fin de compte, j'aimerais 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. À ce stade, il vaut la peine d'utiliser l'une des fonctions de hachage cryptographique SHA2 ou SHA3 (dès que la norme correspondante est publiée). Deuxièmement, n'utilisez pas les fonctions de hachage directement. Essayez toujours d'utiliser "salt" et combinez différents algorithmes. Et troisièmement, choisissez des mots de passe complexes et arbitraires 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 intrus.