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 durée 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,