Hash rates provided by specialized hardware such as ASICs render schemes based on iterated hashing ineffective in protecting password storage, and hence memory-hard functions (MHFs) are recommended for modern password storage. The study of MHFs so far has mainly focused on providing provable guarantees on their minimum expected time--memory complexity cost per evaluation. However, this does not tell us to what degree passwords remain unrecoverable if password banks protected using MHFs are compromised. This thesis aims to answer this question in the context of up to date password security models. This means proving unrecoverability bounds for a large class of MHFs: graph-based data-independent MHFs (iMHFs). Specifically, we prove upper bounds on the \emph{multi-instance} unrecoverability of any graph-based iMHF, based on the unguessability of stored passwords, the number of hash evaluations it carries out, and crucially the cumulative memory complexity of the adversary.
To prove this result, we extend the standard definitions of both guessability, and of memory-hardness to strictly stronger \emph{hash-dependent} settings. We prove reductions from unrecoverability to unguessability in the hash-dependent setting and show that, unlike the hash-independent setting, unpredictable salting is essential in the hash-dependent setting. We then prove that, in contrast to general MHFs, graph-based iMHFs are memory-hard in the hash-dependent setting.
In the last part of the thesis, the analysis is extended to prove indifferentiability results for iMHFs in a large class of multi-stage games, i.e., games which follow a sample, salt and use structure. We show that in this class of games, an iMHF is as secure as a random oracle. Importantly, we give a treatment of adversaries with access to preprocessing information.
