Les Rainbow Tables

“Ahhhhh trop bien on va aller au pays des bisounours, jouer avec les licornes, les arcs-en-ciel et.. les tables !”

Vous ne croyez pas si bien dire…..

Pour ce tuto vous aurez besoin :

De quelques bases en mathématiques (algèbre linéaire de préférence) mais pas beaucoup !
D’une distribution Linux (j’utiliserai pour ma part 5.10.0-kali3-amd64)

Voilà !

“Wow c’est tout ?”

Et.. Oui !

“Ça sent l’arnaque à plein nez ton truc…”

I) Théorie

Comme tout bon tutoriel…

“Ouais donc pas comme les tiens”

Je disais… comme tout bon tutoriel nous allons commencer par un peu de théorie. Une fois n’est pas coutume , regardons ce que nous dis le grand professeur Wikipédios à ce sujet :

Une rainbow table (littéralement table arc-en-ciel) est, en cryptanalyse, une structure de données créée en 2003 par Philippe Oechslin de l’EPFL¹ pour retrouver un mot de passe à partir de son empreinte.
https://fr.wikipedia.org/wiki/Rainbow_table

Mmmmmm d’accord et regardons un peu plus de détails ?

La rainbow table est constituée de paires de mots de passe (i.e. chaque ligne possède un mot de passe de départ et un mot de passe d’arrivée). Pour calculer la table, on établit des chaînes grâce à un mot de passe initial. Celui-ci subit une série de réductions et de hachage afin d’obtenir des éléments intermédiaires (mots de passe et empreintes correspondantes). La fonction de réduction transforme une empreinte en un nouveau mot de passe. Afin d’éviter des problèmes de collision, plusieurs fonctions de réduction sont utilisées. Après plusieurs milliers d’itérations, on obtient un mot de passe en bout de chaîne. C’est celui-ci qui est stocké avec le mot de passe à l’origine de cette chaîne. Le reste de la chaîne n’est pas conservé afin de limiter la mémoire nécessaire. Il est toutefois possible de les retrouver en calculant l’ensemble de la chaîne à partir de l’élément en tête de liste.
On recommence avec un autre mot de passe pour établir une nouvelle chaîne et ainsi de suite jusqu’à constituer une table dont les statistiques sont suffisantes pour garantir le succès de l’attaque.
https://fr.wikipedia.org/wiki/Rainbow_table

Tout ceci peut donc être résumé par ce petit schéma :

Pour faire plus simple et plus concis , les Rainbow Tables permettent d’obtenir un compromis temps/mémoire intéressant lorsqu’il s’agit d’attaquer des mots de passes.

II) La pratique (déjà ?)

Et oui déjà, je ne comptais pas vous assommer avec trop de détails mathématiques non plus ! On va maintenant voir comment on peut générer ces tables et s’en servir !

A) La génération

Pour la suite de ce tuto nous allons nous servir d’une suite d’outils très connue à savoir RainbowCrack. Sous kali il suffit de l’installer comme suit :

apt install rainbowcrack

Pour générer les tables, nous aurons besoin de l’outil rtgen (qui est dans la suite RainbowCrack) regardons un peu comment se servir de l’outil :

Voyons un peu à quoi correspondent les arguments demandés par rtgen :

