Rainbow table

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^[1] pour retrouver un mot de passe à partir de son empreinte. Il s'agit d'une amélioration des compromis temps-mémoire proposés par Martin Hellman dans les années 1980.

Aperçu

La table, qui ne dépend que de la fonction de hachage considérée, est constituée d'une grande quantité de paires de mots de passe. Pour obtenir chacune de ces paires, on part d'un mot de passe, et on calcule son empreinte. Une « fonction de réduction » qui varie selon la position dans la table permet de recréer un nouveau mot de passe à partir de cette empreinte. On itère ce processus, et après un nombre fixe d'itérations, on obtient un mot de passe qui forme le deuxième élément de la paire. La table, créée une fois pour toutes, permet la recherche d'un mot de passe, connaissant son empreinte par la fonction de hachage considérée.

L'algorithme développé par Oechslin optimise la détection des collisions et le parcours dans la table. Des solutions pour réduire la taille de la table ont également été proposées. Plusieurs tables peuvent être produites pour améliorer les chances de réussite.

L'algorithme, déjà efficace avec des mots de passe correctement hachés (le mot de passe Windows "Fgpyyih804423" est retrouvé en 160 secondes^[2]) l'est a fortiori avec les mots de passe de LAN Manager, qui utilisent LM hash (et donc un niveau de sécurité très faible). Ces derniers sont ainsi trouvés en l'espace de quelques secondes s'ils sont alphanumériques. Les tables peuvent être utilisées avec toute autre fonction de hachage comme MD5 ou encore SHA-1, ces dernières étant nettement plus robustes du point de vue cryptographique que LAN Manager et nécessitent des tables plus grandes.

Rappels concernant la problématique

Une des principales menaces concernant l'usage de mots de passe est la compromission des bases contenant les mots de passe utilisateur. Un attaquant profite d'une brèche quelconque pour récupérer la table de mots de passe d'un système. Il pourrait être raisonnable de penser qu'un attaquant capable de compromettre la table de mots de passe d'un système dispose déjà d'un accès suffisant à celui-ci pour que cette dernière ne présente qu'un intérêt limité pour lui. Les études comportementales montrent que la réutilisation par les utilisateurs du même mot de passe pour différents sites ou systèmes est endémique^[3], c'est pourquoi un attaquant qui compromet les mots de passe d'un système donné est souvent en mesure d'en déduire les mots de passe pour d'autres sites.

Pour lutter contre ce phénomène, les normes de sécurité modernes proscrivent la conservation des mots de passe en texte brut par les systèmes gestionnaires d'authentification, au contraire elles incitent à ce que ne soient conservés que des versions hachées des mots de passe.

Les fonctions de hachage cryptographiques employées à cet effet sont spécifiquement conçues pour être mathématiquement difficiles à inverser, c'est pourquoi l'attaquant en est souvent réduit à employer des méthodes d'attaque par force brute.

Là encore les fonctions de hachage sont optimisées pour augmenter le temps de chaque tentative de comparaison.

Une des méthodes principales retenues pour diminuer le temps de réalisation de ce type d'attaques repose sur l'utilisation de compromis temps-mémoire. La table arc-en-ciel (en anglais : rainbow table) est une forme sophistiquée de ce type d'attaque.

Les attaques par compromis temps-mémoire

Table de hachage

Article détaillé : Table de hachage.

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

Compromis temps-mémoire d'Hellman

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

Rainbow table

Création de la table

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.

Une rainbow table avec trois fonctions de réduction

Plus formellement, le calcul d'une chaîne se fait comme suit à partir d'un mot de passe initial P et de fonctions de réduction (différentes à chaque itération pour limiter les collisions) :

