The Cost of False Alarms in Hellman and Rainbow Tradeoffs

Jin Hong

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 tradeoff Hellman rainbow table checkpoint
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: 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},
      url = {https://eprint.iacr.org/2008/362}
}