Que sont les Rainbow Tables ?

Ce qui ressemble à un jeu d’enfant est en réalité un outil puissant pour déchiffrer les mots de passe. Un groupe assez important de personnes, des deux côtés de la loi, met beaucoup d’énergie à craquer les mots de passe, parce qu’ils se promettent d’en tirer profit dans un but criminel ou parce qu’ils sont des experts qui doivent régulièrement vérifier l’efficacité des normes de sécurité. Dans certaines circonstances, les tables arc-en-ciel permettent de révéler les mots de passe en quelques secondes.

Même si vous n’êtes pas à un hacker, il est toutefois intéressant d’en connaitre le principe. En tant qu’internaute, vous comprendrez ainsi mieux pourquoi des mots de passe complexes sont nécessaires et en tant que fournisseur d’une offre Web, pourquoi vous devez le prendre en compte pour sécuriser vos mots de passe.

Les mots de passe ne sont plus (espérons-le) stockés en clair sur Internet. Lorsque les utilisateurs d’une plateforme Web définissent un mot de passe pour leur compte, la chaîne n’apparait en texte clair dans aucune base de données sur un serveur. Cette procédure serait bien trop peu sûre : un hacker n’aurait qu’à accéder à la base de données et peut ainsi directement entrer dans le compte personnel de chaque utilisateur.

Pour le commerce électronique, les services bancaires ou services d’administration en ligne cela serait fatal. Au lieu de cela, les services en ligne utilisent différents mécanismes cryptographiques pour chiffrer les mots de passe des utilisateurs : seule une valeur de hachage du mot de passe apparaît dans les bases de données elles-mêmes.

Même si vous connaissez la fonction crypto, vous ne pouvez pas déterminer directement le mot de passe à partir de la valeur de hachage. Il n’y a aucun moyen de recalculer l’opération. À la place, les pirates utilisent par exemple des attaques par force brute : un programme informatique qui essaie constamment jusqu‘à ce qu’il ait trouvé la chaîne de caractères correcte.

Cette méthode peut aussi être combinée avec des dictionnaires de mots de passe. Ces fichiers, qui peuvent être obtenus via Internet, contiennent de nombreux mots de passe qui sont très populaires ou qui ont été capturés lors d’une attaque précédente sur un système. Cela permet aux pirates de gagner du temps lors du décryptage : auparavant, ils tentaient tous les mots de passe du dictionnaire. Selon la complexité des mots de passe (longueur et type de caractères utilisés), cela peut toutefois coûter du temps et de la capacité de calcul.

Les Rainbow Tables vont plus loin que les dictionnaires de mots de passe : ces tables peuvent également être trouvées sur Internet et peuvent être utilisées pour casser les mots de passe. Ces fichiers, dont certains peuvent avoir une taille de plusieurs centaines de giga-octets, contiennent des mots de passe et leurs valeurs de hachage conformément à l’algorithme de cryptage utilisé. Mais pas complètement : au lieu de cela, certaines chaînes sont créés à partir desquelles les valeurs réelles peuvent être facilement calculées, réduisant ainsi les besoins en mémoire des tables encore très grandes. Les tables arc-en-ciel peuvent donc être utilisées pour assigner des valeurs de hachage trouvées dans une base de données à leurs mots de passe en texte clair.

Pour comprendre le fonctionnement des tables arc-en-ciel, il faut au moins considérer le fonctionnement de base des algorithmes de cryptage. Il sera alors plus facile de comprendre les avantages des tables préfabriquées et donc aussi le compromis temps-mémoire.

Depuis que les fonctions de hachage cryptographiques ont été utilisées dans le cryptage, les algorithmes correspondants ont changé à maintes reprises. Des normes qui étaient considérées comme inviolables il y a seulement 10 ans, sont aujourd’hui considérées comme des violations courantes de la sécurité. Ce qu’ils ont tous en commun, cependant, c’est que le contenu à chiffrer passe par des algorithmes et qu’une valeur de hachage est générée à la fin. Cette valeur de hachage est généralement un nombre hexadécimal d’une certaine longueur. Quelle que soit la longueur du contenu original, au final la valeur de hachage est toujours de 128 bits. Trois propriétés sont cruciales pour le cryptage :

