International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: A Comparison of Cryptanalytic Tradeoff Algorithms

Jin Hong
Sunghwan Moon
Search ePrint
Search Google
Abstract: The three major time memory tradeoff algorithms are compared in this paper. Specifically, the Hellman tradeoff algorithm, the distinguished point tradeoff method, and the rainbow table method, in their non-perfect table versions, are considered. We show that, under parameters that are typically considered in theoretic discussions of the tradeoff algorithms, Hellman and distinguished point tradeoffs perform very close to each other and 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 presented in this paper takes the effects of false alarms into account and also fully considers techniques for reducing storage, such as the ending point truncation method and index files.
  title={A Comparison of Cryptanalytic Tradeoff Algorithms},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / time memory tradeoff, Hellman, distinguished point, rainbow table, random function},
  note={ 14819 received 2 Apr 2010, last revised 29 Jul 2010},
  author={Jin Hong and Sunghwan Moon},