Rainbow Tables (Tables arc-en-ciel)

Entre le temps infini de la Force brute et la mémoire infinie des dictionnaires, les « Rainbow tables » (tables arc-en-ciel) sont un compromis temps/mémoire utilisé en cryptanalyse pour remonter d'un hashcode à casser au mot de passe d'origine.

cr  01.01.2012      r+  21.08.2020      r-  18.04.2024      Pierre Pinard.         (Alertes et avis de sécurité au jour le jour)

Un des usages de la cryptographie est de partir d'une donnée et d'en calculer un condensat (un hashcode ou chiffre clé). Exemple :

• Mot de passe : Papa aime Maman

• Son condensat, selon l'algorithme MD5, est : 99685cdcbee4ac3fc7934da83b703a10

La moindre modification du mot de passe entraine la production d'un condensat totalement différent. Si l'algorithme est bon, le condensat produit est toujours unique, aucun autre texte ne conduira à un condensat identique (ce qui conduit, d'ailleurs, à déconseiller MD5 avec lequel on arrive à provoquer des collisions [2006 - MD5 Collision Demo]).

Un condensat est une valeur calculée par un algorithme de hachage appliqué à une donnée (contenu d'un fichier, chaîne de caractères saisie, etc.), uniquement la donnée et toute la donnée. Si la donnée est dans un fichier, peu importe le nom du contenant, ses attributs, ses dates prétendues de création ou de dernière modification, etc., qui sont toutes des informations extérieures à la donnée elle-même (comme avec le courrier postal elles forment l'enveloppe dont on ne doit pas tenir compte - on ne tient compte que du contenu).

Les algorithmes de hachage les plus universellement utilisés en matière de chiffrement des mots de passe, en 2021, sont MD5, SHA-1, SHA-256.

Les mots de passe ne sont pas conservés, seuls les condensats sont conservés. Comment remonter du condensat au mot de passe ?

1. On peut chercher à s'attaquer aux condensats des mots de passe par attaque par dictionnaire exhaustif en construisant un dictionnaire intégral de toutes les possibilités de caractères pour chaque longueur de mots de passe couramment imposée (6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 caractres) et générer automatiquement tous les condensats. On monte chaque dictionnaire en fichier à recherche indexée pour faire des recherches instantanées. Le problème est que la taille de chacun de ces dictionnaires est monstrueuse et que seuls ses états peuvent essayer de mettre en place de tels centres de données.

2. On peut chercher à s'attaquer aux condensats des mots de passe par attaque en force brute. Aucune taille de mémoire nécessaire, mais du temps de calcul monstrueusement long (on peut compter, pour des mots de passe utilisant des minuscules, majuscules, chiffres, caractères accentués et caractères spéciaux, des milliards de milliards de siècles, même avec des ordinateurs spéciaux d'une puissance inimaginable.)

Sont alors apparues les tables arc-en-ciel (rainbow tables) qui permettent un compromis temps/mémoire.

