Paper Info
Title
On the Memory-Hardness of Data-Independent Password-Hashing Functions.
Abstract
We show attacks on five data-independent memory-hard functions (iMHF) that were submitted to the password hashing competition (PHC). Informally, an MHF is a function which cannot be evaluated on dedicated hardware, like ASICs, at significantly lower hardware and/or energy 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 measure for the hardware cost of evaluating the iMHF on an ASIC. Ideally, one would like the complexity of a DAG underlying an iMHF to be as close to quadratic in the number of nodes of the graph as possible. Instead, we show that (the DAGs underlying) the following iMHFs are far from this bound: Rig.v2,TwoCats and Gambit each having an exponent no more than 1.75. Moreover, we show that the complexity of the iMHF modes of the PHC finalists Pomelo and Lyra2 have exponents at most 1.83 and 1.67 respectively. To show this we investigate a combinatorial property of each underlying DAG (called its depth-robustness. By establishing upper bounds on this property we are then able to apply the general technique of [Alwen-Block'16] for analyzing the hardware costs of an iMHF.
Year
DOI
Venue
2018
10.1145/3196494.3196534
AsiaCCS
DocType
ISBN
Citations 
Conference
978-1-4503-5576-6
0
PageRank 
References 
Authors
0.34
14
9
Name
Order
Citations
PageRank
Joel Alwen151622.21
Peter Gazi26510.14
Chethan Kamath3235.50
Karen Klein402.37
Georg Osang522.14
Krzysztof Pietrzak6151372.60
Leonid Reyzin72640132.67
Michal Rolinek8225.39
Michal Rybár961.12