Paper 2016/027

Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks

Dan Boneh, Henry Corrigan-Gibbs, and Stuart 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 or 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 attacks that run on single-core machines. Recent work shows how to use massively parallel special-purpose machines (e.g., with hundreds of cores) to attack Balloon and other memory-hard functions. We discuss these important attacks, which are outside of our adversary model, and propose practical defenses against them. To motivate the need for security proofs in the area of password hashing, 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.

Note: This version corrects an error in Lemma 7.

Metadata
Available format(s)
PDF
Publication info
A major revision of an IACR publication in ASIACRYPT 2016
Keywords
memory-hard functionspassword hashingpebbling argumentstime-space trade-offssandwich graphArgon2scrypt
Contact author(s)
henrycg @ cs stanford edu
History
2017-05-12: last of 10 revisions
2016-01-12: received
See all versions
Short URL
https://ia.cr/2016/027
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/027,
      author = {Dan Boneh and Henry Corrigan-Gibbs and Stuart Schechter},
      title = {Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks},
      howpublished = {Cryptology ePrint Archive, Paper 2016/027},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/027}},
      url = {https://eprint.iacr.org/2016/027}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.