Cryptology ePrint Archive: Report 2011/393

Analysis and Improvement of Thing's Time-Memory Trade-Off Attack

Zhenqi Li, Dongdai Lin and Wenhao Wang

Abstract: Cryptanalytic time memory trade-off is a probabilistic algorithm for inverting a generic one-way function. Since its first introduction by Hellman, many variants and their analysis results have appeared. Thing gave a new time-memory trade-off method in 2009. His new method has higher success probability and lower memory requirements, compared with Oechslin's rainbow table, but its drawback is obvious and make it to be an impractical method. In this paper, we analyze and improve Thing's method and propose a new method. We compare the success probability, memory requirements and analysis time between our method and Thing's method. Results show that our new method is better than Thing's method and fix its innate drawback.

Category / Keywords: secret-key cryptography / time memory tradeoff, rainbow attack.

Date: received 20 Jul 2011, withdrawn 9 Aug 2011

Contact author: lizhenqi at is iscas ac cn

Available format(s): (-- withdrawn --)

Version: 20110810:023913 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]