1. La même entrée génère toujours la même valeur de hachage : ce n’est qu’alors que la valeur peut fonctionner comme une somme de contrôle. Le mot de passe saisi est-il identique au mot de passe stocké dans la base de données ? le système ne peut accorder l‘accès que si les deux valeurs de hachage sont identiques.
2. Une valeur de hachage doit toujours être unique : des entrées différentes ne doivent pas générer la même valeur de hachage. C’est la seule façon pour la fonction de s’assurer que le mot de passe correct a été saisi. Étant donné que le nombre de valeurs de hachage possibles est limité, mais que le nombre d‘entrées possibles ne l’est pas, de telles collisions ne peuvent pas être exclues. Les fonctions de hachage modernes et les hachages d’une longueur suffisante minimisent le risque du mieux que possible.
3. Les valeurs de hachage ne peuvent pas être recalculées : le contenu original ne peut jamais être dérivé de la valeur de hachage elle-même. C’est pourquoi les valeurs de hachage ne peuvent pas être décodées, comme c’est parfois prétendu. Au lieu de cela, les valeurs de hachage peuvent seulement être tracées.
4. Les fonctions de hachage doivent être assez complexes, mais tout de même pas trop : pour garantir la sécurité, un algorithme ne doit pas fonctionner trop vite, car cela faciliterait aussi le travail des hackers. Mais la conversion ne doit pas non plus être trop complexe, car elle doit aussi être appliquée dans la pratique.

Les valeurs de hachage contenues dans les tables arc-en-ciel ne sont pas créées lors d’une attaque, mais à l’avance. Les hackers peuvent obtenir les tables arc-en-ciel et les utiliser pour chercher des mots de passe. Cependant, ces fichiers sont très volumineux. Rainbow Tables utilise donc une fonction de réduction pour éviter l’encombrement de l’espace de stockage nécessaire : ces fonctions convertissent la valeur de hachage en texte clair. Important : la fonction de réduction n’annule pas la valeur de hachage, de sorte qu’elle n’affiche pas le texte clair (brut) d’origine (par exemple le mot de passe), ce n’est pas possible, à la place, elle en affiche une toute nouvelle.

Une nouvelle valeur de hachage est générée à partir de ce texte. Dans une table arc-en-ciel, cela n’a pas lieu une seule fois, mais plusieurs fois, de sorte qu’une chaîne est créée. Dans le tableau final, cependant, seuls le premier mot de passe et la dernière valeur de hachage d’une chaîne apparaissent. Sur la base de ces informations et en tenant compte des fonctions de réduction utilisées, toutes les autres valeurs peuvent aussi être déterminées. La valeur de hachage à craquer est réduite de façon répétée et hachée selon les mêmes règles, chaque résultat intermédiaire étant comparé aux valeurs du tableau.

Le défi dans le processus de création du tableau est que le contenu source qui représente le début d’une nouvelle chaîne ne doit pas être déjà apparu sous forme de texte brut dans une chaîne précédente. Avec cette technologie, la taille de ces tables peut être extrêmement réduite, et pourtant elles possèdent toujours une taille de plusieurs centaines de giga-octets.

Un compromis temps-mémoire est lorsque vous acceptez une durée plus longue en faveur d’une utilisation moindre de la mémoire ou bien l’inverse. Une attaque par force brute occupe très peu d’espace mémoire, puisque les calculs cryptographiques sont effectués de nouveau à chaque attaque. Une table, d’autre part, dans laquelle des milliards de mots de passe sont représentés avec leurs valeurs de hachage, occupe une énorme quantité d’espace de stockage, mais peut les décrypter très rapidement. Les Rainbow Tables sont un compromis entre les deux : le principe effectue également des calculs en temps réel, mais dans une moindre mesure, ce qui permet d’économiser beaucoup d’espace de stockage par rapport à des tables complètes.

La situation de départ est simple : vous avez une valeur de hachage et vous souhaitez connaître le mot de passe qui se cache derrière. Tout d’abord, vous recherchez cette valeur de hachage dans la liste. Si vous la trouvez au début ou à la fin d’une chaîne, le mot de passe est trouvé relativement rapidement, car vous n’avez plus qu’à tracer les répétitions de la chaîne et ainsi obtenir le résultat désiré. Mais que se passe-t-il si la valeur de hachage n’est pas trouvée dans la table ?

