Cugparck

Introduction

Cugparck est une application de crackage de mot de passe sur GPU qui utilise la technique des rainbow tables.
En 1980, Martin Hellman met au point la technique des compromis temps-mémoire [1]. Celle-ci est perfectionnée en 2003 par Philippe Oechslin pour donner naissance aux rainbow tables [2].

Habituellement, deux techniques sont utilisées pour cracker un hash de mot de passe :

• L'attaque par force-brute. Pour trouver un mot de passe correspondant à un hash, tous les mots de passe possibles sont hachés un par un jusqu'à ce que un hash calculé corresponde au hash recherché.
• L'attaque par dictionnaire. Dans une phase de pré-calcul, tous les mots de passe possibles sont hachés pour construire un dictionnaire qui associe chaque hash à un mot de passe. Pour trouver un mot de passe correspondant à un hash, on recherche dans le dictionnaire le hash correspondant.

Pour comprendre pourquoi les rainbow tables peuvent être appelées "compromis temps-mémoire" et en quoi elle sont intéressantes par rapport à une attaque classique, un tableau comparatif est présenté ci-dessous.

Technique	Temps	Mémoire
Force brute	$$N$$	$$1$$
Dictionnaire	$$1$$	$$N$$
Rainbow tables	$$\frac{N^2}{M^2}$$	$$M$$

Avec \(N\) le nombre de mots de passe possibles et \(M\) tel que \(M \leq N\) la mémoire utilisée.

Ainsi, les rainbow tables permettent de réaliser un compromis entre l'attaque par force brute et celle par dictionnaire. En effet, elles permettent de réduire le temps de calcul de l'attaque par force brute tout en réduisant la mémoire requise par l'attaque par dictionnaire (qui n'est pas praticable quand \(N\) est suffisamment grand à cause du stockage nécessaire).

Motivation

J'ai d'abord travaillé sur les rainbow tables dans le cadre d'un projet à l'INSA. Avec un groupe d'étudiants, nous devions étudier la faisabilité de la génération des rainbow tables sur GPU. Étant parti en semestre d'étude en Irlande, je n'ai pas eu la possibilité de terminer le projet avec mon groupe.

Ayant beaucoup apprécié le sujet et le côté orienté recherche, j'ai décidé de recommencer une implémentation en Rust. Notre implémentation originale en C/C++ disposait de problèmes très subtils et difficiles à débugguer intrinsèquement liés au langage. Il faut faire attention au débordement des nombres entiers, à la gestion de la mémoire et la différenciation des pointeurs du CPU et du GPU. En Rust, la grande majorité des ces problèmes sont mitigés, notamment grâce au système de types particulièrement expressif.

La méthode des rainbow tables est résumée très brièvement ici car elle ne pourrait pas être expliquée en quelques lignes. Pour plus d'information, je vous invite à vous référer à la page Wikipedia citée plus haut qui explique bien le principe de base.

Une attaque avec des rainbow tables se déroule en deux phases :

• La phase de pré-calculs. La structure de donnée appelée rainbow table est générée à ce moment-ci et stockée sur le disque. C'est cette phase qui est particulièrement longue. En général, 4 tables sont générées, pour avoir une probabilité de succès lors du crackage d'un mot de passe proche de 99,96%. Une rainbow table est composée d'une liste de chaînes de mots de passe. Seuls le premier et le dernier maillon de la chaîne sont stockés. En augmentant la longueur des chaînes, on diminue la mémoire utilisée (car moins de chaînes sont nécessaires) mais on augmente le temps pris pour cracker un mot de passe. Générer une table dite quasi-optimale correspond à un effort de \(160N\) calculs de hash.
• La phase d'attaque. Les rainbow tables sont utilisées pour cracker un ou plusieurs mots de passe. Le processus prend de quelques secondes à quelques minutes selon les paramètres des rainbow tables et le type de hash à cracker.

Cugparck utilise l'API de calcul CUDA pour envoyer au GPU des lots de mots de passe. Chaque mot de passe constitue le premier maillon d'une chaîne. Les chaînes sont ensuite générées parallèlement par chaque coeur du GPU à partir des premiers maillons, en utilisant des opérations de hachage successives. Le dernier maillon de chaque chaîne est ensuite renvoyé au CPU. Cette génération des chaînes est extrêmement efficace car elle peut entièrement bénéficier de l'architecture parallélisée du GPU. En effet, le calcul d'une chaîne sur un coeur est totalement indépendant des autres chaînes et par conséquent aucune synchronisation n'est requise.

