tables arc-en-Wikipédia entrée

Question

Wikipedia page for rainbow tables dit:

« cette utilisation des fonctions de réduction multiples double approximativement la vitesse de lookups. »

En supposant que la position « moyenne » dans la chaîne, nous prenons un hachage et le lancer à travers une chaîne 9 itération ...

La table d'origine passe par 4 réductions et 4 hash et trouve la fin de la chaîne, puis cherche encore 5 hachages 5 réductions ... total 9 hachages 9 réductions

La table arc-en-ciel l'exécute par les calculs Rk-1, Rk-2, Rk-3, et Rk-4 pour trouver le fin de la chaîne, puis 5 autres hachages 5 réductions pour obtenir le texte en clair: total 15 hachages 15 réductions ...

Qu'est-ce qui me manque ici? Par mes maths, la seule fois où une recherche arc-en-ciel est la même vitesse qu'une table normale est quand le hachage se trouve juste à la fin de la chaîne ... En fait, la RT devrait être progressivement plus lente vers le début hachage est ...

une chaîne de 5 km avec le hachage au début doit être d'environ 2500 fois plus lent avec des tables arc-en-que avec des tables de hachage normales ...

Suis-je manque quelque chose ou avez-Wikipedia fait une erreur? (Le paper referenced on that page (Page 13) aurait aussi tort, donc je me penche vers le premier)

Answer 1

Le but des tables arc-en-ciel n'est pas nécessairement d'être plus rapide mais de réduire l'espace. Les tables arc-en-ciel font le commerce de la vitesse pour la taille.

Le stockage des hachages pour tous les mots de passe à 10 chiffres possibles serait par exemple prohibitif en termes d'espace disque. Aussi, vous devez considérer que puisque l'espace du dictionnaire est si grand, il nécessitera une pagination significative (opération très lente).

Les tables arc-en-ciel consomment davantage de ressources processeur, mais elles sont beaucoup plus petites et requièrent moins d'espace disque, ce qui permet d'avoir plus d'espace mémoire en même temps dans la mémoire. Gardez à l'esprit que cela signifie dans le monde réel des performances potentielles plus élevées sur les grands espaces du dictionnaire en raison d'une moindre pagination (les lectures de disque sont extrêmement lentes).

Voici un exemple mieux illustré: http://kestas.kuliukas.com/RainbowTables/

Bien sûr, cela est tout académique. Les tables arc-en-ciel n'ont aucune valeur contre les systèmes de sécurité bien conçus. 1) Utiliser un algorithme cryptographiquement sécurisé (pas de «lancer le vôtre») 2) Utiliser une fonction de dérivation de clé (avec des milliers d'itérations) pour ralentir le débit de hachage des attaquants. 3) Utiliser un gros sel aléatoire (de 32 à 64 bits). Les tables arc-en-ciel ne peuvent plus être précalculées, et ce calcul ne peut être utilisé pour aucun autre système (sauf si elles partagent le même sel.) 4) Si possible, utilisez du sel différent par enregistrement, ce qui rend la table arc-en-ciel totalement invalide.

Answer 2

Toutes les réponses sont dans l'article original. Tout d'abord, vous devez voir que vous devez comparer une seule table arc-en-ciel avec t tables classiques, t étant le nombre d'éléments dans une chaîne. En effet, chaque colonne de la table arc-en-ciel agit comme une seule table classique (par exemple si vous avez des éléments identiques dans une colonne d'arc-en-ciel, vous aurez une fusion, si vous avez deux éléments identiques dans une table classique fusionner). Ensuite, vous verrez que pour rechercher dans les tableaux classiques, vous auriez besoin de t^2 opérations si vous devez parcourir toutes les tables (t tables avec des chaînes de longueur t).Si vous recherchez dans la table arc-en-ciel simple, vous aurez besoin de 1 + 2 + 3 + ... + t opérations qui est égale à t^2/2. Donc, dans le pire des cas, lorsque vous ne trouvez pas le mot de passe, vous serez deux fois plus rapide. Maintenant, si le mot de passe s'affiche en moyenne après avoir parcouru la moitié des tables ou des colonnes, il sera 4 fois plus rapide. Si vous voulez une forte probabilité de succès (par exemple 99%) alors en moyenne un mot de passe apparaîtrait déjà après 10% de la table, rendant les tables arc-en-ciel 20 fois plus rapides.