Zenk - Security

Outils d'utilisateurs

Outils du Site

Piste:
rainbow_table

Différences

Cette page vous donne les différences entre la révision choisie et la version actuelle de la page.

Lien vers cette vue

rainbow_table [2012/06/29 11:59]
Pheimors créée 		rainbow_table [2017/04/09 15:33] (Version actuelle)
Ligne 1: Ligne 1:
-====== Rainbow Table ====== 
- 
- 
 ===== Time-Memory Trade-Off ===== ===== Time-Memory Trade-Off =====
  
Ligne 9: Ligne 6:
 On donne le nombre de mots de passe total N. On donne le nombre de mots de passe total N.
  
-Pour chaque chaîne, on commence par un mot de passe de départ (P0). On calcul le hash de ce mot de passe H(P0)=C0.+Pour chaque chaîne, on commence par un mot de passe de départ (P0). On calcule le hash de ce mot de passe H(P0)=C0.
 On applique à ce hash une fonction dite de réduction pour générer un nouveau mot de passe à l'intérieur de l'espace de clef : R(C0) = P1. On applique à ce hash une fonction dite de réduction pour générer un nouveau mot de passe à l'intérieur de l'espace de clef : R(C0) = P1.
 On continue d'appliquer ce processus jusqu'à arriver à Pt-1. On continue d'appliquer ce processus jusqu'à arriver à Pt-1.
Ligne 24: Ligne 21:
  return gen_chain(start, R(H(next)), t-1, tmax)  return gen_chain(start, R(H(next)), t-1, tmax)
 </code> </code>
-En créant suffisament de ces chaines, on réussi idéalement à stocker la totalité des mots de passes de l'espace de clef dans un espace mémoire limité. +En créant suffisament de ces chaînes, on réussi idéalement à stocker la totalité des mots de passes de l'espace de clef dans un espace mémoire moindre. 
-Pour retrouver le mot de passe d'un hash h, on calcul R(h). +Pour retrouver le mot de passe d'un hash h, on calcule R(h). 
-Si le résultat est l'une de valeur de fin, on recalcule la totalité de la chaine en prenant la valeur de départ pour retrouver le mot de passe.+Si le résultat est l'une des valeurs de fin, on recalcule la totalité de la chaine en prenant la valeur de départ pour retrouver le mot de passe.
 Sinon, on continue de calculer R(H(R(h))), puis R(H(R(H(R(j))))) et ainsi de suite jusqu'à avoir t itérations. Sinon, on continue de calculer R(H(R(h))), puis R(H(R(H(R(j))))) et ainsi de suite jusqu'à avoir t itérations.
 Si rien n'a été trouvé au bout de t itérations, le mot de passe n'est pas présent dans la table. Si rien n'a été trouvé au bout de t itérations, le mot de passe n'est pas présent dans la table.
  
 ==== Exemple ==== ==== Exemple ====
-On crée une table de m=2 chaine de longueur t=4. +On crée une table de m=2 chaines de longueur t=4. 
-On part d'un premier mot de passe 'Zenk' dont le hash est H('Zenk')='dza45dza'. Le fonction de réduction R permet d'obtenir un nouveau mot de passe à partir du hash : R(H('Zenk')) = 'Roxxor'. On reprend le processus jusqu'à obtenir une chaine de longueur 4 :+On part d'un premier mot de passe 'Zenk' dont le hash est H('Zenk')='dza45dza'. Le fonction de réduction R permet d'obtenir un nouveau mot de passe à partir du hash : R(H('Zenk')) = 'Roxxor'. On reprend le processus jusqu'à obtenir une chaîne de longueur 4 :
 <code> <code>
  'Zenk' --H--> 'dza45dza' --R--> 'Roxxor' --H--> 'ujn7ez9f' --R--> 'reversing' --H--> 'g78eza94' --R--> 'foo'  'Zenk' --H--> 'dza45dza' --R--> 'Roxxor' --H--> 'ujn7ez9f' --R--> 'reversing' --H--> 'g78eza94' --R--> 'foo'
Ligne 57: Ligne 54:
 Et on retrouve le mot de passe. Et on retrouve le mot de passe.
  
-==== Limitations ====+===== Limitations =====
  
