Paper 2008/362

The Cost of False Alarms in Hellman and Rainbow Tradeoffs

Jin Hong

Abstract

Cryptanalytic time memory tradeoff algorithms are generic one-way function inversion techniques that utilize pre-computation. Even though the online time complexity is known up to a small multiplicative factor for any tradeoff algorithm, false alarms pose a major obstacle in its accurate assessment. In this work, we study the expected pre-image size for an iteration of functions and use the result to analyze the cost incurred by false alarms. We are able to present the expected online time complexities for the Hellman tradeoff and the rainbow table method in a manner that takes false alarms into account. We also analyze the effects of the checkpoint method in reducing false alarm costs. The ability to accurately compute the online time complexities will allow one to choose their tradeoff parameters more optimally, before starting the expensive pre-computation process.

Note: The current version extends the theory of the pervious version so that the analysis now closely fits experiments even for the checkpoint case.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
time memory tradeoffHellmanrainbow tablecheckpoint
Contact author(s)
jinhong @ snu ac kr
History
2009-02-25: revised
2008-08-27: received
See all versions
Short URL
https://ia.cr/2008/362
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/362,
      author = {Jin Hong},
      title = {The Cost of False Alarms in Hellman and Rainbow Tradeoffs},
      howpublished = {Cryptology ePrint Archive, Paper 2008/362},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/362}},
      url = {https://eprint.iacr.org/2008/362}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.