Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / time memory tradeoff, Hellman, rainbow table, checkpoint

Date: received 21 Aug 2008, last revised 25 Feb 2009

Contact author: jinhong at snu ac kr

Available format(s): PDF | BibTeX Citation

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

Version: 20090225:095315 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]