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 calcul 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 chaines, on réussi idéalement à stocker la totalité des mots de passes de l'espace de clef dans un espace mémoire limité. Pour retrouver le mot de passe d'un hash h, on calcul 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. 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 chaine 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 :

	'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 fonctionnerais magnifiquement bien dans le meilleur des mondes. 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. Le problème surviens lorsqu'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.

	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 fusion des chaines, Phillippe Oechslin à mise 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:

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

On retrouve le problème de fusion, 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 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. La fusion n'a en fait pas lieu. Par exemple, une fusion éviter 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. 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 chaines fusionnant sur une même table ne pose pas de problèmes si on les déplace.

• 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