1/12

Tables arc-en-ciel

2/12

Introduction

Présentation

Les fonctions de hachage (comme par exemple MD5) permettent de calculer des empreintes:

hash = md5_hash("hello")
# 5d41402abc4b2a76b9719d911017c592

Comment inverser une fonction de hachage ?

3/12

Première solution naïve: la force brute

On pourrait tester toutes les combinaisons possibles:

for password in all_passwords():
    if hash == md5_hash(password):
        print(f"Password cracked: {password}")

Cette solution prendrait énormément de temps pour chaque mot de passe à trouver.

4/12

Seconde solution naïve: tout pré-calculer

Il serait possible de pré-calculer les empreintes possible, et de les stocker dans une base de données:

Si on se permettait de faire ça, ne serait-ce qu'une fois, on pourrait retrouver un mot de passe en un seul accès à la base!

Cette solution prendrait énormément de place en mémoire.

5/12

Tables arc-en-ciel

Intuition

Et si il était possible de trouver un juste milieu entre ces deux solutions ? C'est à dire:

  • Un pré-calcul des empreintes, sans stocker toutes les combinaisons possibles pour autant
  • En contrepartie, accepter de faire un peu de calcul pour chaque mot de passe à trouver

C'est précisément ce que font les tables arc-en-ciel, ou rainbow tables.

6/12

Fonction de réduction

Pour bien comprendre le fonctionnement des tables arc-en-ciel, il faut d'abord comprendre le concept de fonction de réduction. Une fonction de réduction est une fonction qui prend une empreinte en entrée, et qui renvoie un mot de passe en sortie.

Supposons donc que l'on calcule l'empreinte de hello avec MD5, et que l'on applique une fonction de réduction à cette empreinte. On obtiendrait un autre mot de passe, par exemple paswd. On peut à nouveau calculer l'empreinte de paswd.

Dans la base de données, on stockera le mot de passe initial (hello) et l'empreinte finale (md5("paswd")):

7/12

Recherche (1/2)

Supposons maintenant que l'on utilise la base pour trouver le mot de passe ayant l'empreinte 75e5c3e0. Cette empreinte étant dans la base, on peut retrouver le mot de passe initial (hello), et donc reconstruire la chaîne, jusqu'à retrouver le mot de passe paswd:

8/12

Recherche (2/2)

Si on cherche le mot de passe de l'empreinte 5d41402a, on constatera qu'il n'est pas présent dans la base. Il est possible que ce mot de passe ait été parcouru à un moment donné, mais qu'il n'ait pas été stocké. On peut alors appliquer la fonction de réduction à l'empreinte, pour obtenir paswd, puis la fonction de hachage, pour obtenir 75e5c3e0.

75e5c3e0 étant présent dans la base, on obtient le mot de passe initial (hello):

9/12

Des chaînes plus longues

Dans la pratique, on utiliserait des chaînes aussi longues qu'on le souhaite:

Lors d'une recherche, on testera chaque niveau de la chaîne, jusqu'à retrouver l'empreinte recherchée.

La taille des chaînes est un paramètre de l'algorithme. Plus les chaînes sont longues, plus la base de données est petite, mais plus les calculs sont longs.

10/12

Notes:

  • Les fonction de réduction utilisées à chaque étape sont, dans la pratique, différentes. Cela permet de limiter les cycles dans les chaînes.
  • On ne peut pas être sûrs que tous les mots de passes sont présents dans l'ensemble des chaînes générées.
11/12

La fonction de réduction elle-même pour être sujette à des collisions. À cause de cela, il est possible que plusieurs mots de passes initiaux aient la même empreinte finale.

Par exemple, si reduce2 associe admin à 75e5c3e0 et à 29a9d2e4, il est possible d'avoir les chaînes suivantes:

En cas de recherche, par exemple de 29a9d2e4, la première chaîne (en haut) ressortira de la base de données, mais ne permettra pas de retrouver le mot de passe initial.