Password Hashing Algorithms

Principal Investigator: Jeremiah Blocki

In the last few years breaches at organizations like Yahoo!, Dropbox, Lastpass, AshleyMadison and Adult FriendFinder have exposed over a billion user passwords to offline 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. A 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 e.g., the Antminer S9, currently available on for around $3,000 (USD), is capable of computing 14 trillion SHA256 hashes/second. When LastPass was breached they were using PBKDF2, a slow password hashing algorithm which iteratively computes SHA256 100,000 times. Thus, a LastPass attacker could potentially check 140 million password guesses per second on the Antminer S9. By comparison, 70 million guesses suffice to crack most user passwords (e.g., see empirical frequency data for Yahoo! passwords). There is a clear need to develop secure (moderately expensive) password hashing algorithms so that it is economically infeasible for an offline adversary to check millions of password guesses.

Recognizing this clear need researchers recently organized the Password Hashing Competition (PHC) to encourage the development of better password hashing algorithms. A secure password hashing algorithm should be: 1) quickly computable (e.g., $< 1>



Students: Ben Harsha Samson Zhou Seunghoon Lee

Representative Publications

Keywords: ASICs, Data Independent Memory Hard Functions, Depth-Robust Graphs, Graph Pebbling