CERIAS - Center for Education and Research in Information Assurance and Security

Skip Navigation
Purdue University - Discovery Park
Center for Education and Research in Information Assurance and Security

Memory Hard Functions and Password Hashing

Jeremiah Blocki

Oct 11, 2017

Size: 147.6MB

Download: Video Icon MP4 Video  
Watch in your Browser   Watch on Youtube Watch on YouTube


In 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.

Unless otherwise noted, the security seminar is held on Wednesdays at 4:30P.M. STEW G52 (Suite 050B), West Lafayette Campus. More information...


The views, opinions and assumptions expressed in these videos are those of the presenter and do not necessarily reflect the official policy or position of CERIAS or Purdue University. All content included in these videos, are the property of Purdue University, the presenter and/or the presenter’s organization, and protected by U.S. and international copyright laws. The collection, arrangement and assembly of all content in these videos and on the hosting website exclusive property of Purdue University. You may not copy, reproduce, distribute, publish, display, perform, modify, create derivative works, transmit, or in any other way exploit any part of copyrighted material without permission from CERIAS, Purdue University.