Paper 2018/944

Data-Independent Memory Hard Functions: New Attacks and Stronger Constructions

Jeremiah Blocki and Ben Harsha and Siteng Kang and Seunghoon Lee and Lu Xing and Samson Zhou

Abstract

Data-Independent Memory-hard functions (iMHFs) are a key cryptographic primitive underlying the design of moderately expensive password hashing algorithms and egalitarian proofs of work that are resistant to side-channel attacks. Several goals for MHFs have been proposed including bandwidth hardness, space-time (ST) complexity, amortized area-time (aAT) complexity and sustained space complexity. An iMHF can be specified using a directed acyclic graph (DAG) $G$ with $N=2^n$ nodes and low indegree, and the cost (aAT, ST etc...) to evaluate the iMHF can be analyzed using pebbling games. In particular, given a parameter $N$ (e.g., maximum acceptable running time) we would like to design the DAG $G$ to have maximum possible pebbling cost i.e., to ensure that the iMHF is as expensive as possible for an attacker to compute. Recently, Alwen et al. (CCS'17) gave a randomized DAG construction called DRSample and proved that the aAT cost to pebble the graph was $\Omega\left( N^2/\log N\right)$. In an asymptotic sense the DRSample outperformed all prior constructions including Argon2i, the winner of the password hashing competition, which can be pebbled with aAT cost at most $\mathcal{O}\left(N^{1.767}\right)$. In this work we first prove a matching upper bound on the pebbling cost of DRSample by analyzing the greedy pebbling attack of Boneh et al. (ASIACRYPT'16). This sequential attack on DRSample is simple, easy to implement and has good concrete performance. In fact, our results show that, for practical values of $N\leq 2^{24}$, Argon2i provides stronger resistance to known pebbling attacks than DRSample reversing a finding of Alwen et al. (CCS'17). We then develop a new iMHF candidate by extending DRSample with the bit-reversal graph, and show that the iMHF resists all known attacks in practice and has optimal asymptotic performance under every MHF metric. In particular, we prove that (1) any (nearly) sequential pebbling attack (including the greedy pebbling attack) has aAT cost $\Omega\left( N^2\right)$, (2) any parallel attacker has aAT cost at least $\Omega\left(N^2/\log N\right)$ and at least $\Omega\left(N^2 \log \log N/\log N\right)$ unless one can find new depth-reducing attacks against DRSample which significantly improve upon the state of the art, (3) the graph has high bandwidth-complexity, and (4) any pebbling 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 strong guarantees on the sustained space-complexity. We also observe that the Argon2i round function can (trivially) be evaluated in parallel, which would allow an attacker to reduce aAT costs by (nearly) an order of magnitude, and we develop an inherently sequential version of the Argon2i round function that prevents this attack. We implement our new iMHF candidate (with and without the sequential round function) and show that evaluation speed is nearly identical to Argon2i. Finally, we provide a pebbling reduction which proves that in the parallel random oracle model (PROM) the cost of evaluating an iMHF like Argon2i or DRSample+BRG is given by the pebbling cost of the underlying DAG.