Que sont les Rainbow Tables ?

Ce qui ressemble à un jeu d’enfant est en réalité un outil puissant pour dé­chif­frer 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 pro­met­tent d’en tirer profit dans un but criminel ou parce qu’ils sont des experts qui doivent ré­gu­liè­re­ment vérifier l’ef­fi­ca­cité des normes de sécurité. Dans certaines cir­cons­tances, les tables arc-en-ciel per­met­tent de révéler les mots de passe en quelques secondes.

Même si vous n’êtes pas à un hacker, il est toutefois in­té­res­sant d’en connaitre le principe. En tant qu’in­ter­naute, vous com­pren­drez ainsi mieux pourquoi des mots de passe complexes sont né­ces­saires et en tant que four­nis­seur 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 uti­li­sa­teurs d’une pla­te­forme Web dé­fi­nis­sent 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 di­rec­te­ment entrer dans le compte personnel de chaque uti­li­sa­teur.

Pour le commerce élec­tro­nique, les services bancaires ou services d’ad­mi­nis­tra­tion en ligne cela serait fatal. Au lieu de cela, les services en ligne utilisent dif­fé­rents mé­ca­nismes cryp­to­gra­phiques pour chiffrer les mots de passe des uti­li­sa­teurs : seule une valeur de hachage du mot de passe apparaît dans les bases de données elles-mêmes.

Même si vous con­nais­sez la fonction crypto, vous ne pouvez pas dé­ter­mi­ner di­rec­te­ment le mot de passe à partir de la valeur de hachage. Il n’y a aucun moyen de re­cal­cu­ler l’opération. À la place, les pirates utilisent par exemple des attaques par force brute : un programme in­for­ma­tique qui essaie cons­tam­ment jusqu‘à ce qu’il ait trouvé la chaîne de ca­rac­tères correcte.

Cette méthode peut aussi être combinée avec des dic­tion­naires de mots de passe. Ces fichiers, qui peuvent être obtenus via Internet, con­tien­nent de nombreux mots de passe qui sont très po­pu­laires 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é­cryp­tage : au­pa­ra­vant, ils tentaient tous les mots de passe du dic­tion­naire. Selon la com­plexité des mots de passe (longueur et type de ca­rac­tères utilisés), cela peut toutefois coûter du temps et de la capacité de calcul.

Les Rainbow Tables vont plus loin que les dic­tion­naires 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, con­tien­nent des mots de passe et leurs valeurs de hachage con­for­mé­ment à l’al­go­rithme de cryptage utilisé. Mais pas com­plè­te­ment : au lieu de cela, certaines chaînes sont créés à partir des­quelles les valeurs réelles peuvent être fa­ci­le­ment 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 com­prendre le fonc­tion­ne­ment des tables arc-en-ciel, il faut au moins con­si­dé­rer le fonc­tion­ne­ment de base des al­go­rithmes de cryptage. Il sera alors plus facile de com­prendre les avantages des tables pré­fa­bri­quées et donc aussi le compromis temps-mémoire.

Depuis que les fonctions de hachage cryp­to­gra­phiques ont été utilisées dans le cryptage, les al­go­rithmes cor­res­pon­dants ont changé à maintes reprises. Des normes qui étaient con­si­dé­rées comme in­vio­lables il y a seulement 10 ans, sont aujourd’hui con­si­dé­rées comme des vio­la­tions courantes de la sécurité. Ce qu’ils ont tous en commun, cependant, c’est que le contenu à chiffrer passe par des al­go­rithmes et qu’une valeur de hachage est générée à la fin. Cette valeur de hachage est gé­né­ra­le­ment un nombre hexa­dé­ci­mal d’une certaine longueur. Quelle que soit la longueur du contenu original, au final la valeur de hachage est toujours de 128 bits. Trois pro­prié­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 fonc­tion­ner 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 iden­tiques.
2. Une valeur de hachage doit toujours être unique : des entrées dif­fé­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 col­li­sions ne peuvent pas être exclues. Les fonctions de hachage modernes et les hachages d’une longueur suf­fi­sante mi­ni­mi­sent le risque du mieux que possible.
3. Les valeurs de hachage ne peuvent pas être re­cal­cu­lé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 al­go­rithme ne doit pas fonc­tion­ner trop vite, car cela fa­ci­li­te­rait aussi le travail des hackers. Mais la con­ver­sion 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 vo­lu­mi­neux. Rainbow Tables utilise donc une fonction de réduction pour éviter l’en­com­bre­ment de l’espace de stockage né­ces­saire : ces fonctions con­ver­tis­sent 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 ap­pa­rais­sent. Sur la base de ces in­for­ma­tions et en tenant compte des fonctions de réduction utilisées, toutes les autres valeurs peuvent aussi être dé­ter­mi­né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 in­ter­mé­diaire étant comparé aux valeurs du tableau.

