You are looking at a specific version 20160822:100323 of this paper. See the latest version.

Paper 2016/783

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

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

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
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.