Attaque par compromis temps/mémore (RainbowCrack)

Introduction

Il existe toujours un compromis à faire entre puissance de calcul et espace de stockage. On peut le constater dans les formes les plus élémentaires de l’informatique et dans la vie de tous les jours. Les fichiers MP3 utilisent la compression pour enregistrer un fichier audio de haute qualité dans un espace relativement réduit, mais il faut des ressources informatiques plus importantes pour les lire. Les calculatrices de poche font le compromis inverse, en stockant une table de correspondance pour certaines fonctions, comme sinus et cosinus, afin d’éviter les calculs lourds. Ce compromis se retrouve également en cryptographie dans ce qui est appelé attaque par compromis temps/mémoire.

Problématique

L’attaque par compromis a pour but de décrypter un mot de passe haché en essayant de retrouver le mot de passe en claire. Il existe plusieurs types d’attaques de mot de passe possible. L’attaque par dictionnaire est une technique efficace mais il faut que le mot de passe soit dans le dictionnaire et le temps d’exécution de l’attaque peut durer très longtemps. L’attaque par force brute, consiste quant à elle de tester tous les mots de passe possible, mais il faudrait des millions d’années pour pouvoir tester tout cela. Une autre idée intéressante se fonde sur une très grande table de correspondance hachée. Si les valeurs de hachage de tous les mots de passe possibles sont pré-calculées et enregistrées dans une structure de données, n’importe quel mot de passe peut être craqué en un temps proportionnel au temps de la recherche. Avec une recherche dichotomique, ce temps est en O(log2 N) où N est le nombre d’entrées. Cependant, une telle table de correspondance occuperait approximativement 100 000 téra-octets. Le type d’attaque que nous allons voir réduit considérablement le temps de calcul et la taille de stockage nécessaire.

Principe général

La technique par force brute génère tous les textes clairs possibles et calcul le hash correspondant, puis elle compare les valeurs de hash résultantes avec le hash à craquer. Par contre, dans la technique de compromis temps-mémoire, la tâche de calcul de hachage est effectué à l'avance et les résultats sont stockés dans les « Rainbow Table ». Après cela, les hash peuvent être consultés à partir des tables arcs en ciel lors du crack du mot de passe. Le processus de calcul de la force brute est donc évité. Une fois le temps du pré-calcul terminé, la performance consultation de table peut être des centaines ou des milliers de fois plus vite que la force brute.

Principe détaillé

La méthode s’appuie sur une forme de compression avec perte. À la place d’une table de correspondance exacte, plusieurs milliers de valeurs en clair possibles sont retournées pour un même hachage de mot de passe. Ces valeurs peuvent être vérifiées rapidement afin de converger vers le mot de passe en claire originel et la compression avec perte permet de réduire énormément la taille de l’espace de stockage. Prenons l’exemple suivant,

Dans ce cas, les bits correspondant aux paires de texte en clair seront activés dans la colonne pour HEA, lorsque ces paires texte en clair/hachage sont ajoutées à la matrice. Une fois que la matrice est complète, lorsqu’une valeur de hachage comme est donnée, la colonne pour HEA est examinée et la matrice à deux dimensions retourne les valeurs te,!J ". et "8 pour les deux premiers caractères du texte en clair. Il existe quatre matrices comme celle-ci pour les deux premiers caractères, qui utilisent des sous-chaînes chiffrées à partir des caractères 2 à 4, 4 à 6, 6 à 8 et 8 à 10, chacune avec un vecteur différent des valeurs en clair possibles pour les deux premiers caractères. Chaque vecteur est extrait et ils sont combinés par un ET bit à bit. Ainsi, on ne conserve que les bits activés qui correspondent aux paires de texte en clair donnée comme des possibilités pour chaque sous-chaîne de texte chiffré. Il existe également quatre matrices comme celle-ci pour les deux derniers caractères du texte en claire.

RainbowCrack

