Cryptology ePrint Archive: Report 2012/540

A Comparison of Perfect Table Cryptanalytic Tradeoff Algorithms

Ga Won Lee and Jin Hong

Abstract: The performances of three major time memory tradeoff algorithms were compared by a recent paper. 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.

Even though there are existing claims as to superiority of one tradeoff algorithm over another algorithm, the algorithm performance comparisons provided by the current and preceding papers are of more practical value. 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.

Category / Keywords: secret-key cryptography / time memory tradeoff, distinguished point, rainbow table, perfect table, algorithm complexity

Date: received 13 Sep 2012, last revised 1 Apr 2014

Contact author: jinhong at snu ac kr

Available format(s): PDF | BibTeX Citation

Note: WARNING: The authors have become aware that Prop-9 is incorrect and are currently working to correct this.

Version: 20140401:074704 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]