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.
Michal Rolínek was supported by the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement no 616160. The work was done while Peter Gaži was at IST Austria. All other authors from IST Austria (including Peter Gaži) were supported by the European Research Council consolidator grant (682815-TOCNeT). Leonid Reyzin was supported in part by IST Austria and by US NSF grants 1012910, 1012798, and 1422965; this research was performed while he was visiting IST Austria.
51 - 65
ASIACCS: Asia Conference on Computer and Communications Security
Incheon, Republic of Korea
2018-06-04 – 2018-06-08
Alwen JF, Gazi P, Kamath Hosdurg C, et al. On the memory hardness of data independent password hashing functions. In: Association for Computing Machinery, Inc; 2018. doi:10.1145/3196494.3196534
Alwen, J. F., Gazi, P., Kamath Hosdurg, C., Klein, K., Osang, G. F., Pietrzak, K. Z., … Rybar, M. (2018). On the memory hardness of data independent password hashing functions. Presented at the ASIACCS: Asia Conference on Computer and Communications Security , Incheon, Republic of Korea: Association for Computing Machinery, Inc. https://doi.org/10.1145/3196494.3196534
Alwen, Joel F, Peter Gazi, Chethan Kamath Hosdurg, Karen Klein, Georg F Osang, Krzysztof Z Pietrzak, Lenoid Reyzin, Michal Rolinek, and Michal Rybar. “On the Memory Hardness of Data Independent Password Hashing Functions.” Association for Computing Machinery, Inc, 2018. https://doi.org/10.1145/3196494.3196534.
J. F. Alwen et al., “On the memory hardness of data independent password hashing functions,” presented at the ASIACCS: Asia Conference on Computer and Communications Security , Incheon, Republic of Korea, 2018.
Alwen JF, Gazi P, Kamath Hosdurg C, Klein K, Osang GF, Pietrzak KZ, Reyzin L, Rolinek M, Rybar M. 2018. On the memory hardness of data independent password hashing functions. ASIACCS: Asia Conference on Computer and Communications Security
Alwen, Joel F., et al. On the Memory Hardness of Data Independent Password Hashing Functions. Association for Computing Machinery, Inc, 2018, doi:10.1145/3196494.3196534.
Link(s) to Main File(s)