Pour un cas pratique, nous allons utiliser l’outil RainbowCrack qui intègre déjà des outils pour pouvoir réaliser l’attaque par compromis temps/mémoire.

Rainbowcrack est un outil pour cracker les hash des mots de passe. Il utilise les tables arc en ciel qui se base sur la technique de compromis temps-mémoire. Rainbowcrack arrive avec les outils suivants :

• rtgen : cet outil est utilisé pour générer les tables arc en ciel, cette étape est parfois nommée stade de pré-calcul. Cette étape peut être très lente. Mais une fois ce calcul effectué, l’outil de hack sera beaucoup plus rapide. Il supporte plusieurs algorithmes dont : NTLM, MD2, MD4, MD5, SHA1, et RIPEMD160.
• rtsort : est utilisé pour trier les tables arc en ciel générée par rtgen.
• rcrack : est utilisé pour rechercher dans les tables arc en ciel le hash du mot de passe.

Etape 1 : Générer ou Télécharger une table rainbow

Pour générer une table rainbow, on utilise l’outils rtgen qui est fourni avec RainbowCrack. La syntaxe générale de la commande rtgen est comme suit.

#./rtgen hash_algorithm charset plaintext_len_min plaintext_len_max table_index chain_len chain_num part_index

Dans lequel on a :

paramètre	explication
hash_algorithm	md5, MD2, MD4, SHA1, ....
charset	Le type de caractères, exemple "loweralpha-numeric", ...
plaintext_len_min	le nombre minimum de caractères que le texte clair peut contenir
plaintext_len_max	le nombre maximum de caractères que le texte clair peut contenir
table_index	Le paramètre table_index sélectionne la fonction de réduction
chain_len	C'est la longueur de la chaîne arc-en-ciel. Plus la chaîne Rainbow stocké est longue, plus les textes clairs nécessitent de temps pour générer
chain_num	Nombre de chaînes arc-en-ciel à générer. Rainbow table est tout simplement un tableau de chaînes arc-en-ciel. La taille de chaque chaîne arc-en-ciel est de 16 octets.
part_index	Pour stocker une grande table arc-en-ciel dans de nombreux fichiers plus petits, utilisez un nombre différent dans ce paramètre pour chaque partie et conservez tous les autres paramètres identiques.

Nous allons alors exécuter la commande suivante :

#./rtgen md5 loweralpha-numeric 1 7 0 3800 33554432 0

Cette commande va générer une table arc en ciel pour craquer les mots de passe chiffrés en md5, composé de « loweralpha-numeric » c’est à dire [abcdefghijklmnopqrstuvwxyz0123456789]

On obtient alors ensuite un fichier nommé  "md5_loweralpha-numeric#1-7_0_3800x33554432_0.rt"

Les tables peuvent aussi être téléchargées depuis certains sites, comme : http://www.freerainbowtables.com/en/tables/ ou http://rainbowtables.shmoo.com/. Cela fait gagner du temps.

Etape 2 : Trier la table rainbow

Nous allons ensuite trier la table rainbow avec la commande suivante:

#./rtsort md5_loweralpha-numeric#1-7_0_3800x33554432_0.rt

Etape 3 : Craquer les mots de passe

Enfin, pour craquer un mot de passe haché, il faut exécuter la commande suivante

#./rcrack *. rt-h hash_du_mot_de_passe

Dans notre exemple, on tape la commande suivante :

#./rcrack *. rt-h ab56b4d92b40713acc5af89985d4b786

On obtient le resulat suivant

On a donc réussi à obtenir le mot de passe qui est : abcde

Conclusion

Cette technique d’attaque de mot de passe est une bonne technique comparée à la technique de force brute ou l’attaque par dictionnaire. On a un gain considérable en temps et en espace de stockage. Cependant, le problème lié aux valeurs de salt est toujours présent puisqu’un mot de passe en claire produira plusieurs hachages différents en fonction de la valeur de salt. Cela alors complique aussi la tâche pour une attaque par compromis temps-mémoire