On the memory hardness of data independent password hashing functions Conference Paper

Author(s): Alwen, Joël; Gaži, Peter; Kamath, Chethan; Klein, Karen; Osang, Georg; Pietrzak, Krzysztof; Reyzin, Lenoid; Rolinek, Michal; Rybar, Michal
Title: On the memory hardness of data independent password hashing functions
Affiliation IST Austria
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.
Keywords: Authentication; Graph theory; Side channel attack; Directed graphs; Computer hardware; Hardware; Memory architecture
Conference Title: Unknown (9781450355766)
Conference Dates: June 4-8, 2018
Conference Location: Incheon, South Korea
ISBN: 9781450355766
Publisher: Association for Computing Machinery, Inc  
Date Published: 2018-06-01
Start Page: 51
End Page: 65
DOI: 10.1145/3196494.3196534
Notes: 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.
Open access: yes (repository)
IST Austria Authors
  1. Michal Rybar
    4 Rybar
  2.  Peter Gazi
    9 Gazi
  3. Joel Alwen
    13 Alwen
  4. Karen Klein
    2 Klein
  5. Georg Osang
    3 Osang
Related IST Austria Work