Cassage des mots de passe par tables pré-calculées

Des chercheurs de l'école polytechnique de Lausanne (EPFL) ont publié ce mois-ci les résultats de leur étude sur le cassage des mots de passe, en expliquant qu'ils pouvaient dorénavant découvrir n'importe quel mot de passe Windows en moins de 14 secondes.

D'un point de vue technique, précisons que :

• il s'agit de casser l'empreinte "LMhash" ("LanManager hash"). Cette empreinte est l'une des deux formes utilisées par Windows pour stocker les mots de passe, l'autre étant l'empreinte "NThash". Le "LMhash" est moins robuste que le "NThash", mais existe en standard sur tous les systèmes Windows pour des raisons de compatibilité avec les anciens systèmes, et en particulier avec Windows 9x.

• l'attaque est réalisée en ayant pré-calculé des empreintes "LMhash", et en comparant l'empreinte "LMhash" à casser à ces empreintes pré-calculées. Cette approche est possible avec le "LMhash" parce que cette empreinte n'utilise pas de notion de "diversifiant" : un mot de passe donné produit toujours la même empreinte "LMhash". Les autres algorithmes (et en particulier l'empreinte "crypt" standard sous UNIX) utilisent quant à eux un "diversifiant" qui fait que 2 utilisateurs différents ayant le même mot de passe auront 2 empreintes différentes (parce qu'une valeur différente du "sel" aura été utilisée pour chacun).

• les chances de succès sont de 99,9 % car, comme nous l'expliquons plus loin la méthode cassage proposée fait intervenir une notion de probabilité.

• la plate-forme de test utilisée pour obtenir le temps moyen de cassage (13,6 secondes) est un PC tout à fait standard : il s'agit d'un Pentium 4, 2Ghz muni de 500 Mo de RAM.

On voit donc que l'attaque mise au point concerne un cas tout à fait particulier. Ce type d'attaque a d'ailleurs été identifié depuis longtemps (faiblesse de l'empreinte "LMhash", et possibilité d'utiliser un dictionnaire d'empreintes pré-calculées). Il n'en reste pas moins que la démonstration faite aujourd'hui par ces chercheurs montre clairement que le danger est réel : si une machine Windows est compromise, et si la compatibilité "LMhash" n'a pas été supprimée (ce qui se fait en positionnant une clef de registre), les mots de passe stockés seront découverts en des temps records : moins de 14 secondes par mot de passe.

En fait les travaux de recherche publiés par l'EPFL ont pour objet premier de proposer des améliorations aux algorithmes définis en 1982 pour implémenter le principe d'attaque par tables d'empreintes pré-calculées. Et il a été choisi de démontrer l'efficacité de ces algorithmes améliorés sur le cas des empreintes "LMhash" de Windows : les anciens algorithmes nécessitent 101 secondes, là où dorénavant 13,6 secondes suffisent.

Pour compléter cet article, il nous paraît intéressant de décrire plus en détail le principe des tables d'empreintes pré-calculées, tel que proposé au début des années 80 par Martin Hellman. En effet le principe n'est pas, comme on pourrait le penser, de construire un grand dictionnaire donnant l'empreinte pour chacun de mots de passe possibles : la taille de ce dictionnaire serait alors énorme (2^37 entrées dans le cas de l'empreinte "LMhash"). Au contraire, "l'astuce" est de ne conserver que certaines de ces empreintes (typiquement une sur 4000) et d'en déduire les autres par une fonction de dérivation. Plus précisément, l'algorithme de Hellman crée des chaînes d'empreintes du type :

Mot de passe1 => empreinte 1 -> Mot de passe 2 => empreinte 2 ->… -> Mot de passe N => empreinte N

La fonction "f" qui transforme une "empreinte 1" en un "Mot de passe 2" est une fonction arbitraire (par exemple : transformer chaque octet de l'empreinte en un caractère imprimable) qui a pour seul but de créer une chaîne (une succession) d'empreintes. En effet, si cette chaîne existe, il n'est plus nécessaire de conserver toutes les empreintes contenues dans la chaîne, mais simplement la tête de la chaîne ("Mot de passe 1") et la fin ("empreinte N") : toutes les autres valeurs peuvent être recalculées rapidement au moment où l'on en a besoin. Le dictionnaire des empreintes pré-calculées est donc en fait un tableau mémorisant les couples ("Mot de passe 1", "empreinte N") pour X chaînes qui ont été pré-calculées, et la probabilité de trouver un mot de passe (par exemple 99,9%) dépend du nombre X de chaînes que l'on utilise, et de l'efficacité de la fonction "f". Il faut trouver un couple "(X,f)" qui donnera une bonne couverture de l'espace de tous les mots de passe possibles.

Une fois que l'on a construit le dictionnaire des empreintes pré-calculées, on peut l'utiliser pour casser des empreintes. Pour ce faire, le logiciel de cassage dérive N fois l'empreinte à casser, en examinant à chaque fois si l'empreinte générée correspond à la queue d'une des chaînes pré-calculées. Si c'est le cas, on sait alors que l'empreinte à casser se trouve dans la chaîne de dérivation, et il suffit de parcourir exhaustivement celle-ci depuis le début pour retrouver le mot de passe ayant généré l'empreinte.

L'amélioration décrite par les chercheurs de l'EPFL consiste en fait à proposer un nouveau type de chaîne (baptisée la chaîne "arc-en-ciel") plus efficace que celles proposées jusque-là.

Pour plus d'information

• La publication des chercheurs de l'EPFL : http://lasecwww.epfl.ch/php_code/publications/search.php?ref=Oech03

• L'outil de cassage des mots de passe Windows réalisé pour "illustrer" cette publication : http://lasecpc13.epfl.ch/ntcrack/