Zenk - Security

La première idée pour ce compromis temps-mémoire a été publiée par M. E. Hermann en 1980 et améliorée par Rivest (un des Mr RSA) en 1982. Le principe est de calculer un certain nombre m de chaînes de hash de longueur t (longueur de la chaîne, pas du hash). On doit se fixer un espace de clef précis (key space en anglais). Par exemple, [[:digit:]]{1,5}. 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 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 continue d'appliquer ce processus jusqu'à arriver à Pt-1.

P0 --H--> C1 --R--> P1 --H--> C1 --R--> ... ... Ct-2 --R--> Pt-1

Et on stock le mot de passe de départ et celui de fin. Autrement dit :

	def gen_chain(start, next, t, tmax):
		if t == tmax:
			return start, R(next)
		return gen_chain(start, R(H(next)), t-1, tmax)

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 calcule R(h). 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. Si rien n'a été trouvé au bout de t itérations, le mot de passe n'est pas présent dans la table.

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 chaîne de longueur 4 :

	'Zenk' --H--> 'dza45dza' --R--> 'Roxxor' --H--> 'ujn7ez9f' --R--> 'reversing' --H--> 'g78eza94' --R--> 'foo'

Et on calcul d'autres chaînes de la même manière, à partir d'un nouveau mot de passe de départ :

	'Security' --H--> 'kdkd855d' --R--> '1337' --H--> '1c8eza5s' --R--> 'P0ney' --H--> '8d5dz5ce' --R--> 'CTF'

La table contiendra au final :

	Zenk foo
	Security CTF

On veut maintenant cracker le hash 'ujn7ez9f'.

R('ujn7ez9f') = 'reversing'

'reversing' n'est pas dans la table. On continu

R(H(R('ujn7ez9f'))) = 'foo'

'foo' est dans la table. On reconstruit la chaine à partir de 'Zenk' :

'Zenk' --H--> 'dza45dza' --R--> 'Roxxor' --H--> 'ujn7ez9f' --R--> 'reversing' --H--> 'g78eza94' --R--> 'foo'
                                'Roxxor' <----- 'ujn7ez9f' --R--> 'reversing' --H--> 'g78eza94' --R--> 'foo'

Et on retrouve le mot de passe.

Tout ça fonctionne magnifiquement, mais hélas uniquement dans le meilleur des mondes : celui du modèle théorique. 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. La probabilité de fusions augmente lorsque l'on veut générer de grandes tables. 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.

	H1 --R-|-> P2 --H--> H2 --R--> ... ...
	H2 --R-|

Ces fusions peuvent aussi apparaître sur différentes colonnes :

	P00 --H--> H00 --R0--> P01 --H--> H01 --R1--> P02=P11 --H--> H02=H11 --R2--> P03=P12 --H--> ... ...
	P10 --H--> H10 --R0--> P11=P02 --H--> H11=H02 --R1--> P12=P03 --H--> ... ...

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'applique plus une fonction de réduction unique, mais une fonction de réduction par colonnes de la table. Ainsi:

	P0 --H--> H0 --R0--> P1 --H--> H1 --R1--> ... ...

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. 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. Par exemple, une fusion évitée sur P02=P11 :

	P00 --H--> H00 --R0--> P01 --H--> H01 --R1--> P02=P11 --H--> H02 --R2--> P03
	P10 --H--> H10 --R0--> P11=P02 --H--> H11 --R1--> P12 --H--> H12 --R2--> P13

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

• A cryptanalitic Time-Memory trade-Off _ M. E. Hellman
• Making a Faster Cryptanalytic Time-memory Trade-Off - Phillippe Oechslin
• 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
• How rainbow tables works - http://kestas.kuliukas.com/RainbowTables/