Paper 2016/783

On the Memory-Hardness of Data-Independent Password-Hashing Functions

Joël Alwen, Peter Gaži, Chethan Kamath, Karen Klein, Georg Osang, Krzysztof Pietrzak, Leonid Reyzin, Michal Rolínek, and Michal Rybár

Abstract

We show attacks on five data-independent memory-hard functions (iMHF) that were submitted to the password hashing competition. Informally, an MHF is a function which cannot be evaluated on dedicated hardware, like ASICs, at significantly lower energy and/or hardware cost than evaluating a single instance on a standard single-core architecture. Data-independent means the memory access pattern of the function is independent of the input; this makes iMHFs harder to construct than data-dependent ones, but the latter can be attacked by various side-channel attacks. Following [Alwen-Blocki'16], we capture the evaluation of an iMHF as a directed acyclic graph (DAG). The cumulative parallel pebbling complexity of this DAG is a good measure for the cost of evaluating the iMHF on an ASIC. If n denotes the number of nodes of a DAG (or equivalently, the number of operations --- typically hash function calls --- of the underlying iMHF), its pebbling complexity must be close to n^2 for the iMHF to be memory-hard. We show that the following iMHFs are far from this bound: Rig.v2, TwoCats and Gambit can be attacked with complexity O(n^{1.75}); the data-independent phase of Pomelo (a finalist of the password hashing competition) and Lyra2 (also a finalist) can be attacked with complexity O(n^{1.83}) and O(n^{1.67}), respectively. For our attacks we use and extend the technique developed by [Alwen-Blocki'16], who show that the pebbling complexity of a DAG can be upper bounded in terms of its depth-robustness.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
password hashingmemory hardness
Contact author(s)
peter gazi @ ist ac at
History
2016-08-22: revised
2016-08-18: received
See all versions
Short URL
https://ia.cr/2016/783
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/783,
      author = {Joël Alwen and Peter Gaži and Chethan Kamath and Karen Klein and Georg Osang and Krzysztof Pietrzak and Leonid Reyzin and Michal Rolínek and Michal Rybár},
      title = {On the Memory-Hardness of Data-Independent Password-Hashing Functions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2016/783},
      year = {2016},
      url = {https://eprint.iacr.org/2016/783}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.