hash_algorithm : L’algorithme de hash pour lequel nous voulons générer les Rainbow Tables. (MD5,SHA-1…)
charset : L’ensemble des caractères (lettres, chiffres…) utilisés pour générer une chaine de caractère en clair à l’aide des Rainbow Tables
plaintext_len_min: La longueur minimale de la chaine de caractère en clair.
plaintext_len_max : La longueur maximale de la chaine de caractère en clair.
table_index : Cet argument permet de sélectionner la fonction de réduction pour générer notre Rainbow Table. L’idée derrière la fonction de réduction et de nous permettre de gagner du temps sur la génération en enlevant les combinaisons qui ne nous serviront pas. Néanmoins il ne faut pas tomber dans le piège de vouloir gagner trop de temps, le cas échéant nous risquerions de ne pas inclure des combinaisons qui nous permettraient de trouver le mot de passe que l’on cherche.
chain_len : Cet argument définit la taille de chacune des tables, au plus la table est grande au plus le nombre de mot de passe en clair sont hashés et stockés dans la table.
chain_num : Le nombre de chaines que l’on va générer, chaque chaine à une taille de 16 octets. Typiquement une Rainbow Table est un tableau constitué de ces chaines.
part_index : Permet de segmenter les fichiers générés contenant les tables, pour les stocker sur différents supports par exemples. Le fait de mettre la valeur 0 permet de tout stocker dans un seul fichier.

Utilisons un des exemples donné par rtgen :

rtgen md5 loweralpha 1 7 0 1000 1000 0

Donc nous allons créer une Rainbow Table avec des hashs au format MD5 pour une texte en clair de taille de 1 à 7 caractères, avec des caractères allant de a à z (tous en minuscule) en ne réduisant pas les hashs, le tout avec des tables de taille 1000 et en créant 1000 chaines. Le tout sera stocké dans un seul fichier.

Vous pourrez ainsi retrouver le fichier généré (dans mon cas le fichier se nomme : md5_loweralpha#1-7_0_1000x1000_0.rt) dans le dossier ‘/usr/share/rainbowcrack/’

“Ouais mais la on génère qu’une toute petite table elle nous servira à rien , nous prend pas pour des pingouins de la dernière pluie !”

Bon bon j’ai compris…

Reprenons avec ces 6 commandes :

rtgen md5 loweralpha-numeric 1 7 0 2400 24652134 0
rtgen md5 loweralpha-numeric 1 7 1 2400 24652134 0
rtgen md5 loweralpha-numeric 1 7 2 2400 24652134 0
rtgen md5 loweralpha-numeric 1 7 3 2400 24652134 0
rtgen md5 loweralpha-numeric 1 7 4 2400 24652134 0
rtgen md5 loweralpha-numeric 1 7 5 2400 24652134 0

Faites attention en lançant ces commandes , votre CPU sera énormément sollicité, je vous conseille de les lancer une par une.

Ici nous utilisons le charset loweralpha-numeric , qui contient donc les lettres minuscules et les chiffres de 0 à 9. Le temps de génération sera nettement plus long vous allez voir ! (Environ 20-25 minutes pour chaque partie de la table chez moi) Chaque partie de la table devrait faire aux alentours de 377Mo.

Avec ces 6 tables générées nous allons déjà avoir plus de résultats vous pouvez me croire.

B) Soyons écolo’

Si ce titre ne vous parle pour l’instant pas trop c’est normal…

“Tu nous lève les mots de la bouche…”

Avant de pouvoir utiliser nos tables générés précédemment nous allons devoir avant tout les trier !

“D’où le titre… trop drôle… (c’est faux)”

.. Le fait de trier va entre autre permettre d’accélérer les accès et les recherches dans les tables, ce qui est tout de même plutôt pratique !

Pour ce faire rien de plus simple , regroupez vos tables dans un même dossier, placez vous dans ce dossier avec votre terminal, et utilisez la commande suivante :

rtsort $(pwd)

C) It’s time to crack !

“Ah bah enfin !”

Oui nous allons enfin pouvoir effectuer une attaque cryptographique sur un hash md5 !

Pour l’exemple je vais utiliser ce hash :

f01c021924a023329fd6fe1b290f1a41

Ce hash n’est d’autre que le hash md5 de la chaîne “truc1” , libre à vous d’essayer d’autres chaînes bien évidemment.

Pour pouvoir utiliser nos Rainbow Tables précédemment générées et trouver la valeur de notre hash nous utiliserons cette commande :

rtcrack "chemin vers les rainbow tables" -h "hash à casser"

