Cryptology ePrint Archive: Report 2005/090

Rediscovery of Time Memory Tradeoffs

Jin Hong and Palash Sarkar

Abstract: Some of the existing time memory tradeoff attacks (TMTO) on specific systems can be reinterpreted as methods for inverting general oneway functions. We apply these methods back to specific systems in ways not considered before. This provides the following startling results.

No streamcipher can provide security equal to its key length; some important blockcipher modes of operations are vulnerable to TMTO; and no hash function can provide preimage resistance equal to its digest length.

Category / Keywords: foundations / time memory tradeoff

Publication Info: Presented at Asiacrypt 2005 (LNCS 3788, pp. 353-372)

Date: received 22 Mar 2005, last revised 31 Jul 2008

Contact author: jinhong at snu ac kr

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20080801:055124 (All versions of this report)

Short URL: ia.cr/2005/090

Discussion forum: Show discussion | Start new discussion