Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks
Authors: D. Boneh, H. Corrigan-Gibbs, and S. Schechter
Abstract:
We present the Balloon password-hashing algorithm.
This is the first practical cryptographic hash function that:
(i) has proven memory-hardness properties in the random-oracle model,
(ii) uses a password-independent access pattern, and
(iii) meets, and often exceeds, the performance
of the best heuristically secure password-hashing algorithms.
Memory-hard functions require a large amount of working space to evaluate
efficiently and, when used for password hashing, they dramatically increase the
cost of offline dictionary attacks.
In this work, we leverage a previously unstudied property of
a certain class of graphs ("random sandwich graphs")
to analyze the memory-hardness of the Balloon algorithm.
The techniques we develop are general: we also use them to give a
proof of security of the scrypt and Argon2i password-hashing functions,
in the random-oracle model.
Our security analysis uses a sequential model of computation,
which essentially captures attackers who run on single-core machines.
Recent work shows how to use massively parallel special-purpose
machines (e.g., with hundreds of cores) to attack memory-hard functions, including Balloon
We discuss this important class of attacks, which is outside of our adversary
model, and propose practical defenses against these attacks.
To motivate the need for security proofs in the area, we demonstrate and implement
a practical attack against Argon2i that successfully evaluates the function
with less space than was previously claimed possible.
Finally, we use experimental results to compare the performance of the
Balloon hashing algorithm to other memory-hard functions.
Reference:
In proceedings of ASIACRYPT 2016, pp. 220-248.
Full paper: pdf
Related papers: See project site.