Attaque par dictionnaire et le problème de volume

Avec des dictionnaires exhaustifs de mots de passe et leurs hashcodes pré-calculés (les plus utilisés étant MD5 et SHA-1), le problème du temps de calcul (parfois plusieurs siècles à plusieurs millénaires) rencontré lors d'attaques en "Force brute" est résolu.

L'attaque par dictionnaires exhaustifs dure quelques nanosecondes, c'est tout. Mais un autre problème voit le jour : celui de la taille des dictionnaires.

Des logiciels simples, s'appuyant sur du matériel simple, permettent de construire des dictionnaires de " tous les mots de passe possibles " (toutes les combinaisons et permutations possibles de caractères, selon deux critères simples :

1. Le jeu de caractères autorisé
2. La longueur maximum du mot de passe) et de leurs hashcodes.

Un outil gratuit et Open Source comme " crunch - wordlist generator" fait l'affaire.

Prenons l'exemple d'un mot de passe habituel en 2012 : 8 caractères avec un jeu de caractères type 3 (voir § ci-dessous).

Cela fait 221 919 451 578 090 mots de passe possibles.

Ensuite (ou en même temps), on calcul les hashcodes, en MD5 et en SHA-1, de chaque mot de passe (les deux algorithmes de hachage les plus répandus).

On insère tout cela dans des fichiers indexés ultra rapides et ne prenant aucune place en mémoire Ram : les Arbres-B (B-Trees) (on est très loin de la "technologie" imbécile de DOS / Windows qui consiste à faire intégralement monter un fichier en mémoire (écroulement de la RAM disponible) pour faire une recherche pitoyablement séquentielle dedans (écroulement du temps)).

Chaque ligne de ce fichier (chaque "record") est long de 8 caractères (le mot de passe) + 16 caractères (le MD5 codé sur 128 bits) + 20 caractères (le SHA-1 codé sur 160 bits), soit un total de 44 caractères.

Pour faire simple, disons que la technologie Arbres-B (B-Trees) de ces fichiers, dans lesquels le hash MD5 et le hash SHA-1 sont des index, double la taille occupée par chaque "record". Chaque "enregistrement" (chaque ligne) de ce dictionnaire pèse donc 88 caractères.

Le dictionnaire aura donc une taille de : 88 x 221 919 451 578 090 caractères, soit 19 528 911 738 871 900 caractères soit 19528911,74 téraoctets !

Un dictionnaire de tous les mots de la langue du mot de passe attaqué, c'est 200.000 mots environ (moins en anglais, plus en français - 62 500 mots dans le petit Larousse 2014, environ 60.000 mots dans le petit Robert, environ 100.000 mots dans le grand Robert, 200.000 selon l'Académie Française, ici). C'est très peu de mots. Un dictionnaire de 200.000 mots, augmenté de 200.000 Hashcodes en MD5 et de 200.000 Hashcodes en SHA-1, prend très peu de place et l'attaque est très rapide.

Autres dictionnaires :

• Environ 20.000 prénoms
  
• Environ 1.500.000 patronymes
  
• Les noms d'animaux (nombre ?)
  
• Les immatriculations possibles de véhicules (nombre ?)
  
• Les juxtapositions et permutations de patronymes/prénoms ou prénoms/patronymes ou leurs initiales
• Les dates - on se limitera aux 100 dernières années soit, à raison de 365 dates par an, 36.500 dates.

Par contre, un dictionnaire de toutes les combinaisons de mots de passe possibles avec, seulement, le jeu de caractères le plus faible (type 1 (voir § ci-dessous) soit 26 lettres + 10 chiffres, insensible à la case), permet de casser le mot de passe en quelque nanosecondes.

Mais c'est le volume de données d'un tel dictionnaire qui ne permet pas l'attaque par dictionnaire :
Pour des mots de passe de 8 caractères, le dictionnaire exhaustif pèserait 81 248 téraoctets (2 901 713 047 668 combinaisons de mots de passe de 8 caractères + 20 caractères pour le hash SHA-1 soit 2 901 713 047 668 x 28 = 81 247 965 334 704 caractères )!