Dans ce cas, vous commencez par réduire la valeur de hachage, en utilisant la même fonction que celle qui a été utilisée pour créer les chaînes. Le résultat passe ensuite par la fonction de hachage. Répétez cette opération jusqu’à ce que vous trouviez la valeur de hachage dans l’un des points d’extrémité. Cela ne vous donne pas le mot de passe que vous recherchez. Cependant, la chaîne correspondante contenant la valeur de hachage a été trouvée. Par conséquent, on commence maintenant au point de départ de la chaîne et on effectue les réductions et le hachage alternativement jusqu’à obtenir la valeur de hachage recherchée et donc également le texte clair du mot de passe.

En fin de compte, on peut se demander quel est le lien entre les tables et les arcs-en-ciel. Dans la pratique, on n’utilise pas seulement la fonction de réduction, mais une fonction différente à chaque fois. Cela assure un meilleur résultat dans la réduction et évite la répétition des valeurs de hachage dans le tableau, mais présente l’inconvénient que la recherche de combinaisons de valeurs de hachage et de mots de passe dans les chaines est un peu plus complexe.

Par conséquent, les réductions doivent être effectuées dans l’ordre : si l’on suppose que la chaîne avec les réductions R1, R2, R3 a été construite, on commencerait d’abord par la fonction R3 pendant la recherche. Si cela ne donne pas de résultat, accédez d’abord à R2, puis à R3 et ainsi de suite. Dans le tableau, les différentes fonctions de réduction peuvent être marquées avec des couleurs, ce qui peut conduire à un arc-en-ciel coloré avec un nombre correspondant d’itérations, d’où le nom.

Explication : le mot de passe saisi est k. Ainsi, m représente n’importe quel multiplicateur (2000 dans cet exemple). Pour A, on utilise généralement le nombre d’or (0,618). Modulo (mod) extrait le reste d’une division effectuée dans cette fonction par 1. Les parenthèses gaussiennes arrondissent le résultat à un entier à la fin, si nécessaire. Enfin, le résultat h(k) est la valeur de hachage h pour l’entrée k.

Puisque notre valeur de hachage se compose de quatre chiffres, nous commençons avec un 0 : 0408.

Dans une table arc-en-ciel pour cette fonction de hachage, les fonctions de réduction doivent maintenant fonctionner. Une façon très simple de réduire la valeur de hachage est d’utiliser les deux derniers chiffres. Par exemple, dans le cas du mot de passe 78 et de la valeur de hachage associée 0408, la réduction est donc ici 08, dont la valeur de hachage est à nouveau formée à l’aide de la fonction décrite ci-dessus, et ainsi de suite.

La fréquence des répétitions peut être définie librement. Plus vous répétez, moins la Rainbow table a besoin de mémoire, mais le temps de traitement augmente. Dans cet exemple, nous allons effectuer la réduction trois fois.

Le tableau ci-dessus montre les chaînes complètes avec les résultats des fonctions de hachage et de réduction. Cependant, le but d’une table arc-en-ciel est de raccourcir la circonférence. Par conséquent, la Rainbow Table ne contient que les bords gauche et droit de la table. Toutes les autres valeurs peuvent en être dérivées.

Maintenant, toutes les valeurs de hachage ne sont pas disponibles dans le tableau. Par exemple, si vous saviez qu’il y avait un mot de passe derrière la valeur de hachage 1888, vous chercheriez maintenant la table arc-en-ciel et trouveriez que la valeur n’apparait pas dans la table, mais est cachée dans une chaîne. Par conséquent, vous devez réduire la valeur, ce qui donne 88. Cette valeur ne fait pas non plus partie du tableau, de sorte que la valeur de hachage (0768) et la réduction (68) sont à nouveau calculées. La valeur de hachage correspondante 0048 se trouve à la troisième ligne. Mais le mot de passe dans la même ligne (03) n’appartient pas directement à la valeur de hachage, car ce n’est que le début de la chaîne.

Mais il fournit le point de départ pour le calcul suivant : à partir de 03, on calcule la valeur de hachage 1708, qui est réduite à 08 et forme à nouveau la valeur de hachage : 1888, la valeur de hachage recherchée. Le mot de passe 08 appartient à cette valeur.

Quiconque a compris comment les hackers peuvent pénétrer dans les comptes d’utilisateur à l’aide d’une table arc-en-ciel doit être conscient que des mécanismes de défense appropriés doivent être utilisés. Tant les utilisateurs que les responsables du site Web peuvent prendre des mesures pour prévenir ou au moins pour gêner de telles attaques.

