Les Rainbow Tables (tables arc-en-ciel en français) sont des outils indispensables dans la trousse de l’auditeur en sécurité. Ce terme est utilisé depuis des années pourtant peu de personnes sont aujourd’hui capables d’expliquer à quoi elles correspondent.
L’objectif de cet article en deux parties est de démystifier le concept de tables arc-en-ciel, expliquer à quelle problématique elles répondent et comment elles fonctionnent.
1) Le besoin
En fait, cela fait bien longtemps que les mots de passe stockés notamment en base ne sont plus en clair … et oui malheureusement si l’on arrive à dumper le contenu d’une base de données contenant des logins et des mots de passe associés, ces derniers seront généralement stockés sous forme de HASH, par exemple MD5 ou SHA-1.
Du coup, le cassage de mots de passe par dictionnaire ou brute-force classique ne fonctionnent plus …
Si on prend l’exemple d’un Linux récent qui stocke ces mots de passe dans le fichier /etc/passwd, la représentation du mot de passe est en fait en 3 parties :
- Le premier caractère $6 correspond en fait à l’algorithme SHA-512. $1 correspond par exemple à un autre algorithme de hash, à savoir MD5.
- La seconde partie intéressante est entre deux nouveaux $, il s’agit de ce que l’on appelle un « sel », nombre généré pseudo-aléatoirement et public. Nous verrons un peu plus loin son intérêt
- Enfin, la dernière partie correspond au mot de passe hashé avec l’algorithme SHA-512 et « salé ». Grossièrement, le calcul de ce mot de passe est donc : Hash(SEL+Mot de passe en clair)
2) L’histoire
Pour la petite histoire, c’est Philippe Oechslin qui a proposé concept en 2003. Depuis, cette technique a été largement revisitée afin par exemple d’être adaptée au calcul sur GPU (ou processeur de carte graphique) avec la mise en oeuvre de clusters de consoles de jeux Playstation3 en 2007.
3) Le fonctionnement
En fait, l’idée est de générer un ensemble des structures de données qui vous nous permettre de stocker des milliers d’associations de type mot de passe en clair/ mot de passe hashé. Ces structures, ou chaînes, ont une taille fixe de 128 bits en mémoire.
La réalisation d’une rainbow table se fait en deux étapes :
- Tout d’abord, on calcule les hashs relatifs à des mots de passe en clair. Ceci signifie qu’une Rainbow Table n’est valide que pour un algorithme donné. Ce calcul peut par exemple être effectué sur un serveur puissant pendant plusieurs heures/jours/mois.
- Quand on en a besoin, on utilise la Rainbow Table ainsi générée, possiblement sur un autre ordinateur (moins puissant ou non) afin de « casser » un mot de passe hashé récupéré par exemple dans un /etc/shadow suite à un pentest.
Attention, car le « sel » dont nous parlions un peu plus haut à la faculté de rendre notre opération trèèèès complexe : en effet, il rajoute de l’entropie au processus car du coup, nous serons obligé de générer une rainbow table sur la base de ce sel. Concrètement, cela correspond à une solution très riche, rarement mise en pratique.
Du coup, les tables arc-en-ciel sont très utilisées pour casser des mots de passe hashés qui ne sont en fait pas salés ou salés avec des constantes (et les constantes en cryptographie, c’est mal) comme par exemple certaines versions du SGBD Oracle qui utilisent le login utilisateur (par ex. SYS).
Ces méthodes sont par exemple les hashs LANMAN (LM) et NT sous Windows.
Pour information au lecteur, le hash LM est en fait un mot de passe qui est automatiquement converti en majuscules (ex: password devient PASSWORD) puis divisé en deux parties de 7 caractères : cela signifie qu’il ne sert à rien d’utiliser des mots de passe plus long que 14 caractères, et qu’au cas où il serait < 14 alors il sera « paddé » avec des bits nuls. Ainsi, la première partie de password devient PASSWOR et la deuxième partie D+PADDING.
Chaque portion du mot de passe est donc utilisée comme clé DES pour chiffrer une constante (encore une …) bien connue KGS!@#$% .
Le mot de passe ainsi stocké dans la ruche SAM est la concaténation des deux parties.
Pour le hash NT (à ne pas confrondre avec les protocoles NTLMv1 et v2 qui sont des protocoles d’authentification réseau), il s’agit du même concept mais en utilisant l’algorithme MD4 et sachant que le mot de passe peut aller jusqu’à 256 caractères.
Bon, c’est très bien tout ça mais pour en revenir à nos tables Rainbow Tables, j’ai oublié de préciser une petite chose ….
Il serait très réducteur d’expliquer ces Rainbow Tables en indiquant qu’il suffit de passer un dictionnaire dans un algorithme type MD5 et ensuite de lancer une recherche exhaustive en comparant les mots de passe hashés à casser à notre table.
Sauf que pour un mot de passe par exemple de 7 octets en alphanumérique (ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789) ce qui correspond à 36 possibilités par caractères, hashés en 8 octets, il nous faudra stocker 112 Teraoctets … et encore sans les métadonnées … très clairement ceci est complètement inenvisageable et par conséquent une meilleure solution devrait exister …. c’est ce que nous verrons dans la deuxième partie de cet article 😉
A bientôt !