Le défi dans le processus de création du tableau est que le contenu source qui re­pré­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 tech­no­lo­gie, la taille de ces tables peut être ex­trê­me­ment 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 uti­li­sa­tion 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 cryp­to­gra­phiques sont effectués de nouveau à chaque attaque. Une table, d’autre part, dans laquelle des milliards de mots de passe sont re­pré­sen­tés avec leurs valeurs de hachage, occupe une énorme quantité d’espace de stockage, mais peut les décrypter très ra­pi­de­ment. 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’éco­no­mi­ser 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 re­cher­chez 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é re­la­ti­ve­ment ra­pi­de­ment, car vous n’avez plus qu’à tracer les ré­pé­ti­tions 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 re­cher­chez. Cependant, la chaîne cor­res­pon­dante contenant la valeur de hachage a été trouvée. Par con­sé­quent, on commence main­te­nant au point de départ de la chaîne et on effectue les ré­duc­tions et le hachage al­ter­na­ti­ve­ment jusqu’à obtenir la valeur de hachage re­cher­ché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 dif­fé­rente à chaque fois. Cela assure un meilleur résultat dans la réduction et évite la ré­pé­ti­tion des valeurs de hachage dans le tableau, mais présente l’in­con­vé­nient que la recherche de com­bi­nai­sons de valeurs de hachage et de mots de passe dans les chaines est un peu plus complexe.

Par con­sé­quent, les ré­duc­tions doivent être ef­fec­tuées dans l’ordre : si l’on suppose que la chaîne avec les ré­duc­tions R1, R2, R3 a été cons­truite, on com­men­ce­rait 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 dif­fé­rentes fonctions de réduction peuvent être marquées avec des couleurs, ce qui peut conduire à un arc-en-ciel coloré avec un nombre cor­res­pon­dant d’ité­ra­tions, d’où le nom.

Ex­pli­ca­tion : le mot de passe saisi est k. Ainsi, m re­pré­sente n’importe quel mul­ti­pli­ca­teur (2000 dans cet exemple). Pour A, on utilise gé­né­ra­le­ment le nombre d’or (0,618). Modulo (mod) extrait le reste d’une division effectuée dans cette fonction par 1. Les pa­ren­thèses gaus­siennes ar­ron­dis­sent le résultat à un entier à la fin, si né­ces­saire. 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 com­men­çons avec un 0 : 0408.

Dans une table arc-en-ciel pour cette fonction de hachage, les fonctions de réduction doivent main­te­nant fonc­tion­ner. 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é­ti­tions peut être définie librement. Plus vous répétez, moins la Rainbow table a besoin de mémoire, mais le temps de trai­te­ment 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 rac­cour­cir la cir­con­fé­rence. Par con­sé­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.

Main­te­nant, toutes les valeurs de hachage ne sont pas dis­po­nibles dans le tableau. Par exemple, si vous saviez qu’il y avait un mot de passe derrière la valeur de hachage 1888, vous cher­che­riez main­te­nant la table arc-en-ciel et trou­ve­riez que la valeur n’apparait pas dans la table, mais est cachée dans une chaîne. Par con­sé­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 cor­res­pon­dante 0048 se trouve à la troisième ligne. Mais le mot de passe dans la même ligne (03) n’ap­par­tient pas di­rec­te­ment à 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 re­cher­chée. Le mot de passe 08 ap­par­tient à cette valeur.