Stealdows est un module de l'application qui permet de récupérer automatiquement les hashs des mots de passe des utilisateurs d'un système d'exploitation Windows monté sur un disque secondaire (même si celui-ci est verrouillé par le mode démarrage rapide). Ces hashs, au format NTLM, peuvent être automatiquement crackés par Cugparck en utilisant des rainbow tables préalablement générées.

En installant Cugparck sur une clé USB (qui tourne sous un Debian minimaliste par exemple) il est possible de récupérer les hashs des mots de passe des utilisateurs d'un ordinateur sous Windows en quelques secondes. Ces hashs peuvent être crackés en quelques minutes en laissant la clé sur l'ordinateur, ou alors sur un autre ordinateur ultérieurement.

D'autres projets utilisent déjà le GPU pour la génération de rainbow tables, mais à ma connaissance Cugparck est le projet open-source qui dispose du plus de fonctionnalités "à la pointe de la recherche", dont certaines datant de 2021. Par exemple Cugparck supporte le facteur de maximalité [3] qui permet de prédire à l'avance le nombre de chaînes nécessaires pour créer une rainbow table quasi-optimale. Il supporte aussi la filtration [3] qui permet de réduire le nombre d'opérations de hachage nécessaires en éliminant le plus tôt possible les chaînes redondantes. Enfin, les rainbow tables générées par Cugparck peuvent être compressées avec une compression delta et un codage de Rice comme décrit dans le papier [4], ce qui permet un stockage de 10% à 15% plus efficace que la technique de compression classique préfixe-suffixe.

De grands remerciements sont dûs à nos professeurs qui ont aidé notre groupe à comprendre ces papiers.

Il faut cependant noter que ces fonctionnalités ne rendent pas forcément Cugparck plus efficace que les autres implémentations, car une optimisation minutieuse des nouveaux paramètres introduits doit être réalisée pour observer des gains de performance. De plus, Cugparck ne supporte pas pour l'instant la génération et l'utilisation de rainbow tables trop grosses pour être entièrement stockées en RAM.

Contributions à l'Open Source

Pendant le développement de Cugparck j'ai pu faire quelques contributions à d'autres projets Open Source.

• rkyv, une bibliothèque de sérialisation sans copie.
  • Support de BitVec
  • Paramétrisation du hacheur de IndexMap
• nt-hive, une bibliothèque pour lire les registres Windows.
  • Ajout de la fonction class_name

Démonstration

La vidéo suivante montre le fonctionnement d'une phase d'attaque avec Cugparck, plus particulièrement avec le module Stealdows. Une clé USB est utilisée pour booter sur un système Linux minimaliste comme expliqué précédemment. Une fois le système lancé, un script Bash s'occupe de lancer Cugparck pour voler automatiquement les hashs d'un système Windows et les sauvegarder dans un fichier de la clé USB. Ensuite, Cugparck est lancé à nouveau pour cracker les hashs trouvés. Le résultat est à nouveau sauvegardé dans la clé USB.

Cugparck est ici capable de récupérer les mots de passe H4CkM3 et admin en moins d'une minute. Les deux autres mots de passe n'ont pas été trouvés. En effet, les tables stockées sur la clé USB peuvent cracker des mots de passe de jusqu'à 6 caractères, en utilisant le jeu de caractères 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz-_ avec une efficacité de 99,96%. Les deux autres mots de passe sont plus longs et donc Cugparck ne peut pas les cracker avec ces tables.

Références

[1] Hellman, M. (1980). A cryptanalytic time-memory trade-off. IEEE transactions on Information Theory, 26(4), 401-406.

[2] Oechslin, P. (2003, August). Making a faster cryptanalytic time-memory trade-off. In Annual International Cryptology Conference (pp. 617-630). Springer, Berlin, Heidelberg.

[3] Avoine, G., Carpent, X., & Leblanc-Albarel, D. (2021, October). Precomputation for Rainbow Tables has Never Been so Fast. In European Symposium on Research in Computer Security (pp. 215-234). Springer, Cham.

[4] Avoine, Gildas & Carpent, Xavier. (2013). Optimal Storage for Rainbow Tables. 10.1007/978-3-319-12160-4_9.