La réputation de l'algorithme de calcul d'un hashcode (calcul d'un condensat - fonction de hachage) est de ne jamais produire deux hashcodes identiques si les objets (fichiers) contiennent la moindre différence. La fonction de hachage doit donc produire une clé unique d'identification d'une donnée unique (calcul homogène).

1. Intégrité des données
   Il est impossible de modifier la donnée (injection d'un parasite, tel un virus, modification d'un seul bit ou, tout simplement, nouvelle version de la donnée...) en lui conservant un même résultat de calcul de "chiffre clé". Par exemple : un fichier est proposé en téléchargement et son "chiffre clé" MD5 ou SHA-1 est affiché sur le site proposant ce fichier (c'est le cas de Assiste.com - regardez la zone de téléchargements du site). Une fois le fichier réceptionné, vous utilisez SummerProperties pour recalculer ce "chiffre clé" avec le même algorithme MD5 ou SHA-1. Si les deux "chiffres clé" sont identiques, le fichier réceptionné est strictement le même que celui d'origine. C'est le principe du "Contrôle d'intégrité des données" qui ne doit pas être confondu avec l'innocuité des données - vous pouvez seulement vous assurer que le téléchargement s'est bien passé, rien d'autre - si le fichier téléchargé est un virus, vous vérifiez ainsi que vous avez reçu un virus en parfait état ! Faites-le analyser gratuitement et immédiatement par plus de 70 antivirus simultanés avant de l'exécuter (avant de l'ouvrir) !

2. Calcul à sens unique (théoriquement)
   Il n'est, théoriquement, pas possible de faire le calcul inverse : de remonter d'un "chiffre clé" (Hashcode) à la chaîne de caractères d'origine (il n'est pas possible (théoriquement) de retrouver le mot de passe à partir de son chiffre clé). Nous verrons, dans les techniques d'attaques des mots de passe, que ce vœu pieux est battu en brèche.

3. Unicité du chiffre clé
   De purs travaux de laboratoire ont permis la création de "chiffres clé" identiques (appelés "Collisions") à partir de données différentes. Ce risque est total avec les algorithmes antédiluviens et abandonnés comme CRC-16 et CRC-32. Ce risque existe avec les algorithmes MD5 avec lesquels il est désormais possible de créer des "Collisions". Pour prendre un peu d'avance sur les futurs développements matériels et logiciels des cybercriminels, même SHA-1 est en voie d'abandon et l'on commence le calcul des condensats avec SHA-256.

Lorsque vous créez un mot de passe pour protéger l'accès à une ressource (votre ordinateur, un fichier, un compte sur un site ou un forum, un panneau de gestion d'un compte en banque d'entreprise ou de particulier, un document secret d'un chercheur, d'un journaliste, d'un avocat..., les correspondances d'un diplomate ou d'un homme politique, etc.), le mot de passe n'est pas (normalement) stocké en clair. Le site de confiance le crypte, sous forme d'un hashcode, le plus souvent avec l'algorithme MD5, SHA-1 ou SHA-256 et stocke uniquement votre identifiant et le hashcode de votre mot de passe, mais ne stocke jamais le mot de passe lui-même.

Lorsque vous revenez vous identifier pour utiliser cette ressource protégée, vous saisissez (composez) à nouveau votre identifiant (login) et votre mot de passe. Le site refait un calcul de hashcode avec le même algorithme.

Le site compare alors le hashcode de référence du mot de passe au hashcode du mot de passe qui vient d'être saisi. Si les deux hashcodes sont identiques, c'est que les deux mots de passe sont identiques. L'autorité vous donne alors accès à la ressource, sinon elle vous en interdit l'accès.

• Note 1
  D'où l'intérêt des logiciels en "Open Source" où l'on peut voir comment sont traitées les données sensibles tandis qu'on ne peut qu'avoir des soupçons de malveillances avec les logiciels "propriétaire" et les sites pour lesquels aucune confiance ne peut être accordée (comme tous les réseaux sociaux, les éditeurs de logiciels proches de leurs gouvernements, les nébuleuses du "Cloud Computing", etc.)
  

• Note 2
  C'est la raison pour laquelle, lorsque vous perdez votre "mot de passe", il n'est pas possible de le retrouver, car s'il est possible de calculer un MD5 ou un SHA-1 à partir d'un "mot de passe", il n'est théoriquement pas possible de retrouver (recalculer) le "mot de passe" d'origine à partir de son MD5 ou de son SHA-1.
  

