« previous 1 2 3 4 5 next »

Trooping the colours

A further improvement to Hellman's technique, which far from increasing the number of collisions almost completely prevents them, was proposed by Philippe Oechslin in 2003. Like other TMTO techniques, it begins by using a random key to encrypt a previously chosen message, but a pass-dependent function is used to prepare the result for the next pass. With other techniques, a collision occurs if a previously calculated value emerges, following the encryption pass. The additional pass-dependent function, however, ensures that the key derived for the next pass is different. Collisions only occur if the same output emerges in two chains during the same pass.

The pass-dependent function can be quite simple, for example, "add 1 after the first pass, add 2 after the second pass", and so on. More complicated pass-dependent functions matched to the cryptographic characteristics of the encryption function yield better results, in that collisions are fewer and there is improved coverage of all possible keys. To use a metaphor, we can picture the data trooping through a rainbow of functions, first the red one, then orange, yellow, green etc. This has earned the technique its "rainbow table" name.

To avoid collisions with the rainbow table, the trick is to modify the pass-dependent function in accordance with the step number.

To find a key using a rainbow table, an attacker has to restore several sections of a chain, because the pass-dependent function means that the point at which computation begins is no longer insignificant. The encrypted message of the targeted system first goes through the last pass – its pass-dependent function as well as the encryption. If the rainbow table doesn't yield a hit for the end value, the message goes through the next to last pass and then the last one, then starts again from the third last pass, and so on until an end value turns up in the table. Statistically, half of the key is found on average as soon as half the chain length has been reached.

Since the first sub-chains to be computed are comparatively short, the search only recomputes an average of half as many chain links as do the other TMTO techniques, speeding up the search for the key by a factor of anything up to two. This speed gain only occurs, however, if the desired key is actually present in the table. Otherwise, all the sub-chains have to be generated in order to determine that the desired element is missing, and this involves considerably more effort than do the other techniques.

So there is no clear winner between Oechslin's rainbow tables and Rivest's distinguished points: one or the other method is faster, depending on the characteristics of the encryption function. Rainbow tables require substantially more disk accesses, while distinguished points cause more collisions because the number of possible end points is smaller.

Next: Success stories

« previous 1 2 3 4 5 next »