Paper 2016/115
Efficiently Computing DataIndependent MemoryHard Functions
Joel Alwen and Jeremiah Blocki
Abstract
A memoryhard function (MHF) $f$ is equipped with a {\em space cost} $\sigma$ and {\em time cost} $\tau$ parameter such that repeatedly computing $f_{\sigma,\tau}$ on an application specific integrated circuit (ASIC) is not economically advantageous relative to a general purpose computer. Technically we would like that any (generalized) circuit for evaluating an iMHF $f_{\sigma,\tau}$ has area $\times$ time (AT) complexity at $\Theta(\sigma^2 * \tau)$. A dataindependent MHF (iMHF) has the added property that it can be computed with almost optimal memory and time complexity by an algorithm which accesses memory in a pattern independent of the input value. Such functions can be specified by fixing a directed acyclic graph (DAG) $G$ on $n=\Theta(\sigma * \tau)$ nodes representing its computation graph. 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 ATcomplexity. 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 threadcount) such that $n=\sigma*\tau$. 1) The CatenaDragonfly function of~\cite{forler2013catena} has AT and energy complexities $O(n^{1.67})$. 2) The CatenaButterfly function of~\cite{forler2013catena} has complexities is $O(n^{1.67})$. 3) The DoubleBuffer 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 SingleBuffer 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 ATcomplexity $\Theta(\sigma^2 * \tau)$ is unachievable. Along the way we prove a lemma upperbounding the depthrobustness of any DAG which may prove to be of independent interest.
Note: Improved analysis of the attack on multipass variants of random DAG based iMHFs.
Metadata
 Available format(s)
 Publication info
 Preprint. MINOR revision.
 Keywords
 Memory Hard FunctionPassword HashingDepthRobust GraphGraph PebblingArgon2
 Contact author(s)
 jblocki @ microsoft com
 History
 20160308: last of 2 revisions
 20160211: received
 See all versions
 Short URL
 https://ia.cr/2016/115
 License

CC BY
BibTeX
@misc{cryptoeprint:2016/115, author = {Joel Alwen and Jeremiah Blocki}, title = {Efficiently Computing DataIndependent MemoryHard Functions}, howpublished = {Cryptology ePrint Archive, Paper 2016/115}, year = {2016}, note = {\url{https://eprint.iacr.org/2016/115}}, url = {https://eprint.iacr.org/2016/115} }