Towards a Theory of Data-Independent Memory Hard Functions

Memory hard functions (MHFs), first explicitly introduced by Percival, are a promising key-stretching tool for password hashing because the cost of storing/retrieving items from memory is relatively constant across different computer architectures. Thus, in contrast to standard cryptographic hash functions (e.g., SHA256) the cost of computing an MHF cannot be significantly reduced by developing customized hardware (ASICs). More specifically, we want to ensure that any circuit evaluating multiple instances of the MHF has high amortized AT-complexity --- Area X Time/#instances. Data-Independent Memory Hard Functions (iMHFs) are an important variant of MHFs due to their greater resistance to side-channel attacks. An iMHF can be specified by a directed acyclic G specifying data-dependencies during computation. Due to the recently completed Password Hashing Competition we have many candidate iMHFs, but many of these iMHFs had not been analyzed until recently.

This talk will summarize recent results demonstrating that a combinatorial property called depth-robustness fully characterizes iMHFs with high amortized-AT complexity. We will also show that Argon2i, the winner of the password hashing competition, is defined using a directed acyclic graph G that is not depth-robust. The resulting attacks are practical for realistic settings of the Argon2i parameters.

The talk is based on joint work with Joel Alwen and Krzysztof Pietrzak.