Quiconque a compris comment les hackers peuvent pénétrer dans les comptes d’uti­li­sa­teur à l’aide d’une table arc-en-ciel doit être conscient que des mé­ca­nismes de défense ap­pro­priés doivent être utilisés. Tant les uti­li­sa­teurs que les res­pon­sables du site Web peuvent prendre des mesures pour prévenir ou au moins pour gêner de telles attaques.

Pour les uti­li­sa­teurs, il s’applique en général : les mots de passe doivent être aussi longs que possible et contenir des lettres ma­jus­cules, des lettres mi­nus­cules, des chiffres et d’autres ca­rac­tères, cela aide contre les attaques par force brute et les tables arc-en-ciel, puisque le dé­cryp­tage devient trop complexe. La taille de la table requise augmente ex­po­nen­tiel­le­ment avec la longueur du mot de passe. Il est aussi conseillé de ne pas utiliser de mots réels, mais des chaînes de ca­rac­tères aléa­toires pour éviter les attaques basées sur des dic­tion­naires. Ainsi, les ges­tion­naires 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é­chif­frer des mots de passe et à accéder à des données per­son­nelles, il est facile d’essayer tous les autres comptes sur Internet avec exac­te­ment ce même mot de passe.

Mais les opé­ra­teurs de serveurs peuvent aussi faire beaucoup pour protéger leurs uti­li­sa­teurs. 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 nom­breuses ef­frac­tions sur les serveurs des grandes en­tre­prises. Par con­sé­quent, vous devez en­re­gis­trer la valeur de hachage. Cela commence par le fait qu’aucun al­go­rithme obsolète n’est utilisé.

Le MD5 et le SHA-1 ont longtemps été con­si­dé­rés comme dangereux et les tables arc-en-ciel cor­res­pon­dantes sont faciles à trouver sur Internet. Avec ces derniers, les mots de passe qui ont été hachés comme ceci peuvent être dé­cou­verts en quelques secondes. Il est donc essentiel d’être cons­tam­ment informé sur l’existence de nouveaux al­go­rithmes 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 con­si­dé­rées comme sûres, mais SHA-3 est main­te­nant aussi dis­po­nible, 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 uti­li­sa­teur 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 dif­fé­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 cir­cons­tance est dé­rou­tante : les at­ta­quants qui reçoivent le contenu de base de données ont donc le nom d’uti­li­sa­teur, la valeur de hachage et le Salt cor­res­pon­dant. En fait, attaques par force brute et par dic­tion­naires ne sont pas évitées, mais la mesure sup­plé­men­taire aide surtout contre les Rainbow Tables. Une telle table est créée à l’avance, basée sur un al­go­rithme de hachage et in­dé­pen­dante 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 con­nais­sait pas encore le Salt.

Un autre avantage du grain de sable, est que les uti­li­sa­teurs n’ont pas à s’en souvenir. Ils peuvent donc être com­plè­te­ment chao­tiques et, surtout, très longs. Cela rend les valeurs de hachage elles-mêmes si complexes qu’il est plus difficile de tra­vail­ler 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 uti­li­sa­teurs utilisent le même mot de passe pour dif­fé­rents services. La valeur de hachage stockée est dif­fé­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 dic­tion­naires. Le Pepper est aussi une chaîne aléatoire qui, au mieux en com­bi­nai­son avec le Salt, s’écoule dans la valeur de hachage en même temps que le mot de passe. Con­trai­re­ment au Salt, le Pepper n’est pas stocké avec d’autres données de connexion dans une base de données, mais sé­pa­ré­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 pla­te­forme. Par con­sé­quent, Pepper n’aide pas contre le fait que plusieurs uti­li­sa­teurs ont le même mot de passe, parce qu’ils utilisent aussi le même Pepper, ce qui conduit à des valeurs de hachage iden­tiques. Par con­sé­quent, les ad­mi­nis­tra­teurs devraient choisir une com­bi­nai­son de Salt et Pepper.