Voir la source de Rainbow table

{{langue du titre|en}}
{{Voir homonymes|Arc-en-ciel (homonymie)|Rainbow}}

Une '''''{{lang|en|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'[[École polytechnique fédérale de Lausanne|EPFL]]<ref>{{en}} Philippe Oechslin, « {{lang|en|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|978-3-540-45146-4}}, {{p.}}617-630 {{doi|10.1007/978-3-540-45146-4_36}}. [http://lasecwww.epfl.ch/php_code/publications/search.php?ref=oech03  texte intégral en ligne]</ref> pour retrouver un mot de passe à partir de son [[fonction de hachage|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 [[mot de passe|mots de passe]]. Pour obtenir chacune de ces paires, on part d'un mot de passe, et on calcule son empreinte. Une « [[fonction (mathématiques)|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 [[Collision (informatique)|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 [[Microsoft Windows|Windows]] "Fgpyyih804423" est retrouvé en 160 secondes<ref>{{en}} Jeff Atwood, « [http://www.codinghorror.com/blog/archives/000949.html {{lang|en|Rainbow Hash Cracking}}] », ''Coding Horror'', 8 septembre 2007</ref>) 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<ref>John Fontana, [http://www.zdnet.com/passwords-rotten-core-not-complexity-but-reuse-7000013019/ Password's rotten core not complexity but reuse], Zdnet.com, 22 mars 2013, consulté le 24 octobre 2013</ref>, 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 [[fonctions de hachage|hachées]] des mots de passe.

Les [[fonction de hachage|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 [[fonction de hachage|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}}
{{Section vide ou incomplète}}

===Compromis temps-mémoire d'Hellman===
{{Section vide ou incomplète}}

===Rainbow table ===

==== Création de la table ====
La ''{{lang|en|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.

[[Image:simple_rainbow_table.svg|thumb|center|700px|Une ''{{lang|en|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) :

<math>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 </math>

==== 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 =====

[[Image:simple_rainbow_search.svg|550px|left]]
* À 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.
{{clr}}

== 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 [[Salage (cryptographie)|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 ==
{{Références}}

== Voir aussi ==
{{Autres projets
| wiktionary = table arc-en-ciel
| wiktionary titre = table arc-en-ciel
}}

=== Articles connexes ===

* [[Algorithme rho de Pollard]]
* [[RainbowCrack]]
* [[Ophcrack]]
* [[Cassage de mot de passe]]

=== Liens externes ===

* {{en}} [http://lasecwww.epfl.ch/~oechslin/ Philippe Oechslin (LASEC/EPFL)]
* {{en}} [http://www.uninformed.org/?v=3&a=2&t=pdf ''Attacking NTLM with Precomputed Hashtables'']
* {{en}} [http://www.hashbreaker.com:8700/tmrldrtg/ Site du projet TMRL DRTG]. Projet de [[calcul réparti]] utilisant [[Berkeley Open Infrastructure for Network Computing|BOINC]] afin de créer des ''{{lang|en|rainbow tables}}''.
* {{en}} [http://www.freerainbowtables.com/ Site du projet Free Rainbow Tables]. Autre projet de [[calcul réparti]].
* {{en}} [http://tbhost.eu/rt.php Rainbow Tables Download]

{{Portail|sécurité informatique|cryptologie}}

[[Catégorie:Cryptanalyse]]