Que sont les tables arc-en-ciel et comment sont-elles utilisées?

Les Rainbow Tables sont souvent confondues avec une autre technique plus simple qui exploite un temps de calcul-s échange de mots de passe dans la récupération des mots de passe: tables de hachage.

Les tables de hachage sont construites en hachant chaque mot dans un dictionnaire de mots de passe. Les paires mot de passe-hachage sont stockées dans une table, triées par valeur de hachage. Pour utiliser une table de hachage, prenez simplement le hachage et effectuez une recherche binaire dans la table pour trouver le mot de passe dorigine, sil est présent.

Les tables arc-en-ciel sont plus complexes. Construire une table arc-en-ciel nécessite deux choses : une fonction de hachage et une fonction de réduction. La fonction de hachage pour un ensemble donné de Rainbow Tables doit correspondre au mot de passe haché que vous voulez récupérer. La fonction de réduction doit transformer un hachage en quelque chose utilisable comme mot de passe. Une fonction de réduction simple est en Base64 encodez le hachage, puis tronquez-le à un certain nombre de caractères.

Les tables arc-en-ciel sont constituées de «chaînes» dune certaine longueur: 100 000 par exemple. Pour construire la chaîne, choisissez une valeur de départ aléatoire. Ensuite appliquez les fonctions de hachage et de réduction à cette valeur de départ et à sa sortie, et continuez litération 100 000 fois. Seules la valeur de départ et la valeur finale sont stockées. Répétez ce processus pour créer autant de chaînes que vous le souhaitez.

Pour récupérer une mot de passe en utilisant Rainbow Tables, le hachage du mot de passe subit le processus ci-dessus pour la même longueur: dans ce cas 100 000 mais chaque maillon de la chaîne est conservé. Chaque maillon de la chaîne est comparé à la valeur finale de chaque chaîne. Sil y a correspondance, la chaîne peut être reconstruite, en conservant à la fois la sortie de chaque fonction de hachage et la sortie de chaque fonction de réduction. Cette chaîne reconstruite contiendra le hachage du mot de passe en question ainsi que le mot de passe qui la produit.

Les points forts dune table de hachage sont que la récupération dun mot de passe est ultra-rapide (recherche binaire) et la personne qui construit la table de hachage peut choisir ce quil contient, par exemple les 10 000 mots de passe les plus importants. La faiblesse par rapport aux Rainbow Tables est que les tables de hachage doivent stocker chaque paire de mots de passe de hachage.

Les Rainbow Tables ont lavantage que la personne qui construit ces tables peut choisir la quantité de stockage requise en sélectionnant le nombre de liens dans chaque chaîne. Plus il y a de liens entre la graine et la valeur finale, plus les mots de passe sont capturés. Lune des faiblesses est que la personne qui construit les chaînes ne choisit pas les mots de passe quelle capture, donc Rainbow Tables ne peut pas être optimisée pour les mots de passe courants. En outre, la récupération de mot de passe implique le calcul de longues chaînes de hachages, ce qui fait de la récupération une opération coûteuse. Plus les chaînes sont longues, plus les mots de passe y sont capturés, mais il faut plus de temps pour trouver un mot de passe à lintérieur.

Les tables de hachage sont bonnes pour les mots de passe courants, les Rainbow Tables sont bonnes pour les mots de passe difficiles. La meilleure approche serait de récupérer autant de mots de passe que possible à laide de tables de hachage et / ou de craquage conventionnel avec un dictionnaire des N premiers mots de passe. Pour ceux qui restent, utilisez Rainbow Tables.

Commentaires

