On the memory hardness of data independent password hashing functions
Alwen, Joel F
Gazi, Peter
Kamath Hosdurg, Chethan
Klein, Karen
Osang, Georg F
Pietrzak, Krzysztof Z
Reyzin, Lenoid
Rolinek, Michal
Rybar, Michal
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.
ACM
2018
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
http://purl.org/coar/resource_type/c_5794
https://research-explorer.ista.ac.at/record/193
Alwen JF, Gazi P, Kamath Hosdurg C, et al. On the memory hardness of data independent password hashing functions. In: <i>Proceedings of the 2018 on Asia Conference on Computer and Communication Security</i>. ACM; 2018:51-65. doi:<a href="https://doi.org/10.1145/3196494.3196534">10.1145/3196494.3196534</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1145/3196494.3196534
info:eu-repo/semantics/altIdentifier/wos/000516620100005
info:eu-repo/grantAgreement/EC/FP7/616160
info:eu-repo/grantAgreement/EC/H2020/682815
info:eu-repo/semantics/openAccess