• Note 3
  Il serait préférable que, lors de la saisie de votre mot de passe, la communication entre votre ordinateur et celui du site distant se fasse dans un protocole de communication sécurisé (HTTPS), sinon une attaque par "sniffer" lira vos mots de passe en clair, avant qu'ils ne soient cryptés. Regardez en bas à droite de votre navigateur si un cadenas fermé apparaît. Mais le protocoleHTTPS ne sera mis en œuvre que par des sites professionnels. Ce ne sera pas le cas des millions de forums, blogs, etc. sur lesquels il faut également s'identifier (d'où l'intérêt d'utiliser des mots de passe différents).
  

• Note 4
  Certains sites Internet usurpent l'apparence de sites ayant pignon sur rue est utilisent des URL trompeuses. Sur de tels sites de "phishing", vers lesquels vous êtes souvent dirigés depuis un e-mail trompeur, vos identifiant et mot de passe sont stockés en clair et exploités immédiatement par des cybercriminels. Et absolument rien ne permet d'être certain de ce que font les très grands sites à la solde des gouvernements, comme Microsoft (Microsoft vous espionne) ou Google (Google vous espionne).
  

Le cybercriminel, qui s'est procuré un mot de passe chiffré (son code de hachage) ou le piratage de millions de hashcodes des clients d'une banque, d'un site e-marchand, d'un réseau social, etc. (par divers procédés de piratage), va utiliser un logiciel spécialisé et, éventuellement, du matériel spécialisé, pour attaquer en force brute les hashcodes qu'il s'est procurés afin de remonter du hashcode au mot de passe en clair, bien que le hachage soit considéré comme une opération univoque (il n'est, en théorie, pas possible de remonter d'un code de hachage au texte d'origine en clair). Cette forme d'attaque en force brute contre les hashcodes consiste à tenter toutes les combinaisons possibles de caractères des mots de passe et calculer tous leurs hashcodes jusqu'à trouver les bonnes combinaisons de caractères qui correspondent aux hashcodes détenus.

Si l'algorithme de hachage utilisé est, par exemple, SHA-1, qui crypte les mots de passe en hashcodes de 160 digits de long, le nombre de calculs qui doivent être effectués est 2 ^ 160 ^ 4 (2 puisque chaque position binaire (chaque bit) ne peut prendre que deux valeurs, 0 ou 1, à la puissance 160 et que chaque digit comporte 4 bits) soit 4,5624406176222^E+192 opérations. Si l'on dispose d'une puissance de calcul de cent mille milliards de calculs de hashcodes à la seconde, il faudra, pour chaque mot de passe, 5,84 centaines de milliards de milliards de milliards de siècles pour y arriver. On ira de plus en plus vite avec la montée en puissance des machines et le nombre de machines mises en oeuvre, mais c'est le problème du temps. Accéder à une donnée avec des années de retard sur sa signifiance risque de conduire à une donnée totalement périmée, n'ayant plus aucune valeur.

On peut oser un rapprochement incongru et déclarer que les « attaques par dictionnaires » sont une forme « intelligente » d'« attaque en force brute ».

L'attaque des mots de passe par dictionnaire est une forme d'attaque dirigée contre les mots de passe en clair, pas contre leurs chiffrements (pas contre les hashcodes). On se limite à tenter des mots existants réellement dans divers dictionnaires.

L'idée est qu'un utilisateur aura tendance, naturellement, à aller vers la facilité et donc à utiliser quelque chose de facile à retenir, quelque chose existant déjà, au lieu d'une suite barbare de caractères impossibles à mémoriser (ce qui est, pourtant, l'une des règles de bonne pratique avec les mots de passe).

L'attaque par dictionnaire cherche donc à pallier le problème du temps soulevé par les attaques en force brute. Elle risque de passer à côté de mots de passe tarabiscotés, mais est beaucoup plus rapide que la force brute.

Dans une attaque par dictionnaire, on va tenter tous les mots présents dans de simples dictionnaires ou listes finies : langues, dates, immatriculations, noms d'animaux, patronymes, prénoms, etc., ainsi que les mots de passe faibles habituels (mots de passe par défaut (d'usine, d'origine), mots de passe imbéciles, etc.)

Ces dictionnaires mettent un certain temps à être construits et représentent, finalement, l'intégralité des mots et termes normalement interdits en tant que mot de passe.

Quant aux dictionnaires exhaustifs (voir l'article étendu sur les dictionnaires exhaustifs), ils occupent une place folle et un coût délirant impossibles à mettre en place sauf au niveau d'un état.

Seul le compromis temps/mémoire avec les tables Arc-en-ciel arrive à casser relativement rapidement tous les mots de passe en faisant un compromis temps/mémoire.