$P\to H(P)\to R_{1}(H(P))\to H(R_{1}(H(P)))\to R_{2}(H(R_{1}(H(P))))\to H(R_{2}(H(R_{1}(H(P))))\to \cdot \cdot \cdot$

Recherche du mot de passe

On considère une empreinte H engendrée à partir d'un mot de passe P. La première étape consiste à prendre H, lui appliquer la dernière fonction de réduction utilisée dans la table, et regarder si ce mot de passe apparaît dans la dernière colonne de la table. Si cette occurrence n'est pas trouvée alors on peut déduire que l'empreinte ne se trouvait pas à la fin de la chaîne considérée. Il faut revenir un cran en arrière. On reprend H, on lui applique l'avant-dernière fonction de réduction, on obtient un nouveau mot de passe. On hache ce mot de passe, on applique la dernière fonction de réduction et on regarde si le mot de passe apparaît dans la table.

Cette procédure itérative continue jusqu'à ce que le mot de passe calculé en fin de chaîne apparaisse dans la table (si rien n'est trouvé, l'attaque échoue). Une fois le mot de passe découvert dans la dernière colonne, on récupère le mot de passe qui se trouve dans la première colonne de la même ligne. On calcule à nouveau la chaîne tout en comparant à chaque itération l'empreinte obtenue à partir du mot de passe courant avec l'empreinte H du mot de passe inconnu P. S'il y a égalité, alors le mot de passe courant correspond à celui recherché et l'attaque a réussi ; plus précisément, on a trouvé un mot de passe dont l'empreinte est la même que celle de P, ce qui est suffisant.

Exemple

À partir d'une empreinte ("re3xes"), on calcule la dernière réduction utilisée dans la table et on regarde si le mot de passe apparaît dans la dernière colonne de la table (étape 1)
Si le test échoue ("rambo" n'apparaît pas dans la table), on passe au point 2 où l'on calcule une chaîne avec les deux dernières réductions.
Si ce test échoue à nouveau, on recommence avec 3 réductions, 4 réductions, etc. jusqu'à trouver une occurrence du mot de passe dans la table. Si aucune chaîne ne correspond alors l'attaque échoue.
Si le test réussit (étape 3, ici "linux23" apparaît en fin de chaîne et également dans la table), on récupère le mot de passe à l'origine de la chaîne qui a abouti à "linux23". Il s'agit ici de "passwd".
On génère la chaîne (étape 4) et on compare à chaque itération l'empreinte avec l'empreinte recherchée. Le test est concluant, on trouve ici l'empreinte "re3xes" dans la chaîne. Le mot de passe courant ("culture") est celui qui a engendré la chaîne : l'attaque a réussi.

Contre-mesures

Article détaillé : Salage (cryptographie).

L'efficacité des tables diminue de façon significative lorsque les fonctions de hachage sont combinées à un sel. Dans le cadre d'un système de mots de passe, le sel est une composante aléatoire ou un compteur qui change en fonction de l'utilisateur. Si deux utilisateurs ont le même mot de passe, le sel permet d'éviter que les empreintes soient identiques. De manière informelle, le sel consiste en une opération du type :

empreinte = h(mot_de_passe   sel)

où l'opération peut être une concaténation ou une opération plus complexe.

Cette mesure augmente la complexité de l'attaque : il faut non seulement inverser la fonction grâce aux tables, mais il faut encore explorer l'ensemble des possibilités induites par la présence du sel. Si l'attaque réussit, il faut encore retirer le sel du mot de passe.

En pratique, certaines applications n'utilisent pas de sel et sont vulnérables. En outre, le sel doit avoir une longueur suffisante pour augmenter sensiblement la complexité. Un sel trop court (par exemple 4 bits) ne multiplierait la complexité que d'un facteur de 16. Dans le système GNU/Linux, la fonction de hachage utilisée est du MD5 avec un sel de 8 caractères en ASCII ce qui rend l'attaque impossible en pratique.

Notes et références

↑ (en) Philippe Oechslin, « Making a Faster Cryptanalytic Time-Memory Trade-Off », dans Advances in Cryptology - CRYPTO 2003: 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 2003. Proceedings, Springer, coll. « Lecture Notes in Computer Science », vol. 2729, 2003 (ISBN 978-3-540-40674-7 et 978-3-540-45146-4), p. 617-630 DOI 10.1007/978-3-540-45146-4_36. texte intégral en ligne
↑ (en) Jeff Atwood, « Rainbow Hash Cracking », Coding Horror, 8 septembre 2007
↑ John Fontana, Password's rotten core not complexity but reuse, Zdnet.com, 22 mars 2013, consulté le 24 octobre 2013

Voir aussi

Sur les autres projets Wikimedia :

table arc-en-ciel, sur le Wiktionnaire

Articles connexes

Liens externes

(en) Philippe Oechslin (LASEC/EPFL)
(en) Attacking NTLM with Precomputed Hashtables
(en) Site du projet TMRL DRTG. Projet de calcul réparti utilisant BOINC afin de créer des rainbow tables.
(en) Site du projet Free Rainbow Tables. Autre projet de calcul réparti.
(en) Rainbow Tables Download

[1] (en) Philippe Oechslin, « Making a Faster Cryptanalytic Time-Memory Trade-Off », dans Advances in Cryptology - CRYPTO 2003: 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 2003. Proceedings, Springer, coll. « Lecture Notes in Computer Science », vol. 2729, 2003 (ISBN 978-3-540-40674-7 et 978-3-540-45146-4), p. 617-630 DOI 10.1007/978-3-540-45146-4_36. texte intégral en ligne

[2] (en) Jeff Atwood, « Rainbow Hash Cracking », Coding Horror, 8 septembre 2007

[3] John Fontana, Password's rotten core not complexity but reuse, Zdnet.com, 22 mars 2013, consulté le 24 octobre 2013

[1]

[2]

[3]