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 Amazon.com 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>

 

Personnel

Students: Ben Harsha Samson Zhou Seunghoon Lee

Representative Publications

• Practical Graphs for Optimal Side-Channel Resistant Memory-Hard Functions. with Joel Alwen and Ben Harsha 24th ACM Conference on Computer and Communications Security

• Sustained Space Complexity. with with Joel Alwen and Krzysztof Pietrzak. EUROCRYPT 2018.

• Bandwidth-Hard Functions: Reductions and Lower Bounds. with Ling Ren and Samson Zhou. 25th ACM Conference on Computer and Communications Security.

• On the Computational Complexity of Minimal Cumulative Cost Graph Pebbling. with Samson Zhou. Financial Crypto 2018.

• • Efficiently Computing Data Independent Memory Hard Functions. with Joel Alwen. CRYPTO 2016.

   

• Depth-Robust Graphs and Their Cumulative Memory Complexity. with Joel Alwen and Krzysztof Pietrzak. EUROCRYPT 2017).

   

   

   

• Towards Practical Attacks on Argon2i and Balloon Hashing. with Joel Alwen. EuroS&P 2017.

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