Perfect Rainbow Tradeoff with Checkpoints Revisited

Jin Hong

PLOS ONE, 2016, vol. 11, issue 11, 1-18

Abstract: The rainbow tradeoff is an algorithm for inverting one-way functions that is widely used in practice to recover passwords from unsalted password hashes. An auxiliary technique referred to as checkpoints can be applied to the rainbow tradeoff to reduce the time taken for these inversions. Working out a rigorous theory that can explain and predict the effects of this technique involves delicate manipulations of the random function and is thus a challenging task. In this work, we compare three existing theoretical analyses of the checkpoint technique. We first demonstrate that the claims made by the three works are incompatible with each other. We then carry out experiments designed to highlight these incompatibilities, obtaining experimental evidences that show just one of the three analyses to be correct. Finally, we discuss the obscure theoretical errors made by the two inadequate analyses.

Date: 2016
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0166404 (text/html)
https://journals.plos.org/plosone/article/file?id= ... 66404&type=printable (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:plo:pone00:0166404

DOI: 10.1371/journal.pone.0166404

Access Statistics for this article

More articles in PLOS ONE from Public Library of Science
Bibliographic data for series maintained by plosone ().