Memory-Hard Functions: When Theory Meets Practice

Memory-hard functions (MHFs) is a class of hash functions whose fast evaluation requires the heavy use of memory, and an evaluation that spends less memory has to incur a much larger time penalty. Memory-hardness is particularly useful in the setting of password hashing and cryptocurrencies, as memory cost is platform-independent and efficient special-purpose hardware for brute-forcing attacks becomes much harder to be built. Since its first proposal by Colin Percival in 2009, many memory-hard hash heuristics were proposed, and the notion/design of MHFs has received a considerable amount of theoretical scrutiny as well. However, a large gap still exists when theory meets practice. On the one hand, most of the practical schemes are only heuristics without formal analysis, and attacks do exist for some of them; on the other hand, theoretical analyses are usually based on unrealistic assumptions: they consider MHFs as modes of operation of some underlying hash function H, modeled as a random oracle. Unfortunately, in practice, this is never the case as H is usually a heuristic design built from simpler primitives.This dissertation makes progress in addressing both of the problems. Our main contributions are threefold. First, we prove that a widely-used MHF candidate, called scrypt, is provably and optimally memory-hard, thus shedding light on the confidence of its wide application. Second, we model simple cryptographic tools (e.g. AES) as the underlying ideal primitives and present a generic and provably-secure MHF construction from hard-to-pebble graphs. The resulting scheme significantly decreases the efficiency gap between legitimate users and ASICs-equipped attackers. Finally, given the practice demands for H to have large outputs (to increase memory hardness without changing the description size of MHFs), we go back to the framework of constructing MHFs from H (with large output). Different from previous work, we take finer-granularity of the hash function H into account and provide the first provably secure design of H from simpler primitives (e.g. fixed-key AES)