Limites des tables Rainbow et comment les dépasser en utilisant des méthodes probabilistes optimisées — Cedric Tissieres, Philippe Oechslin, Pierre Lestringant
Date : 06 June 2013 à 15:15 — 30 min.
Les tables Rainbow sont un moyen efficace pour casser des hashs de mot de passe non salés. La taille des ensembles de mots de passe pouvant être cassés est limitée par l'effort nécessaire pour créer les tables. L'utilisation de cartes graphiques a permis de repousser un peu cette limite. On trouve ainsi des tables d'une taille de l'ordre de quelques tera octets qui cassent des mots de passe complexes de 8 caractères (10^16). C'est là qu'apparaît la prochaine limitation: d'aussi grosses tables ne peuvent pas être stockées en RAM et difficilement en SSD ce qui rend les temps d'accès très lents et réduit considérablement leur efficacité.
Pour pouvoir passer la limite des 8 caractères, nous avons appliqué deux méthodes probabilistes. La première consiste à représenter les mots de passe par des patterns. Pour les suites de caractères qui apparaissent dans ces patterns, nous utilisons ensuite un modèle de Markov du deuxième ordre pour ne garder que les suites les plus probables. Finalement nous avons optimisé l'implémentation de ce modèle pour l'adapter aux spécificités des GPU.
Nous nous sommes basés sur des bases de données publiques (RockYou, ...) pour choisir les patterns et des pondérations de Markov les plus efficaces et avons créé deux jeux de tables: un de taille limitée pour un liveCD Ophcrack et un second de 60 gigaoctets dont les parties les plus importantes peuvent tenir en RAM lors du cassage des mots de passe.