Rainbow tables
Dans ce TD, nous allons nous "attaquer" à MD5, une fonction de hachage, en nous limitant à des mots de passe court (4 caractères) pour des raisons pratiques.
Attaque par force brute
Ouvrez tout d'abord le fichier bruteforce.py et implémentez la fonction generate_passwords.
Testez le code en fournissant un hash de
Lancez plot_bruteforce.py, sans surprise, vous devriez voir que le temps nécessaire pour
générer tous les mots de passe augmente exponentiellement avec la taille du mot de passe.
L'espace de stockage nécessaire augmente lui aussi exponentiellement.
Attaque par table arc-en-ciel
Dans une attaque par force brute, il est nécessaire d'effectuer de nombreuses opérations de hachage. Les mots de passes peuvent être pré-calculés, ce qui permet de réduire le temps nécessaire pour retrouver un mot de passe, mais au prix d'un espace de stockage plus important.
Les tables arc-en-ciel sont une technique qui permet de réduire l'espace de stockage nécessaire lors du pré-calcul, au coût d'un temps de calcul plus important.
L'idée est de créer des séquences du type:
Où aaaaaa est un mot de passe, puis 281DAF40 un hash, puis sgfnyd un nouveau mot de passe obtenu
à partir du hash précédent à l'aide d'une fonction de réduction, et ainsi de suite.
Dans la pratique, plusieurs fonctions de réduction sont utilisées à chaque étape (\(R_1\), \(R_2\) ...)
Lors de la recherche, on appliquera la dernière fonction de réduction sur le hash recherché, si celui-ci est dans la chaîne, on pourra remonter jusqu'au mot de passe initial. Sinon, on appliquera l'avant dernière, puis la dernière fonction de réduction, etc.
Regardez le fichier utils.py, notamment la fonction reduction: comment fonctionne t-elle ?
Ouvrez le fichier rainbow.py et implémentez les fonctions create_table et search_password.
En supposant que les pré-calculs aient déjà été réalisés, quel