In this work we develop new tools for analyzing iMHFs. First we define and motivate a new complexity measure capturing the amount of {\em energy} (i.e. electricity) required to compute a function. We argue that, in practice, this measure is at least as important as the more traditional AT-complexity. Next we describe an algorithm $\mathcal{A}$ for repeatedly evaluating an iMHF based on an arbitrary DAG $G$. We upperbound both its energy and AT complexities per instance evaluated in terms of a certain combinatorial property of $G$.
Next we instantiate our attack for several general classes of DAGs which include those underlying many of the most important iMHF candidates in the literature. In particular, we obtain the following results which hold for all choices of parameters $\sigma$ and $\tau$ (and thread-count) such that $n=\sigma*\tau$.
1) The Catena-Dragonfly function of~\cite{forler2013catena} has AT and energy complexities $O(n^{1.67})$.
2) The Catena-Butterfly function of~\cite{forler2013catena} has complexities is $O(n^{1.67})$.
3) The Double-Buffer and the Linear functions of~\cite{CBS16} both have complexities in $O(n^{1.67})$.
4) The Argon2i function of~\cite{Argon2} (winner of the Password Hashing Competition~\cite{PHC}) has complexities $O(n^{7/4}\log(n))$.
5) The Single-Buffer function of~\cite{CBS16} has complexities $O(n^{7/4}\log(n))$.
6) \emph{Any} iMHF can be computed by an algorithm with complexities $O(n^2/\log^{1-\epsilon}(n))$ for all $\epsilon > 0$. In particular when $\tau=1$ this shows that the goal of constructing an iMHF with AT-complexity $\Theta(\sigma^2 * \tau)$ is unachievable.
Along the way we prove a lemma upper-bounding the depth-robustness of any DAG which may prove to be of independent interest.
Category / Keywords: Memory Hard Function, Password Hashing, Depth-Robust Graph, Graph Pebbling, Argon2 Date: received 10 Feb 2016, last revised 8 Mar 2016 Contact author: jblocki at microsoft com Available format(s): PDF | BibTeX Citation Note: Improved analysis of the attack on multi-pass variants of random DAG based iMHFs. Version: 20160308:192215 (All versions of this report) Short URL: ia.cr/2016/115