Et oui, parce que 1.9 milliards de mots de passe par seconde sur une architecture SIMD 128 bits, avec 6 cœurs à 3.2 Ghz, ça fait environ 40 cycles par mot de passe. Dur à croire, comme on le verra par la suite.

Au delà des trolls immédiats[1], et comme il est difficile d'expliquer la crédulité des comités d'organisation ou des journalistes, il peut être intéressant d'entrevoir des pistes pour détecter ce genre de mascarades. En pratique, ce billet va essayer de répondre à la question suivante : quelle est la vitesse maximale de cassage de mot de passe pour une fonction de hachage donnée ?

Tout d'abord, commençons par calculer le nombre d'opérations nécessaires pour MD5, décrit dans le RFC 1321. Comme le décrit le RFC, cinq étapes sont nécessaires pour hacher une zone de mémoire :

  • ajout des bits de bourrage[2] : le bloc à hacher doit avoir une taille finale multiple de 64 octets ;
  • ajout d'une valeur dépendant de la taille à hacher vers la fin : les derniers 64 bits contiennent la taille multipliée par 8 ;
  • initialisation des quatre registres d'état ;
  • calcul des 4 rondes composées de 16 étapes chacunes ;
  • calcul de la valeur finale.

Nous allons prendre l'hypothèse, comme Nick Breese, que l'on ne va calculer que des mots de passe de taille fixe, ici 7 caractères. Pour le mot de passe "ABCDEFG", la zone mémoire sur laquelle seront effectués les calculs aura cet air à l'issue de l'étape 2 :

41424344 45464780 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 38000000 00000000

Par la suite, on parlera de cette zone mémoire comme d'un tableau d'entiers de 32 bits nommé M. Si la taille du mot de passe est fixée à 7 caratères, seuls les 7 premiers octets seront modifiés lorsque le mot de passe changera, soit M[0] et M[1]. Une fois le tampon initialisé, ces deux phases ne prendront donc pas de temps processeur et peuvent être ignorées pour la suite.

L'étape 3, qui consiste en pratique à initialiser 4 registres de 32 bits comptera donc 4 opérations.

L'étape 4 est la plus complexe. Elle est composée 4 rondes, chacune contenant 16 étapes. Une étape est définie ainsi :

ETAPE(a,b,c,d,M,val,rotation)
a += FUNC(b,c,d)
a += M
a += val
a = rotation_gauche(a, rotation)
a += b

Ici a, b, c et d sont variables, alors que M, val et rotation sont donnés et connus pour chaque étape. La fonction FUNC varie pour chaque ronde, et consiste en 3 opérations pour les rondes 1, 2 et 4, ou seulement deux opérations pour la ronde 3. On peut en déduire que cette étape consomme :

16*(5+3) + 16*(5+3) + 16*(5+2) + 16*(5+3)

Soit 496 opérations. Mais il est en pratique possible de faire beaucoup mieux !

En effet, il faut bien comprendre que l'on n'a pas besoin de calculer l'empreinte exacte d'un mot de passe testé, mais juste de vérifier si, en fin de compte, elle sera identique à un mot de passe recherché. Cette approche est par exemple mise en œuvre lorsqu'une conversion d'endianité est à réaliser entre les résultats calculés et les empreintes à découvrir. Il est alors plus malin de convertir l'endianité de toutes les empreintes à casser une seule fois, avant de commencer les calculs, que de convertir celle de tous les hachages calculés. On va ici prendre comme hypothèse que l'on connait les 3 derniers caractères du mot de passe, et donc que la seule inconnue réside dans M[0]. Si on regarde la dernière ronde et la fin de la troisième, on peut voir les opérations suivantes :

ETAPE_C(a, b, c, d, M[ 9], constante_45, 4 )
ETAPE_C(d, a, b, c, M[12], constante_46, 11)
ETAPE_C(c, d, a, b, M[15], constante_47, 16)
ETAPE_C(b, c, d, a, M[ 2], constante_48, 23)

