Paper 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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown status
Keywords
time memory tradeoffdistinguished pointrainbow tableperfect tablealgorithm complexity
Contact author(s)
jinhong @ snu ac kr
History
2014-06-22: last of 4 revisions
2012-09-20: received
See all versions
Short URL
https://ia.cr/2012/540
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/540,
      author = {Ga Won Lee and Jin Hong},
      title = {A Comparison of Perfect Table Cryptanalytic Tradeoff Algorithms},
      howpublished = {Cryptology ePrint Archive, Paper 2012/540},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/540}},
      url = {https://eprint.iacr.org/2012/540}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.