Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks
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 oft
- PDF / 925,472 Bytes
- 29 Pages / 439.37 x 666.142 pts Page_size
- 83 Downloads / 136 Views
Stanford University, Stanford, CA 94305, USA {dabo,henrycg}@cs.stanford.edu Microsoft Research, Redmond, WA 98052, USA
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 passwordhashing 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 passwordhashing 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 memory-hard functions, including Balloon. 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. Keywords: Memory-hard functions · Password hashing · Pebbling arguments · Time-space trade-offs · Sandwich graph · Argon2 · Scrypt
1
Introduction
The staggering number of password-file breaches in recent months demonstrates the importance of cryptographic protection for stored passwords. In 2015 alone, The full version of this paper is available online at https://eprint.iacr.org/2016/027. c International Association for Cryptologic Research 2016 J.H. Cheon and T. Takagi (Eds.): ASIACRYPT 2016, Part I, LNCS 10031, pp. 220–248, 2016. DOI: 10.1007/978-3-662-53887-6 8
Balloon Hashing: A Memory-Hard Function Providing Provable Protection
221
attackers stole files containing users’ login names, password hashes, and contact information from many large and well-resourced organizations, including LastPass [79], Harvard [47], E*Trade [62], ICANN [45], Costco [41], T-Mobile [76], the University of Virginia [74], and a large number of others [65]. In this environment, systems administrators must operate under the assumption that attackers will eventually gain access to sensitive authentication information, such as password hashes and salts, stored on their computer systems. After a compromise, the secrecy of user passwords rests on the cost to an attacker of mounting an offline dictionary at
Data Loading...
