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)
- 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
-
CC BY