Paper 2013/591

Analysis of the Rainbow Tradeoff Algorithm Used in Practice

Jung Woo Kim, Jin Hong, and Kunsoo Park


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.

Available format(s)
Secret-key cryptography
Publication info
Preprint. MINOR revision.
cryptanalytic time memory tradeoffrainbow tradeoffexternal memory model
Contact author(s)
jinhong @ snu ac kr
2013-09-14: received
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.