Dans mon exemple en supposant que vous lancier “rtcrack” depuis l’endroit ou se trouve vos tables, cela donnera :

rcrack $(pwd) -h f01c021924a023329fd6fe1b290f1a41

Après seulement quelques instants :

Nous venons de trouver bien la chaine : “truc1” , Victoire !

III) Quelques possibles améliorations et digression

Croyez le ou non mais il est possible d’optimiser encore plus les Rainbow Tables. Bien sur cela prendra plus de temps à générer mais cela peut faire gagner du temps sur l’attaque de mot de passe.

Une des manières d’arriver à ce résultat est de convertir le format initial des Rainbow Tables dans d’autres formats plus adaptés au utilisations que l’on souhaite en faire.

Je vous met à disposition la page du projet officiel de rainbow crack portant sur ce sujet :

https://project-rainbowcrack.com/convert.htm

N’oubliez pas que de convertir les Rainbow Tables peut être dans certains cas plus long que de les générer.

Il est également possible d’utiliser vos GPU pour accélérer les attaques de mot de passe , en effet l’outil “rtcrack” que nous avons utiliser plus haut dispose de deux variantes “rcrack_cl_amd” pour les GPU AMD et “rcrack_cuda” pour les GPU Nvidia. Ils s’utilisent de la même manière que l’outil “rtcrack” ainsi , en reprenant l’exemple d’attaque vu précédemment les deux commandes seront :

rcrack_cl_amd $(pwd) -h f01c021924a023329fd6fe1b290f1a41

rcrack_cuda $(pwd) -h f01c021924a023329fd6fe1b290f1a41

Il est également à noter que ces deux programmes supportent les multiples GPU, bien qu’il soit conseillé de disposer de plusieurs fois le même modèle de GPU pour des performances optimales.

IV) Conclusion

Bon nous voilà arrivé à bon port !

“Contre toute attente…”

… Pour conclure je vous propose de faire une petit récapitulatif sur ce que sont les Rainbow Tables, ainsi que de voir quels sont les avantages et les inconvénients de les utiliser.

“Et si on est pas d’accord ?”

Et bien nous allons le faire quand même !

Rappelons premièrement que les Rainbow Tables sont des tables pré-calculées de hashs , qui permettent de renverser l’algorithme cryptographique des fonctions de hash. Cela permet entre autre d’utiliser une Table pré-calculée pour retrouver le texte en clair à partir d’un hash donné.

Pour essayer de faire une analogie que les puristes trouveront un peu vague possiblement, mais que je trouve assez parlante, les Rainbow Tables sont un peu comme le discriminant “b2 -4ac” vis à vis des équations du second degrés, c’est une manière rapide de trouver le résultat sans avoir besoin de tout tester.

De ce fait cela explique pourquoi nous avons pu retrouver notre mot de passe dans l’exemple ci-dessus en seulement quelques secondes, puisque nous avons renversé le processus de hash.

Les Rainbow Tables de par leurs natures disposent ainsi d’avantages mais aussi d’inconvénients, le tableau ci-dessous vous donnera une liste (non exhaustive) de ces avantages et inconvénients :

Avantages	Inconvénients
– Attaque de mot de passe très rapide – Plus léger en terme de sollicitation de CPU qu’une attaque “traditionnelle” – Probabilité de réussite supérieure aux autres méthodes	– Prend énormément de place sur le disque pour stocker les tables – Pour être optimale l’attaque demande d’avoir une voir plusieurs GPU – Demande une grosse quantité de RAM pour la génération

Sachez que vous pouvez directement télécharger les tables déjà générées en fonction de vos besoins, je vous laisse des liens à la fin à ce sujet.

Voilà j’espère que ce tutoriel vous sera utile , et que vous aurez pris du plaisir à le suivre !

A très bientôt pour un nouveau tuto !

ZeR0-@bSoLu

https://project-rainbowcrack.com/

https://project-rainbowcrack.com/table.htm