Table arc-en-ciel

Un article de Wikipédia, l'encyclopédie libre.

Vous avez de nouveaux messages (diff^?).

En cryptologie, une table arc-en-ciel (plus communément appelé Rainbow Table) est une structure de données inventée en 2003 par Philippe Oechslin 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.

Sommaire

1 Aperçu
2 Description détaillée
- 2.1 Création de la table
- 2.2 Recherche du mot de passe
  - 2.2.1 Exemple
3 Contre-mesures
4 Voir aussi
5 Liens externes

[modifier] Aperçu

Plusieurs tables peuvent être produites pour améliorer les chances de réussite. Les tables contiennent une grande quantité de chaînes qui proposent en alternance un mot de passe suivi de son empreinte. Une fonction de réduction qui varie selon la position dans la table permet de recréer un autre mot de passe à partir de l'empreinte et ainsi de suite. 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.

L'algorithme est très efficace avec les mots de passe de LAN Manager implémenté dans Microsoft Windows. Les mots de passe de LM peuvent ainsi être trouvés en l'espace de quelques secondes s'ils sont alphanumériques. Les tables peuvent être utilisées pour d'autres fonctions de hachage comme MD5 ou encore SHA-1, ces dernières sont toutefois nettement plus robustes du point de vue cryptographique que LAN Manager et nécessitent des tables plus grandes. La sécurité calculatoire du système de Microsoft a toujours été faible mais il a été remplacé par les NT-hash dans Windows NT et les versions ultérieures de Windows.

[modifier] Description détaillée

[modifier] Création de la table

La table arc-en-ciel est constituée de paires de mots de passe (ie. 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 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ée 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.

Table arc-en-ciel 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$

[modifier] 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 à 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 se 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 celle recherchée. Si le test est affirmatif, alors le mot de passe courant correspond à celui recherché et l'attaque a réussi.

[modifier] 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 aboutit à "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.

[modifier] Contre-mesures

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 (soit 48 bits) ce qui rend l'attaque impossible en pratique.