Tables arc-en-ciel: TD

Installation

Pour commencer, téléchargez l'archive suivante:

Vous aurez besoin de la librairie tqdm pour afficher la progression de vos calculs:

pip install tqdm

Introduction

Dans ce TD, nous allons implémenter des tables arc-en-ciel (pédagogiques). Nous nous intéresserons à la fonction de hachage MD5. Pour simplifier, nous ne considérerons que des mots de passe de taille 5, avec le jeu de 32 caractères suivant: abcdefghijklmnopqrstuvwxyz123456.

Dans tools.py, vous trouverez les fonctions suivantes:

generate_password: génère un mot de passe aléatoire,
md5_hash(password): calcule l'empreinte MD5 d'une chaîne,
reduce(hash, level): applique une fonction de réduction à une empreinte,
all_passwords(): retourne un itérateur sur tous les mots de passe possibles.

Première solution naïve: la force brute

Lisez et testez le code de bruteforce.py. Il s'agit d'une solution naïve pour retrouver un mot de passe à partir de son empreinte MD5.

Le code ne s'arrêtant pas lorsque le mot de passe a été trouvé, constatez le temps d'exécution pour trouver un mot de passe.

Deuxième solution naïve: tout pré-calculer

Lisez le code de store_all.py. Il s'agit d'une solution naïve pour pré-calculer toutes les empreintes possibles.

Si vous avez de l'espace disque, vous pouvez tester et constater la taille du fichier all_passwords.pkl ainsi généré: 1.4 Go!

Le fichier all_passwords.pkl n'est absolument pas optimisé en terme de stockage. Pensez à supprimer ce fichier après cette partie, il n'est pas nécessaire pour la suite.

Tables arc-en-ciel

Créez maintenant un fichier rainbow.py, c'est dans ce fichier que vous implémenterez les tables arc-en-ciel.

Nous utiliserons les paramètres suivants:

# Taille des chaînes arc-en-ciel
chains_length = 256
# Taille de la table arc-en-ciel
rainbow_table_size = 200_000

Écrivez le code de la fonction compute_chain(), qui calcule une chaîne arc-en-ciel, en partant d'un mot de passe aléatoire.

def compute_chain() -> tuple:
    """
    Calcule une chaîne arc-en-ciel

    Retourne un tuple (password, hash), où:
    - password est le premier mot de passe de la chaîne,
    - hash est le dernier hash
    """

Écrivez le code de la fonction compute_rainbow_table(), qui calcule une table arc-en-ciel:

def compute_rainbow_table():
    """
    Calcule une table arc-en-ciel, et la stocke dans un
    fichier rainbow_table.pkl
    """

Vous stockerez les chaînes arc-en-ciel dans un dictionnaire, où chaque clé est le hash du dernier mot de passe, et chaque valeur est une liste de mots de passe initiaux possibles.

Écrivez à présent le code de la fonction load_rainbow_table(), qui charge une table arc-en-ciel depuis un fichier:

def load_rainbow_table() -> dict:
    """
    Charge une table arc-en-ciel depuis un fichier
    """

Constatez la taille du fichier rainbow_table.pkl ainsi généré.

Enfin, écrivez le code de la fonction crack_password(), qui retrouve un mot de passe à partir de son empreinte, et de la table arc-en-ciel:

def crack_password(target_hash: str, rainbow_table: dict) -> None:
    """
    Retrouve un mot de passe à partir de son empreinte
    """

Quel est le temps d'exécution pour retrouver un mot de passe à partir de son empreinte, avec la table arc-en-ciel ?