Cryptology ePrint Archive: Report 2013/591

Analysis of the Rainbow Tradeoff Algorithm Used in Practice

Jung Woo Kim and Jin Hong and Kunsoo Park

Abstract: Cryptanalytic time memory tradeoff is a tool for inverting one-way functions, and the rainbow table method, the best-known tradeoff algorithm, is widely used to recover passwords. Even though extensive research has been performed on the rainbow tradeoff, the algorithm actually used in practice differs from the well-studied original algorithm. This work provides a full analysis of the rainbow tradeoff algorithm that is used in practice. Unlike existing works on the rainbow tradeoff, the analysis is done in the external memory model, so that the practically important issue of table loading time is taken into account. As a result, we are able to provide tradeoff parameters that optimize the wall-clock time.

Category / Keywords: secret-key cryptography / cryptanalytic time memory tradeoff, rainbow tradeoff, external memory model

Date: received 12 Sep 2013

Contact author: jinhong at snu ac kr

Available format(s): PDF | BibTeX Citation

Version: 20130914:224226 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]