Computer Science Distinguished Lecture
Location:
8102
-
Gates & Hillman Centers
Speaker:
JEREMIAH BLOCKI
,
Postdoctoral Fellow
http://www.cs.cmu.edu/~jblocki/
We demonstrate an algorithm for evaluating data-independent memory-hard functions (iMHFs) with significantly less cumulative resources (e.g., memory/energy) than ideally desired of such algorithms. Data-independent memory-hard functions are defined by fixing a directed acyclic graph (DAG) G on n nodes which represents the dependence between the inputs and outputs of n calls to an underlying compression function H. Ideally we would like that to compute an iMHF (even allowing parallel calls to H) the cumulative computational resources required should be Omega(n^2). That is either the sum of the amount of memory used at each time step should be at least Omega(n^2) or the total number of queries to H should be at least Omega(n^2). In this work we demonstrate attacks on iMHFs based on three classes of DAGs each using o(n^2) resources. In particular we get that: (1) The Catena-Dragonfly iMHF can be computed by an algorithm with cumulative complexity O(n^{1.67}). Similarly, the cumulative complexity of the newer Catena-Butterfly iMHF is O(n^{1.67}). (2) The Argon2i iMHF (winner of the Password Hashing Competition) can be computed by an algorithm with cumulative complexity O(n^{7/4}\log(n)). (3) Any iMHF can be computed by an algorithm with cumulative complexity O(n^2/\log^{1-\epsilon}(n)) for all epsilon > 0. At a technical level we provide a general attack against any iMHF defined by a DAG $G=(V,E)$ that is not depth-robust, meaning that we can find a ``small" set $S\subset V$ of nodes such that $G-S$ does not contain a ``long" path. We demonstrate that the Catena and Argon2i DAGs are not depth robust in an extreme sense. Furthermore, no simple DAG (constant indegree) is sufficiently depth robust to resist an attack with cumulative complexity O(n^2/\log^{1-\epsilon}(n)). This shows that the goal of constructing an iMHF requiring Omega(n^2) cumulative resources is unachievable. Joint work with Joel Alwen (IST Austria) About the Speaker