Paper 2006/127

A New Cryptanalytic Time/Memory/Data Trade-off Algorithm

Sourav Mukhopadhyay and Palash Sarkar

Abstract

In 1980, Hellman introduced a time/memory trade-off (TMTO) algorithm satisfying the TMTO curve $TM^2=N^2$, where $T$ is the online time, $M$ is the memory and $N$ is the size of the search space. Later work by Biryukov-Shamir incorporated multiple data to obtain the curve $TM^2D^2=N^2$, where $D$ is the number of data points. In this paper, we describe a new table structure obtained by combining Hellman's structure with a structure proposed by Oechslin. Using the new table structure, we design a new multiple data TMTO algorithm both with and without the DP method. The TMTO curve for the new algorithm is obtained to be $T^3M^7D^8=N^7$. This curve is based on a conjecture on the number of distinct points covered by the new table. Support for the conjecture has been obtained through some emperical observations. For $D>N^{1/4}$, we show that the trade-offs obtained by our method are better than the trade-offs obtained by the BS method.

Metadata
Available format(s)
PDF PS
Publication info
Published elsewhere. Unknown where it was published
Keywords
one-way functiontimememory trade-offcryptanalysis
Contact author(s)
msourav @ gmail com
History
2006-04-03: received
Short URL
https://ia.cr/2006/127
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/127,
      author = {Sourav Mukhopadhyay and Palash Sarkar},
      title = {A New Cryptanalytic Time/Memory/Data Trade-off Algorithm},
      howpublished = {Cryptology ePrint Archive, Paper 2006/127},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/127}},
      url = {https://eprint.iacr.org/2006/127}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.