Paper 2010/176

A Comparison of Cryptanalytic Tradeoff Algorithms

Jin Hong and Sunghwan Moon

Abstract

Three time memory tradeoff algorithms are compared in this paper. Specifically, the classical tradeoff algorithm by Hellman, the distinguished point tradeoff method, and the rainbow table method, in their non-perfect table versions, are treated. We show that, under parameters and assumptions that are typically considered in theoretic discussions of the tradeoff algorithms, Hellman and distinguished point tradeoffs perform very close to each other and that the rainbow table method performs somewhat better than the other two algorithms. Our method of comparison can easily be applied to other situations, where the conclusions could be different. The analysis of tradeoff efficiency presented in this paper does not ignore the effects of false alarms and also covers techniques for reducing storage, such as ending point truncations and index tables. Our comparison of algorithms takes the success probabilities and pre-computation efforts fully into account.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A minor revision of an IACR publication in JOC 2013
DOI
10.1007/s00145-012-9128-3
Keywords
time memory tradeoffHellmandistinguished pointrainbow tablerandom function
Contact author(s)
jinhong @ snu ac kr
History
2013-09-27: last of 5 revisions
2010-04-04: received
See all versions
Short URL
https://ia.cr/2010/176
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/176,
      author = {Jin Hong and Sunghwan Moon},
      title = {A Comparison of Cryptanalytic Tradeoff Algorithms},
      howpublished = {Cryptology ePrint Archive, Paper 2010/176},
      year = {2010},
      doi = {10.1007/s00145-012-9128-3},
      note = {\url{https://eprint.iacr.org/2010/176}},
      url = {https://eprint.iacr.org/2010/176}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.