• Oh mon Dieu, javoue être choqué – je discute et explique les tables Rainbow toutes les temps, et tout ce temps, il semble que jai été lun des  » couramment confondus « ! Je le ferais totalement +1000 fois, jai vraiment appris quelque chose de nouveau ici (et je pensais connaître la réponse). Heureux davoir posé la question après tout … Merci!
• Bien que pour être précis (maintenant que vous avez ouvert les yeux, jai fait quelques recherches supplémentaires :)), Rainbow Tables se différencie des Hellman Hash Chains en utilisant plusieurs fonctions de réduction différentes. Plus complexe certes … mais vraiment une très belle idée (Ah! Cest cest pourquoi ils ‘ sont appelés  » Rainbow  » tables?)
• Je suis daccord que cest une très bonne explication. Dans ma réponse, je lai expliqué simplement et je lai aussi vraiment expliqué mal en étant trop simple.La beauté des tables Rainbow réside dans le fait qu’elles ne stockent ‘ aucune valeur de hachage. Je vais éditer le mien mais aussi voter pour cela car cest certainement une meilleure explication.
• Hmm … Bien que plus jy pense, dans les systèmes réels, les Rainbow Tables sont loin dêtre aussi utiles que tables de hachage. Comme vous lavez dit, pour les mots de passe courants, les tables de hachage sont bien meilleures (puisquelles sont dun ordre de grandeur plus rapide et que les exigences de taille pour un dictionnaire de mots de passe sont bien sûr beaucoup plus petites que toute la gamme possible de mots de passe). Et de qui ‘ on rigole? La plupart des mots de passe entrent dans cette catégorie, il est très rare (et le sera pendant un certain temps) que vous deviez appeler en RT.
• Malheureusement, vous mavez perdu ici:  » Pour récupérer un mot de passe à laide de Rainbow Tables, le mot de passe subit le processus ci-dessus pour la même longueur.  » Comment le mot de passe peut-il subir le processus lorsquil ‘ nest même pas connu? Voulez-vous dire le hachage du mot de passe? De plus, ‘ est ceci:  » Chaque maillon de la chaîne est comparé à la valeur finale de chaque chaîne.  » Je ne vois pas de situation où un maillon de la chaîne correspondrait à la valeur finale de la chaîne, car la valeur du lien serait continuellement hachée et réduite.

Il existe de nombreuses bonnes explications sur ce que sont les tables arc-en-ciel, celle-ci Fonctionnement des tables arc-en-ciel est particulièrement bon. L article de Wikipedia a également une très bonne explication. Pour une lecture un peu plus approfondie, larticle définitif sur le sujet est Making a Faster Cryptanalytic Time-Memory Trade-Off .

Une explication simple des Rainbow Tables est quils utilisent une technique de compromis entre la mémoire et le temps. Au lieu de prendre une valeur de hachage cible et un dictionnaire de mots, puis de hacher chaque mot et de faire la comparaison à la volée (approche par force brute utilisant quelque chose comme John ), vous hachez à la place toutes les valeurs du dictionnaire à lavance (cela peut prendre beaucoup de temps en fonction de la taille du dictionnaire). Mais une fois terminé, vous pouvez comparer autant de hachages que vous le souhaitez avec les valeurs pré-hachées dans les tables arc-en-ciel, cest beaucoup plus rapide que de calculer à nouveau les hachages.

Lexplication que jai écrite précédemment dans un effort pour être court était trompeur, car il nexpliquait pas lutilisation des réductions utilisées par les tables arc-en-ciel. Pour une meilleure explication jusquà ce que je réécrive ce bit, voir @Crunge answer .

Vous pouvez soit générer vous-même les tableaux arc-en-ciel en utilisant une application comme RainbowCrack ou vous pouvez les télécharger à partir de sources telles que The Shmoo Group , Site Web du projet Free Rainbow Tables , projet Ophcrack et de nombreux autres emplacements en fonction du type de hachage pour lequel vous avez besoin de tables.

Pour se protéger contre une attaque basée sur Rainbow Table, la méthode la plus efficace pour la combattre est de sassurer que chaque hachage dun système est salé . Cela rend les tables arc-en-ciel pré-générées inutiles et signifierait quun attaquant devrait générer un ensemble personnalisé de tables à utiliser contre les hachages ciblés, ce qui ne serait possible que sils connaissaient le sel.

Commentaires

• De plus (pensez à le modifier dans), si vous utilisez un sel différent pour chaque mot de passe, en l’enregistrant non chiffré dans la base de données, attaqué devrait générer un ensemble personnalisé de tables pour chaque hachage, ce qui vaincrait lobjet de lexercice – le but de la table arc-en-ciel est de forcer brutalement tout lespace de mot de passe, puis dobtenir tous les mots de passe pour une force brute effort; si vous ‘ nobtenez quun seul mot de passe par table arc-en-ciel, vous pouvez aussi bien forcer directement le hachage.

Objectif et pertinence

Les tableaux arc-en-ciel aident à déchiffrer les mots de passe difficiles, cest-à-dire ceux qui ne peuvent même pas être trouvés dans un grand dictionnaire. Les mots de passe étaient historiquement stockés sous forme de hachages simples dans les bases de données, et cest ce contre quoi les tables arc-en-ciel sont efficaces: créer une seule table arc-en-ciel (lente) et exécuter nimporte quel nombre de bases de données pleines de hachages (rapide).

