Comparison of Cryptanalytic Time Memory Tradeoff Algorithms with Focus on Some Rainbow Variants

Abstract

Cryptanalytic time memory tradeoff algorithms are tools for inverting one-way functions, and they are used to recover passwords from unsalted password hashes. There are many publicly known tradeoff algorithms, and the rainbow tradeoff algorithm, which is widely believed to be the best tradeoff algorithm, at least among implementers, has been the most popular method.

In this thesis, we provide accurate complexity analyses of the thick rainbow tradeoff algorithm and the non-perfect and perfect table fuzzy rainbow tradeoff algorithms. These are algorithms that have not yet received much attention. Our analyses show that, when the pre-computation cost and the online execution efficiency are both taken into consideration, the perfect table fuzzy rainbow tradeoff can be seen as performing the best among the three algorithms considered and actually even better than the original rainbow tradeoff.

The computational complexities for some time memory data tradeoff methods are also analyzed. The multi-target tradeoffs that we cover are the classical Hellman, distinguished point, and fuzzy rainbow methods, both in their non-perfect and perfect table versions for the latter two methods. We find that their execution complexities are no different from the complexities of the corresponding single-target algorithms executed under certain matching parameters. As in the single-target case, we conclude that the perfect table fuzzy rainbow tradeoff algorithm is the most preferable among the multi-target tradeoff algorithms we have considered.