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 in 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 the superiority of one tradeoff algorithm over another algorithm, the algorithm performance comparisons provided by the current work and the recent preceding paper 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 significant 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 22 Jun 2014
Contact author: jinhong at snu ac kr
Available format(s): PDF | BibTeX Citation
Version: 20140622:150618 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]