De nos jours, de plus en plus de systèmes utilisent des algorithmes de stockage de mots de passe appropriés tels que Bcrypt, Scrypt ou Argon2. Voir: Comment [stocker] les mots de passe en toute sécurité? Ces algorithmes sont plus « vulnérable » aux tables arc-en-ciel: puisque chaque hachage est unique, même si les mots de passe sont égaux, les tables arc-en-ciel ne fonctionnent plus.

Cest pourquoi les tables arc-en-ciel sont impopulaires aujourdhui.Même si quelque chose de moderne comme Argon2 nest pas utilisé, les développeurs savent aujourdhui quils devraient au moins utiliser un sel. Cest déjà suffisant pour rendre une table arc-en-ciel inutile.

Fonctionnement

Création dune table

Imaginez que nous créons une table arc-en-ciel avec seulement deux chaînes, chacune de longueur 5. La table arc-en-ciel est pour la fonction de hachage fictive MD48, qui produit 48 bits (seulement 12 caractères hexadécimaux). Lors de la construction de la chaîne, nous voyons ceci:

Chain 0: 0=cfcd208495d5 => z=fbade9e36a3f => renjaj820=7668b2810262 => aL=8289e8a805d7 => ieioB=2958b80e4a3a => WLgOSj Chain 1: 1=c4ca4238a0b9 => ykI4oLkj=140eda4296ac => Dtp=1b59a00b7dbe => W=61e9c06ea9a8 => 6cBuqaha=d4d2e5280034 => 0uUoAD 

Nous commençons par 0 car cest la première chaîne (nous avons juste besoin dune valeur pour commencer). Lorsque nous hachons cela avec MD48, cela se transforme en cfcd208495d5. Maintenant, nous appliquons une fonction « réduire » qui formate essentiellement ce hachage en un mot de passe, et nous nous retrouvons avec « z ». Lorsque nous hachons à nouveau, nous obtenons fbade9e36a3f, puis le réduisons à nouveau et obtenons renjaj820 . Il y a encore quelques cycles, et le résultat final est WLgOSj.

Idem pour la deuxième chaîne. Nous commençons simplement avec une autre valeur et faisons la même chose. Cela se termine par 0uUoAD.

Notre table arc-en-ciel complète est maintenant la suivante:

WLgOSj => 0 0uUoAD => 1 

Cest tout ce que vous avez à stocker.

Recherche dun hachage

Disons que nous avons trouvé un hachage en ligne, 7668b2810262. Faisons-le craquer en utilisant notre table!

Looking for hash "7668b2810262", reduced to "aL". hashed=>reduced "aL" to ieioB hashed=>reduced "ieioB" to WLgOSj Found a match, "WLgOSj" is in our rainbow table: WLgOSj => 0 The chain starts with "0". Let"s walk that chain and look for the hash. hashed "0" to cfcd208495d5 hashed "z" to fbade9e36a3f hashed "renjaj820" to 7668b2810262 That hash matches! Found the password: renjaj820 

Pour jouer avec vous-même, les exemples ci-dessus ont été créés à laide de ce script Python: https://gist.github.com/lgommans/83cbb74a077742be3b31d33658f65adb

Propriétés de mise à léchelle

En bref:

• Des recherches rapides signifient des tables plus grandes, en supposant que la couverture reste la même.
• Une meilleure couverture signifie soit des recherches plus lentes, soit des tables plus grandes.
• Des tables plus petites signifient soit des recherches plus lentes, soit une couverture plus mauvaise.

Les sections suivantes supposent que le temps par hachage + réduction est de 1 µs et ne tiennent pas compte des collisions. Ce sont tous des nombres approximatifs, donnés à titre dexemples et non de valeurs exactes.

Heure de recherche

Si une opération de hachage + réduction prend une microseconde, générer une table avec un million de chaînes et 10 000 réductions par chaîne prendrait environ 3 heures:
chain_length × chain_count / reductions_per_second / seconds_per_hour
= 10 000 × 1 000 000 / 1 000 000 / 3600 = 2,8 heures.

