International Association
for Cryptologic Research

Analyses of three major time memory tradeoff algorithms were presented by a recent paper in such a way that facilitates comparisons of the algorithm performances at arbitrary choices of the algorithm parameters. The algorithms considered there were the classical Hellman tradeoff and the non-perfect table versions of the distinguished point method and the rainbow table method. This paper adds the perfect table versions of the distinguished point method and the rainbow table method to the list, so that all the major tradeoff algorithms may now be compared against each other.

The algorithm performance information provided by this and the preceding paper is aimed at making practical comparisons possible. Comparisons that take both the cost of pre-computation and the efficiency of the online phase into account, at parameters that achieve a common success rate, can now be carried out with ease. Comparisons can be based on the expected execution complexities rather than the worst case complexities, and details such as the effects of false alarms and various storage optimization techniques need no longer be ignored.

A large portion of this paper is allocated to accurately analyzing the execution behavior of the perfect table distinguished point method. In particular, we obtain a closed-form formula for the average length of chains associated with a perfect distinguished point table.