Flux RSS - La vie du site - Nouveautés et mises à jour
Assiste.com - Sécurité informatique - Vie privée sur le Web - Neutralité d'Internet Assiste.com - Sécurité informatique - Vie privée sur le Web - Neutralité d'Internet

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.

01.01.2012 - Révision 21.08.2020 - Révision mineure 21.09.2021. Auteur : Pierre Pinard.

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 :

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.

Rainbow Tables - Réputation d'un algorithme de calcul de condensats

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).


Exemples d'algorithmes de hachage

CRC-16

Produit un hashcode (condensat) de 16 bits (4 caractères hexadécimaux)

CRC-32

Produit un hashcode (condensat) de 32 bits (8 caractères hexadécimaux)

CRC-64

Produit un hashcode (condensat) de 64 bits (16 caractères hexadécimaux)

MD5

Produit un hashcode (condensat) de 128 bits (32 caractères hexadécimaux)

SHA-1

Produit un hashcode (condensat) de 160 bits (40 caractères hexadécimaux)

SHA-256

Produit un hashcode (condensat) de 256 bits (64 caractères hexadécimaux)

SHA-512

Produit un hashcode (condensat) de 512 bits (128 caractères hexadécimaux)

Etc.

...


Exemples de stockages chiffrés (cryptés) d'un même
mot de passe selon divers algorithmes de hachage :

Mot de passe

Secret 1

Bytes

53:65:63:72:65:74:20:31 (longueur=8)

Adler32

0d5002b8

CRC-32

f12d6570

Haval

45d48542b5ee305a769ad2a772a2f240

MD2

4934bfbb60dacd24004f3f9eba0dae5b

MD4

681960160ad1ee6aba6574beae65299e

MD5

3827558347b988089547698445ea8dc4

RipeMD128

1e7a09422c54864d1ff83c9d61bcf409

RipeMD160

a4cf327f6bb9ff9903a64fd5e9f409d7f36dd5ef

SHA-1

7136a0430119d37b00f9723177bc14eb4e5a3a84

SHA-256(SHA-2)

5a1c45473a963981e0a182815a9431caa6ba32c7c464f9aa8e24e9b9c14f5df7

SHA-384 (SHA-2)

70e52c8258950198be14b23167b5ef78ec4f73d46f3e4263c3ef7fae539d9f25413a2804cd08454ed259f79db0b06316

SHA-512 (SHA-2)

22ffbc4c4f0c243d8dff78aac024c7699db6dffba5e25032353eceab3237ee7b02c72c24a3ce8928a84f171363065bec3b3031b47c18e16b8fd98f98d6504b66

Tiger

7ef5afbb8327bd37166ab63cb27cd64752284f237d8da6d6

Whirlpool

baac0f62f8a9fb13a9b6d797380b4a335f915332c791487aa9214c883caf2d1aa9676fc03819500c25eafd0c9aea69b87efe3b5000e26fff4aa7f9ee7484a46b

  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.

Rainbow Tables - L'intérêt des condensats est triple

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).

Rainbow Tables - Application des condensats aux mots de passe

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,5624406176222E+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.


Note :

Le cybercriminel gagne du temps s'il sait quel est le jeu de caractères autorisé pour la création des « mots de passe » qu'il tente de casser, ainsi que les longueurs minimum et maximum de ces mots de passe. Ces informations sont faciles à obtenir : il suffit de tenter d'ouvrir un compte sur le système attaqué pour que l'autorité vous dise, la plupart du temps, que votre « mot de passe » doit faire tant de caractères de long et ne comporter que tels et tels caractères. Le choix de l'algorithme d'attaque en « Force brute » ou du dictionnaire pour une « attaque par Dictionnaire » ou de la Rainbow table est ainsi précisé.


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

Rainbow Tables - Rainbow Tables - régler le problème du temps

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.

Rainbow Tables - Rainbow Tables - régler le problème du volume

Dossier (collection) : Mots de passe

Introduction au dossier

Concepts, attaques, défenses
16 formes d'attaques des mots de passe
Attaque en force brute
Attaque Man in the Middle
Attaque par authentification faible
Attaque par authentification frauduleuse
Attaque par caméra de surveillance
Attaque par dictionnaire exhaustif
Attaque par espionnage humain
Attaque par ingénierie sociale
Attaque par keylogger
Attaque par keylogger acoustique
Attaque par keylogger électromagnétique
Attaque par le virus PEBCAK
Attaque par phishing
Attaque par sniffing sur protocole HTTPS
Attaque par tables arc-en-ciel
Attaques célèbres et réussies de mots de passe
Décrypter un hashcode
Double authentification
Générateur de hashcode cryptographique
Générateur de mots de passe
Générateur d'identifiant (pseudo)
Heartbleed (faille dans OpenSSL) affecte les mots de passe
Identifiant
Identifier l'algorithme de hachage utilisé
Jeux de caractères utilisés dans les mots de passe
Logiciels craqueurs de mots de passe
Mot de passe
Mot de passe : test de solidité
Mots de passe imbéciles
Mots de passe par défaut (usine, constructeur, éditeur)
Risque juridique de complicité passive de l'internaute
Virer le mot de passe protégeant le BIOS

Termes (encyclopédie)
CRC
CRC-1
CRC-12
CRC-16
CRC-32
CRC-64
MD5
NTLM
SHA-1
SHA-2
SHA-224
SHA-256
SHA-384
SHA-512
BIOS
Chiffre clé
Clavier virtuel
CMOS
Condensat
Cryptographie
Exploit
Hack
Hacker
Hashcode
Heartbleed
Identifiant
Ingénierie sociale
Keylogger
Login
Mots de passe
Password Cracker
Password Revealer
Password Stealer
Phishing
Rainbow Tables (Tables Arc-en-ciel)
Spyware
UEFI

Logithèque
HashTab - Calcul de condensats (Windows)
SummerProperties - Calcul de condensats




Rainbow Tables - Ressources


# Ailleurs sur le Web #

  1. #Rainbow Tables#