We are pleased to share that Wickr has been acquired by Amazon and is now part of the Amazon Web Services (AWS) team. We’re proud to have created highly trusted, secure communication solutions for messaging, video conferencing, file sharing, and more. From our founding ten years ago, we have grown to serve organizations across a wide range of industries, all over the world. Together with AWS, we look forward to taking our solutions to the next level for our customers and partners. Learn more here →

Authors: Alwen, Gazi, Kamath, Klein, Osang, Pietrzak, Reyzin, Rolinek, Rybar
Venua: AsiaCCS
Date: 2018
Full Version: https://eprint.iacr.org/2016/783
Proceedings Version: https://dl.acm.org/citation.cfm?doid=3196494.3196534

We show attacks on five data-independent memory-hard functions (iMHF) that were submitted to the password hashing competition. Informally, an MHF is a function which cannot be evaluated on dedicated hardware, like ASICs, at significantly lower energy and/or hardware cost than evaluating a single instance on a standard single-core architecture. Data-independent means the memory access pattern of the function is independent of the input; this makes iMHFs harder to construct than data-dependent ones, but the latter can be attacked by various side-channel attacks.

Following , we capture the evaluation of an iMHF as a directed acyclic graph (DAG). The cumulative parallel pebbling complexity of this DAG is a good measure for the cost of evaluating the iMHF on an ASIC. If n denotes the number of nodes of a DAG (or equivalently, the number of operations — typically hash function calls — of the underlying iMHF), its pebbling complexity must be close to n^2 for the iMHF to be memory-hard. We show that the following iMHFs are far from this bound: Rig.v2, TwoCats and Gambit can be attacked with complexity O(n^{1.75}); the data-independent phase of Pomelo (a finalist of the password hashing competition) and Lyra2 (also a finalist) can be attacked with complexity O(n^{1.83}) and O(n^{1.67}), respectively.

For our attacks we use and extend the technique developed by , who show that the pebbling complexity of a DAG can be upper bounded in terms of its depth-robustness.