Pour les utilisateurs, il s’applique en général : les mots de passe doivent être aussi longs que possible et contenir des lettres majuscules, des lettres minuscules, des chiffres et d’autres caractères, cela aide contre les attaques par force brute et les tables arc-en-ciel, puisque le décryptage devient trop complexe. La taille de la table requise augmente exponentiellement avec la longueur du mot de passe. Il est aussi conseillé de ne pas utiliser de mots réels, mais des chaînes de caractères aléatoires pour éviter les attaques basées sur des dictionnaires. Ainsi, les gestionnaires de mots de passe peuvent aider. Il est également très important de ne pas utiliser les mots de passe plus d’une fois, quelle que soit la forme d’attaque utilisée par les hackers : une fois que quelqu’un a réussi à corrompre une base de données, à déchiffrer des mots de passe et à accéder à des données personnelles, il est facile d’essayer tous les autres comptes sur Internet avec exactement ce même mot de passe.

Mais les opérateurs de serveurs peuvent aussi faire beaucoup pour protéger leurs utilisateurs. Dans la première étape, vous devriez bien sûr essayer de ne pas laisser les hackers accéder aux bases de données avec les valeurs de hachage. Le fait que cela soit plus facile à dire qu’à faire est aussi prouvé par les nombreuses effractions sur les serveurs des grandes entreprises. Par conséquent, vous devez enregistrer la valeur de hachage. Cela commence par le fait qu’aucun algorithme obsolète n’est utilisé.

Le MD5 et le SHA-1 ont longtemps été considérés comme dangereux et les tables arc-en-ciel correspondantes sont faciles à trouver sur Internet. Avec ces derniers, les mots de passe qui ont été hachés comme ceci peuvent être découverts en quelques secondes. Il est donc essentiel d’être constamment informé sur l’existence de nouveaux algorithmes ou si la fonction de hachage utilisée est toujours aussi sûre. SHA-2 et donc aussi sa variante la plus connues SHA-256 sont toujours considérées comme sûres, mais SHA-3 est maintenant aussi disponible, ce qui promet une sécurité encore meilleure et pus longue.

Afin de rendre le décodage à travers les tables arc-en-ciel beaucoup plus complexes, on utilise aujourd’hui ce que l’on nomme en anglais Salt et grain de sable en français : lorsqu’un utilisateur définit un mot de passe, le système crée également une valeur aléatoire : un grain de sable. Cette valeur s’écoule avec le mot de passe dans la fonction de hachage et génère ainsi une valeur différente de celle du mot de passe seul.

Le Salt et la valeur de hachage sont stockés ensemble dans la base de données. Cette circonstance est déroutante : les attaquants qui reçoivent le contenu de base de données ont donc le nom d’utilisateur, la valeur de hachage et le Salt correspondant. En fait, attaques par force brute et par dictionnaires ne sont pas évitées, mais la mesure supplémentaire aide surtout contre les Rainbow Tables. Une telle table est créée à l’avance, basée sur un algorithme de hachage et indépendante de la base de données que vous utilisez. Les grains de sable ne peuvent donc pas être contenus dans les tables arc-en-ciel, puisque le créateur de la table ne connaissait pas encore le Salt.

Un autre avantage du grain de sable, est que les utilisateurs n’ont pas à s’en souvenir. Ils peuvent donc être complètement chaotiques et, surtout, très longs. Cela rend les valeurs de hachage elles-mêmes si complexes qu’il est plus difficile de travailler avec elles. De plus, un Salt empêche deux personnes ou plus d’entrer le même mot de passe et donc d’écrire la même valeur de hachage dans la base de données. Enfin, le grain de sable aide aussi à résoudre le problème que les utilisateurs utilisent le même mot de passe pour différents services. La valeur de hachage stockée est différente pour tous les services en raison du Salt.

En plus du Salt, il y aussi Pepper : ce qui rend plus difficile d’attaquer par force brute ou via des dictionnaires. Le Pepper est aussi une chaîne aléatoire qui, au mieux en combinaison avec le Salt, s’écoule dans la valeur de hachage en même temps que le mot de passe. Contrairement au Salt, le Pepper n’est pas stocké avec d’autres données de connexion dans une base de données, mais séparément et dans l’endroit le plus sûr possible.

Une chaîne fixe est souvent utilisée pour tous les mots de passe sur la plateforme. Par conséquent, Pepper n’aide pas contre le fait que plusieurs utilisateurs ont le même mot de passe, parce qu’ils utilisent aussi le même Pepper, ce qui conduit à des valeurs de hachage identiques. Par conséquent, les administrateurs devraient choisir une combinaison de Salt et Pepper.