-Tout ça fonctionnerais magnifiquement bien dans le meilleur des mondes. +Tout ça fonctionne magnifiquement, mais hélas uniquement dans le meilleur des mondes : celui du modèle théorique. 
-Les fonctions de réductions ne sont pas parfaites, et il arrive que deux chaines fusionnent entre elle si la fonction de réduction utilisée retourne le même mot de passe pour deux hash différents. +En pratique, les fonctions de réductions ne sont pas parfaites et il arrive que deux chaines fusionnent entre elles si la fonction de réduction utilisée retourne le même mot de passe pour deux hash différents. 
-Le problème surviens lorsqu'on veut générer de grandes tables. +La probabilité de fusions augmente lorsque l'on veut générer de grandes tables. 
-Si un hash H1 et un autre H2 fournisse le même P2 une fois la fonction de réduction appliquée, la suite de la chaîne sera la même.+Si un hash H1 et un autre H2 fournissent le même P2 une fois la fonction de réduction appliquée, la suite de la chaîne sera la même.
 <code> <code>
  H1 --R-|-> P2 --H--> H2 --R--> ... ...  H1 --R-|-> P2 --H--> H2 --R--> ... ...
Ligne 74: Ligne 71:
  
 ===== Rainbow Table ===== ===== Rainbow Table =====
-Pour remédier à ce problème de fusion des chaines, Phillippe Oechslin à mise au point en 2003 la structure des Rainbow Table. +Pour remédier à ce problème de fusions de chaîne, Phillippe Oechslin à mis au point en 2003 la structure des Rainbow Table. 
-On n'appliquer plus une fonction de réduction unique, mais une fonction de réduction par colonnes de la table. Ainsi:+On n'applique plus une fonction de réduction unique, mais une fonction de réduction par colonnes de la table. Ainsi:
 <code> <code>
  P0 --H--> H0 --R0--> P1 --H--> H1 --R1--> ... ...  P0 --H--> H0 --R0--> P1 --H--> H1 --R1--> ... ...
 </code> </code>
-On retrouve le problème de fusion, mais uniquement si la fusion apparaît sur une même colonne de la table.+On retrouve le problème de fusions, mais uniquement si la fusion apparaît sur une même colonne de la table.
 Le risque de fusion est réduit de 1/t. Le risque de fusion est réduit de 1/t.
-En case de fusion sur des colonnes différentes, les fonctions de réduction ne seront pas les mêmes, et le mot de passe généré sera aussi différent.+En cas de fusion sur des colonnes différentes, les fonctions de réduction ne seront pas les mêmes, et le mot de passe généré sera aussi différent.
 La fusion n'a en fait pas lieu. La fusion n'a en fait pas lieu.
-Par exemple, une fusion éviter sur P02=P11 :+Par exemple, une fusion évitée sur P02=P11 :
 <code> <code>
  P00 --H--> H00 --R0--> P01 --H--> H01 --R1--> P02=P11 --H--> H02 --R2--> P03  P00 --H--> H00 --R0--> P01 --H--> H01 --R1--> P02=P11 --H--> H02 --R2--> P03
Ligne 89: Ligne 86:
 </code> </code>
 Les chaines sont en général d'une taille de l'ordre du millier d'éléments, il reste quand même des risques de fusions. Les chaines sont en général d'une taille de l'ordre du millier d'éléments, il reste quand même des risques de fusions.
-Sur 80 milliards de chaînes de longueur 4000-5000, on ne récupère que 35 millions de chaînes sans fusions.+Par exemple avec le logiciel rainbowcrack : sur 80 milliards de chaînes de longueur 4000-5000, on ne récupère que 35 millions de chaînes sans fusions.
 Il faut dans ce cas supprimer les chaînes posant problème. Il faut dans ce cas supprimer les chaînes posant problème.
-On résout une partie de ce problème en créant plusieurs tables : les chaines fusionnant sur une même table ne pose pas de problèmes si on les déplace.+On résout une partie de ce problème en créant plusieurs tables : les chaînes fusionnant sur une même table ne pose pas de problèmes si on déplace les chaînes fusionnant dans une nouvelle table.
  
  
Ligne 100: Ligne 97:
   * Les compromis temps-mémoire et leur utilisation pour casser les mots de passe Windows - Phillippe Oechslin - http://lasecwww.epfl.ch/~oechslin/publications/sstic04.pdf   * Les compromis temps-mémoire et leur utilisation pour casser les mots de passe Windows - Phillippe Oechslin - http://lasecwww.epfl.ch/~oechslin/publications/sstic04.pdf
   * Optimization of Time-Memory Trade-off cryptanalysis and its application to DES - Tsutomu Matsumoto and Koji Kusuda   * Optimization of Time-Memory Trade-off cryptanalysis and its application to DES - Tsutomu Matsumoto and Koji Kusuda
 +  * How rainbow tables works - http://kestas.kuliukas.com/RainbowTables/
  
rainbow_table.1340963972.txt.gz · Dernière modification: 2017/04/09 15:33 (modification externe)

Outils de la Page

Sauf mention contraire, le contenu de ce wiki est placé sous la licence suivante : CC Attribution-Share Alike 3.0 Unported
CC Attribution-Share Alike 3.0 Unported Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki