Paper 2008/054

Variants of the Distinguished Point Method for Cryptanalytic Time Memory Trade-offs (Full version)

Jin Hong, Kyung Chul Jeong, Eun Young Kwon, In-Sok Lee, and Daegun Ma

Abstract

The time memory trade-off (TMTO) algorithm, first introduced by Hellman, is a method for quickly inverting a one-way function, using pre-computed tables. The distinguished point method (DP) is a technique that reduces the number of table lookups performed by Hellman's algorithm. In this paper we propose a new variant of the DP technique, named variable DP (VDP), having properties very different from DP. It has an effect on the amount of memory required to store the pre-computed tables. We also show how to combine variable chain length techniques like DP and VDP with a more recent trade-off algorithm called the rainbow table method.

Metadata
Available format(s)
PDF PS
Category
Applications
Publication info
Published elsewhere. The short version of this paper will appear in the proceedings of ISPEC 2008.
Keywords
time memory trade-offHellman trade-offdistinguished pointsrainbow table
Contact author(s)
jeongkc @ math snu ac kr
History
2008-02-15: last of 3 revisions
2008-02-03: received
See all versions
Short URL
https://ia.cr/2008/054
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/054,
      author = {Jin Hong and Kyung Chul Jeong and Eun Young Kwon and In-Sok Lee and Daegun Ma},
      title = {Variants of the Distinguished Point Method for Cryptanalytic Time Memory Trade-offs (Full version)},
      howpublished = {Cryptology ePrint Archive, Paper 2008/054},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/054}},
      url = {https://eprint.iacr.org/2008/054}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.