Paper 2018/944
DataIndependent Memory Hard Functions: New Attacks and Stronger Constructions
Jeremiah Blocki, Ben Harsha, Siteng Kang, Seunghoon Lee, Lu Xing, and Samson Zhou
Abstract
Memoryhard functions (MHFs) are a key cryptographic primitive underlying the design of moderately expensive password hashing algorithms and egalitarian proofs of work. Over the past few years several increasingly stringent goals for an MHF have been proposed including the requirement that the MHF have high sequential spacetime (ST) complexity, parallel spacetime complexity, amortized areatime (aAT) complexity and sustained space complexity. DataIndependent Memory Hard Functions (iMHFs) are of special interest in the context of password hashing as they naturally resist sidechannel attacks. iMHFs can be specified using a directed acyclic graph (DAG) $G$ with $N=2^n$ nodes and low indegree and the complexity of the iMHF can be analyzed using a pebbling game. Recently, Alwen et al. [CCS 17] constructed a DAG called DRSample that has aAT complexity at least $\Omega\left( N^2/\log N\right)$. Asymptotically DRSample outperformed all prior iMHF constructions including Argon2i, winner of the password hashing competition (aAT cost $\mathcal{O}\left(N^{1.767}\right)$), though the constants in these bounds are poorly understood. We show that the greedy pebbling strategy of Boneh et al. [ASIACRYPT 16] is particularly effective against DRSample e.g., the aAT cost is $\mathcal{O}\left( N^2/\log N\right)$. In fact, our empirical analysis {\em reverses} the prior conclusion of Alwen et al. that DRSample provides stronger resistance to known pebbling attacks for practical values of $N \leq 2^{24}$. We construct a new iMHF candidate (DRSample+BRG) by using the bitreversal graph to extend DRSample. We then prove that the construction is asymptotically optimal under every MHF criteria, and we empirically demonstrate that our iMHF provides the best resistance to {\em known} pebbling attacks. For example, we show that any parallel pebbling attack either has aAT cost $\omega(N^2)$ or requires at least $\Omega(N)$ steps with $\Omega(N/\log N)$ pebbles on the DAG. This makes our construction the first practical iMHF with a strong sustained spacecomplexity guarantee and immediately implies that any parallel pebbling has aAT complexity $\Omega(N^2/\log N)$. We also prove that any sequential pebbling (including the greedy pebbling attack) has aAT cost $\Omega\left( N^2\right)$ and, if a plausible conjecture holds, any parallel pebbling has aAT cost $\Omega(N^2 \log \log N/\log N)$  the best possible bound for an iMHF.
Note: Full version of CRYPTO 2019 paper
Metadata
 Available format(s)
 Publication info
 A major revision of an IACR publication in CRYPTO 2019
 Keywords
 Memory Hard FunctionDepthRobust GraphSustained Space ComplexityGraph Pebbling
 Contact author(s)
 jblocki @ purdue edu
 History
 20190604: last of 3 revisions
 20181005: received
 See all versions
 Short URL
 https://ia.cr/2018/944
 License

CC BY
BibTeX
@misc{cryptoeprint:2018/944, author = {Jeremiah Blocki and Ben Harsha and Siteng Kang and Seunghoon Lee and Lu Xing and Samson Zhou}, title = {DataIndependent Memory Hard Functions: New Attacks and Stronger Constructions}, howpublished = {Cryptology {ePrint} Archive, Paper 2018/944}, year = {2018}, url = {https://eprint.iacr.org/2018/944} }