Le temps de recherche dans de tels dictionnaires n'est pas excessivement long (s'ils pouvaient être construits) : tri préalable sur le hash puis recherches par dichotomie en accès direct (le hash étant en binaire, il est incompressible et une recherche par arbre-B (B-Tree) doublerait la taille du dictionnaire pour un gain, en vitesse d'accès, assez faible ).

Mots de passe de 9 caractères : 3 029 388 téraoctets
Mots de passe de 10 caractères : 112 818 603 téraoctets
Mots de passe de 11 caractères : 4 196 852 043 téraoctets
Mots de passe de 12 caractères : 155 960 437 193 téraoctets
Mots de passe de 13 caractères : 5 790 031 230 781 téraoctets
Mots de passe de 14 caractères : 214 757 522 014 427 téraoctets

Donc on ne peut pas construire de tels dictionnaires (sauf, peut-être, la NSA (UKUSA) ou l'Europe, qui ont des capacités de stockage illimitées)

Ces dictionnaires permettent d'avoir sous la main, en une fraction de seconde, la conversion en "clair" d'un hashcode mais leurs volumes sont tels que le principe lui-même des dictionnaires exhaustifs est impossible à mettre en oeuvre sauf pour des mots de passe très court s'appuyant sur des jeux de caractères de type 1 ou 2..

Les types de jeux de caractères

Les mots de passe donnés aux sites Web, lors de la création d'un compte, sont uniquement conservés de manière chiffrée/cryptée, en utilisant un algorithme de condensat/hashcode (encore que des hacks de certains sites ont prouvé que ce n'était pas toujours le cas).

Plus le jeu de caractères autorisé est riche, plus les tentatives de casser le chiffrement par condensat/hashcode des mots de passe seront difficiles, voire impossibles.

Vous pouvez donc juger rapidement de l'intérêt que met un site Web à vous protéger ou à s'en moquer éperdument (ou pour d'autres raisons plus troubles)

Les types de jeux de caractères

Pour simplifier, les jeux de caractères autorisés/utilisés par les sites Web sont classés, arbitrairement, en 4 types (il y a bien d'autres jeux de caractères intermédiaires) :

1. Type 1 : Les 26 lettres de l'alphabet
   Toutes les 26 lettres de l'alphabet, et seulement ces 26 lettres, en majuscules seulement ou en minuscules seulement. Ce jeu de caractères est très restrictif et un mot de passe court (8 à 12 caractères) est cassable en quelques secondes ou quelques minutes par attaque en force brute ou par dictionnaire ou avec des tables arc en ciel.
   ABCDEFGHIJKLMNOPQRSTUVWXYZ
   Ou
   abcdefghijklmnopqrstuvwxyz
   
   
2. Type 2 : Le type 1 augmenté des 10 chiffres
   Amplitude : 36 caractères.
   Très restrictif et cassable très rapidement.
   ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789
   Ou
   abcdefghijklmnopqrstuvwxyz0123456789
   
   
3. Type 3 : Les types 1 ou 2 ou insensibles à la case
   Amplitude : 52 ou 62 caractères.
   Restrictif et cassable assez rapidement.
   ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
   ou
   ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789
   
   
4. Type 4 : Le type 3 avec plus ou moins de caractères spéciaux et accentués
   Type 3 augmenté d'un nombre plus ou moins restreint de caractères spéciaux et de caractères accentués (jeu de 90 à plus de 100 caractères).
   C'est le seul type recommandé. Dans les évaluations de temps de calcul en attaque par "Force brute" ou de volume mémoire en attaques par "dictionnaire exhaustif", nous retiendrons un type 4 à 100 caractères.
   Exemples de jeux de caractères :
   ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789,?;.:/!§%µ
   Ou
   ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789²&é"'(-è_çà)=#{[|\^@]}^¨$£¤ù%*µ,?;.:/!§
   

Temps de construction d'un dictionnaire intégral (MD5 et SHA-1 simutanés)

Combien de temps faut-il pour construire un dictionnaire exhaustif ?

Nous disposons d'une base de temps de référence : en 2007, nsa.unaligned.orga conduit une construction d'un dictionnaire en s'appuyant sur un matériel spécifique. Il a fallu une seule journée pour calculer et construire un dictionnaire intégral, incluant les hashcodes, de toutes les combinaisons possibles de caractères pour des mots de passe de 8 caractères construits avec un jeu de caractères de type 3 (jeu de 64 caractères dans leur test, soit le calcul d'un dictionnaire contenant 221 919 451 578 090 entrées).

Cette opération a été menée avec des circuits logiques programmables (FPGA - field-programmable gate array, réseau de portes programmables) Virtex-II Pro (XC2VP20) introduit sur le marché en 2002. Ils délivrent 8000 MIPS.

En 2009, leur successeur est introduit sur le marché, Virtex-7 qui délivre 180.000 MIPS soit 22,5 fois plus de puissance.

A partir de là, on calcul le nombre de jours nécessaires pour calculer d'autres dictionnaires par de simples règles de trois.

On peut estimer que, mis à part le problème insoluble du volume de stockage de tels dictionnaires (plusieurs millions de milliards de teraoctets), tous les types de mots de passe dont l'établissement du dictionnaire intégral prend moins de 6 ans (2200 jours), sont compromis.

Les dictionnaires intégraux sont déjà tous construits mais leurs volumes les rend intransportables et inexploitables (sauf à disposer des moyens financiers, des moyens de stockage et des puissances de calcul de la NSA).

Les "Tables Arc en ciel" (Rainbow Tables) ont règlé le problème du compromis temps de calcul / volume de stockage.

Ces durées doivent sans arrêt être revues à la baisse. Les techniques de calcul distribué permettent de mettre simultanément des centaines de milliers ou des millions de PC, dotés de processeurs graphiques dont la puissance de calcul phénoménale augmente continuellement, au service de la résolution d'un même problème.

En 2012 on peut raisonnablement penser que toutes les "rainbow table", pour tous les algorithmes de chiffrement massivement utilisés (au moins MD5 et SHA-1), pour tous les types de jeux de caractères et pour toutes les longueurs de mots de passe jusqu'à 10 caractères, sont entièrement calculées. Les tables pour les mots de passe de 11 à 12 caractères devraient suivre.

Contre-mesures

Il ne faut jamais utiliser un mot (ou une combinaison de mots) réel existant dans un dictionnaire (Larousse, Robert, etc. ...)
Utilisez des mots de passe d'au moins 14 caractères de long !
Calculer la résistance de vos mots de passe.