Paper 2015/227

Tradeoff Cryptanalysis of Memory-Hard Functions

Alex Biryukov and Dmitry Khovratovich

Abstract

We explore time-memory and other tradeoffs for memory-hard functions, which are supposed to impose significant computational and time penalties if less memory is used than intended. We analyze three finalists of the Password Hashing Competition: Catena, which was presented at Asiacrypt 2014, \textsf{yescrypt} and Lyra2. We demonstrate that Catena's proof of tradeoff resilience is flawed, and attack it with a novel \emph{precomputation tradeoff}. We show that using $M^{4/5}$ memory instead of $M$ we have no time penalties and reduce the AT cost by the factor of 25. We further generalize our method for a wide class of schemes with predictable memory access. For a wide class of data-dependent schemes, which addresses memory unpredictably, we develop a novel \emph{ranking tradeoff} and show how to decrease the time-memory and the time-area product by significant factors. We then apply our method to yescrypt and Lyra2 also exploiting the iterative structure of their internal compression functions. The designers confirmed our attacks and responded by adding a new mode for Catena and tweaking Lyra2.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in ASIACRYPT 2015
Keywords
password hashingmemory-hardCatenatradeoffcryptocurrencyproof-of-work
Contact author(s)
alex biryukov @ uni lu
khovratovich @ gmail com
History
2015-09-28: revised
2015-03-11: received
See all versions
Short URL
https://ia.cr/2015/227
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/227,
      author = {Alex Biryukov and Dmitry Khovratovich},
      title = {Tradeoff Cryptanalysis of Memory-Hard Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2015/227},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/227}},
      url = {https://eprint.iacr.org/2015/227}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.