ETAPE_D(a, b, c, d, M[ 0], constante_49, 6 )
ETAPE_D(d, a, b, c, M[ 7], constante_50, 10)
ETAPE_D(c, d, a, b, M[14], constante_51, 15)
ETAPE_D(b, c, d, a, M[ 5], constante_52, 21)
ETAPE_D(a, b, c, d, M[12], constante_53, 6 )
ETAPE_D(d, a, b, c, M[ 3], constante_54, 10)
ETAPE_D(c, d, a, b, M[10], constante_55, 15)
ETAPE_D(b, c, d, a, M[ 1], constante_56, 21)
ETAPE_D(a, b, c, d, M[ 8], constante_57, 6 )
ETAPE_D(d, a, b, c, M[15], constante_58, 10)
ETAPE_D(c, d, a, b, M[ 6], constante_59, 15)
ETAPE_D(b, c, d, a, M[13], constante_60, 21)
ETAPE_D(a, b, c, d, M[ 4], constante_61, 6 )
ETAPE_D(d, a, b, c, M[11], constante_62, 10)
ETAPE_D(c, d, a, b, M[ 2], constante_63, 15)
ETAPE_D(b, c, d, a, M[ 9], constante_64, 21)

La constatation importante à faire est que l'inconnue, M[0], est utilisée pour la dernière fois à l'étape 49 du calcul. Il devient donc possible, pour une empreinte à casser donnée, de calculer la valeur qu'auraient du avoir a, b, c et d à la fin de l'étape 49 si on connaissait tout le reste, c'est à dire le contenu du tampon mémoire entre les bits 33 et 512 et le hachage final. Mieux, comme a, b, c et d sont mis à jour l'un après l'autre, il est possible de connaitre la valeur de b, c et d à la fin de l'étape 48, de c et d à la fin de l'étape 47 et donc de d à la fin de l'étape 46! Dans le cas où notre casseur de mot de passe fait varier les 4 premiers caractères beaucoup plus souvent que les autres, il devient possible de ne calculer la plupart du temps que 46 étapes au lieu de 64.

Pour finir, on peut sauter l'addition avec M[x] lorsqu'il est nul, c'est à dire lorsque x n'est pas égal à 0, 1 ou 14. La quantité d'opérations nécessaires devient :

16*(5+3) - 13 + 16*(5+3) - 13 + 14*(5+2) - 11

Soit 317 opérations.

Les dernières étapes du RFC ne sont pas effectuées, au profit d'une comparaison avec le ou les mots de passe à casser. Ici, si on casse un mot de passe unique, stocké en dur, on comptera une opération pour le test, et une opération pour le saut conditionnel.

Au total, on doit donc au minimum réaliser 4+317+2 = 323 opérations. On peut y ajouter une opération pour incrémenter le mot de passe testé et donc réaliser un crackeur complet, portant le total à 324 opérations. Maintenant, si on imagine que chaque opération ne prend qu'un cycle processeur[3] , qu'on n'a pas de problèmes de cache/accès mémoire[4] et surtout pas de problèmes de remplissage du pipeline[5], alors il est possible de calculer le débit maximum d'un processeur :

  • pour 1Ghz, on peut calculer (1000000000/324) = 3086419 (3.1M) mots de passes par seconde ;
  • si on a une architecture SIMD 128 bits (4 fois 32 bits), cadencée à 1Ghz, on peut aller jusqu'à (4*1000000000/324) = 12345679 (12.3M) mots de passes par seconde.

Pour la Playstation 3, qui possède 6 cœurs utilisables[6] cadencés à 3.2Ghz, on peut donc théoriquement casser 237 millions mots de passe par seconde, et ce dans un contexte très limité et avec des hypothèses très généreuses. Pour comparer, un MD5 littéral, c'est à dire où l'étape 4 prend 496 opérations, avec un assez bon remplissage du pipeline mais aucune autre optimisation, tourne à 120 millions de tests par seconde. En réduisant l'étape 4 on pourrait atteindre 180 millions de tests par seconde, ce qui n'est pas si loin du maximum théorique. On peut donc voir que dans un futur proche il ne sera pas possible de faire mieux que quelques centaines de millions de mots de passe par secondes sur des processeurs génériques.

Et que BlackHat, c'était mieux avant...

Bartavelle

Notes

[1] Genre "les conférences de sécurité n'existent que pour payer des vacances aux consultants", "la BlackHat ne selectionne ses conférences que pour leur impact médiatique", etc.

[2] Padding.

[3] C'est probablement faux sur la PS3, mais je n'ai pas trouvé de réference correcte sur la latence des différentes instructions. A priori, seule l'instruction de rotation devrait poser des problèmes.

[4] Possible sur PS3.

[5] Également possible sur PS3.

[6] En réalité il y en a 7, mais le seul environnement disponible au commun des mortels, c'est-à-dire Linux, ne permet pas d'accéder au dernier cœur qui sert d'hyperviseur.