Faire une recherche dans cette table prend en moyenne 10 millisecondes. En effet, nous devrons généralement passer par des chain_length/2 réductions avant de trouver quelle chaîne contient le hachage. Par exemple, il se peut que nous devions effectuer 3000 réductions sur un hachage avant de trouver une valeur qui se trouve dans le tableau. Ensuite, nous devons refaire cette chaîne depuis le début jusquà ce que nous trouvions la valeur correspondante. Si nous devions juste en faire 3000 pour le trouver dans notre tableau, alors nous devons faire 7000 réductions dès le début pour arriver au bon point de la chaîne. En gros, nous effectuons autant dopérations lors de la recherche que lors de la génération dune seule chaîne. Par conséquent, le temps de recherche est de 10 000 fois une microseconde, soit dix millisecondes (ou une centiseconde, si vous voulez).

Exigences de stockage

Lorsque vous voulez créer une table de recherche complète et rapide pour une fonction de hachage, même MD5, vous « auriez encore besoin de cent milliards de milliards de téraoctets de stockage. Cela » Ce nest pas très utile. Mais que se passe-t-il si nous voulons couvrir uniquement les mots de passe minuscules jusquà 10 caractères?

Si nous voulons passer au plus 30 secondes à chercher un hachage, et en supposant que nous avons besoin de 1 microseconde (un millionième de seconde) par hachage + réduire le cycle, alors nous pouvons avoir une longueur de chaîne de: 1 million × 30 = 30 millions. Il existe 26 ¹⁰ (ou 10 ¹⁴ ) mots de passe minuscules possibles de 10 caractères, et par chaîne nous couvrons 30 millions de valeurs. Cela nous laisse avec 4 millions de chaînes. Nous savons que chaque chaîne na quune valeur de début et de fin stockée, et que les valeurs sont de 10 caractères chacune. Donc, 2 × 10 × 4 million = 76 Mio de données.

La génération de la table en itérant tous les mots de passe à 10 caractères prend beaucoup de temps: 30 secondes par chaîne, multiplié par 4 millions de chaînes, cest environ 91 ans. Cependant, beaucoup de gens seraient intéressés par une telle table, donc en regroupant 1092 processeurs (= 91 × 12), cela ne prend que 1 mois. Cela montre à quel point une telle table peut être comparée à lespace de mot de passe quelle couvre: les recherches ne prennent que 30 secondes et vous ne devez stocker que 76 Mo de données.

Conclusion

Les tables arc-en-ciel peuvent être considéré comme un compromis temps-mémoire : on ne stocke qu’une petite partie de la table et la récupère grâce à un calcul supplémentaire au moment de la recherche. Cest en partie la raison pour laquelle les sels, ou plutôt, un bon algorithme de stockage de mots de passe comme Scrypt ou Argon2 sont importants pour protéger les mots de passe.Une table arc-en-ciel ne peut récupérer un mot de passe salé que si la table contient une entrée suffisamment grande pour contenir à la fois le sel et le mot de passe, ce qui serait extrêmement inefficace et irait à lencontre de lobjectif.

Notez quune chose similaire sapplique au cryptage: lorsque les gens crypter des fichiers avec un mot de passe, une table arc-en-ciel peut être construite pour déchiffrer les fichiers. Disons que le logiciel utilise AES et que le premier bloc du fichier doit être déchiffré en « passwordcorrect » en utilisant le mot de passe fourni par lutilisateur, puis une table arc-en-ciel utiliserait AES au lieu dune fonction de hachage.

Chaque fois que vous manipulez un mot de passe (un secret dont la force est inconnue, et surtout si lutilisateur peut le réutiliser), exécutez-le toujours via un algorithme de stockage de mot de passe (lent) approprié pour le rendre lent et unique à craquer.

Commentaires

• Bonne explication. Si jai bien compris, la puissance des tables arc-en-ciel réside dans une bonne fonction de réduction, non? Comment en trouver un bon? Et comment éviter les collisions pour tous les candidats à travers les chaînes?
• @ Kyu96 Bonnes questions! Je ne ‘ ne connais pas la réponse mais je serais intéressé si vous en trouviez une. Cette page traite de la question générale de savoir ce quest une table arc-en-ciel, pas de détails comme la conception dun algorithme. Vous devriez ouvrir une nouvelle question , mais ce site Web a pour objet de  » protéger les actifs contre les menaces numériques  » (iirc ). Je pense que ce serait sur le sujet de notre site sœur, crypto.stackexchange.com , qui concerne  » les mathématiques et les propriétés des systèmes cryptographiques, leur analyse ( » cryptanalysis « ) et les sujets subsidiaires qui composent généralement la cryptologie, comme le nombre aléatoire génération.  »