Analysis of the Rainbow Tradeoff Algorithm Used in Practice

Jung Woo Kim; Jin Hong; Kunsoo Park

Paper 2013/591

Analysis of the Rainbow Tradeoff Algorithm Used in Practice

Jung Woo Kim, 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.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: cryptanalytic time memory tradeoff rainbow tradeoff external memory model
Contact author(s): jinhong @ snu ac kr
History: 2013-09-14: received
Short URL: https://ia.cr/2013/591
License: CC BY

BibTeX

@misc{cryptoeprint:2013/591,
      author = {Jung Woo Kim and Jin Hong and Kunsoo Park},
      title = {Analysis of the Rainbow Tradeoff Algorithm Used in Practice},
      howpublished = {Cryptology {ePrint} Archive, Paper 2013/591},
      year = {2013},
      url = {https://eprint.iacr.org/2013/591}
}