Students: Spring 2023, unless noted otherwise, sessions will be virtual on Zoom.
Memory Hard Functions and Password Hashing
Oct 11, 2017Download: MP4 Video Size: 147.6MB
Watch on YouTube
AbstractIn the last few years breaches at organizations like Yahoo!, Dropbox, Lastpass, AshleyMadison and Adult FriendFinder have exposed billions of user passwords to offline brute-force attacks. Password hashing algorithms are a critical last line of defense against an offline attacker who has stolen password hash values from an authentication server. An attacker who has stolen a user's password hash value can attempt to crack each user's password offline by comparing the hashes of likely password guesses with the stolen hash value. Because the attacker can check each guess offline it is no longer possible to lockout the adversary after several incorrect guesses. The attacker is limited only by the cost of computing the hash function. Offline attacks are increasingly commonplace and dangerous due to weak password selection and improved cracking hardware such as a GPU, Field Programmable Gate Array (FPGA) or an Application Specific Integrated Circuit (ASIC).
A secure password hashing algorithm should have the properties that (1) it can be computed quickly (e.g., at most one second) on a personal computer, (2) it is prohibitively expensive for an attacker to compute the function millions or billions of times to crack the user's password even if the attacker uses customized hardware. The first property ensures that the password hashing algorithm does not introduce an intolerably long delay for the user during authentication, and the second property ensures that an offline attacker will fail to crack most user passwords. Memory hard functions (MHFs), functions whose computation require a large amount of memory, are a promising cryptographic primitive to enable the design of a password hashing algorithm achieving both goals.
The talk will introduce and motivate the notion of memory hard functions and survey recent advances in the theory of MHFs. These results include (1) an attack on the Argon2i MHF, winner of the password hashing competition, which could reduce an amortized costs for a password attacker, (2) security lower bound for SCRYPT MHF and (3) construction of the first provably secure data-independent memory hard function.
About the Speaker
Jeremiah Blocki is an Assistant Professor in Computer Science at Purdue University. Jeremiah completed his PhD on Usable Human Authentication at Carnegie Mellon University under the supervision of Manuel Blum and Anupam Datta. Prior to joining Purdue he also spent a time at Microsoft Research New England as a postdoc and as a research fellow at the Simon's Institute for the Theory of Computing. Professor Blocki has made fundamental contributions to the theory of memory hard functions --- an important cryptographic primitive which can be used to protect low entropy secrets such as passwords against brute force attacks. Broadly, his research interests include cryptography, usable authentication, passwords, differential privacy, game theory and learning theory. One of his more ambitious research goals is to develop cryptographic protocols that are so simple that a human could execute them without receiving assistance from a trusted computer.