Cryptology ePrint Archive: Report 2017/443

Practical Graphs for Optimal Side-Channel Resistant Memory-Hard Functions

Joel Alwen and Jeremiah Blocki and Ben Harsha

Abstract: A memory-hard function (MHF) $f_n$ with parameter $n$ can be computed in sequential time and space $n$. Simultaneously, a high amortized parallel area-time complexity (aAT) is incurred per evaluation. In practice, MHFs are used to limit the rate at which an adversary (using a custom computational device) can evaluate a security sensitive function that still occasionally needs to be evaluated by honest users (using an off-the-shelf general purpose device). The most prevalent examples of such sensitive functions are Key Derivation Functions and password hashing algorithms where rate limits help mitigate off-line dictionary attacks. As the honest users' inputs to these functions are often (low-entropy) passwords special attention is given to a class of side-channel resistant MHFs called iMHFs.

Essentially all iMHFs can be viewed as some mode of operation (making $n$ calls to some round function) given by a directed acyclic graph (DAG) with very low indegree. Recently, a combinatorial property of a DAG has been identified (called ``depth-robustness'') which results in good provable security for an iMHF based on that DAG. Depth-robust DAGs have also proven useful in other cryptographic applications. Unfortunately, up till now, all known very depth-robust DAGs are impractically complicated and little is known about their exact (i.e. non-asymptotic) depth-robustness both in theory and in practice.

In this work we build and analyze (both formally and empirically) several exceedingly simple and efficient to navigate practical DAGs for use in iMHFs and other applications. For each DAG we:

- Prove that their depth-robustness is asymptotically maximal.

- Prove bounds of at least $3$ orders of magnitude better on their exact depth-robustness compared to known bounds for other practical iMHF.

-Implement and empirically evaluate their depth-robustness and aAT against a variety of state-of-the art (and several new) depth-reduction and low aAT attacks. We find that, against all attacks, the new DAGs perform significantly better in practice than Argon2i, the most widely deployed iMHF in practice.

Along the way we also improve the best known empirical attacks on the aAT of Argon2i by implementing and testing several heuristic versions of a (hitherto purely theoretical) depth-reduction attack. Finally, for the best performing of the new DAGs we implement an iMHF using the Argon2i round function and code base and show that on a standard off-the-shelf CPU the new iMHF can actually be evaluated slightly faster than Argon2i (despite seemingly enjoying significantly higher aAT).

Category / Keywords: secret-key cryptography / Memory Hard Function, Password Hashing, Data-Independence, Depth-Robust Graph

Date: received 20 May 2017, last revised 7 Jun 2017

Contact author: jblocki at purdue edu

Available format(s): PDF | BibTeX Citation

Note: Typo fixes

Version: 20170607:180139 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]