Economics of Password Cracking
Principal Investigator: Jeremiah Blocki
In recent years the authentication servers at major companies like Yahoo!, Dropbox, Ashley Madison, eBay, Zappos, Sony, LinkedIn and Adobe have been breached resulting in the release of the cryptographic hashes of over a billion of user passwords, each of which has significant economic value to adversaries. An adversary who has obtained the cryptographic hash of a user's password can mount an offline attack to crack the password by comparing this hash value with the cryptographic hashes of likely password guesses. This offline attacker is limited only by the resources he is willing to invest to crack the password. This project aims to address the following questions: Can we quantitatively predict how many passwords a rational attacker will crack after a breach? What defenses could an authentication server adopt to minimize the potential damage if a password breach does occur?
We have developed an economic model of password cracking, which are currently using to analyze recent password breaches. (e.g., what % of Yahoo! will be cracked by an attacker?). The basic premise of our model is that a rational attacker should cease attacking once marginal guessing costs exceed the marginal guessing reward. An attacker's marginal guessing reward is parameterized by the value of a cracked password and by the empirical distribution over user selected passwords (e.g., expected marginal reward is the value a cracked password times the probability that the next password guess is correct). Marginal guessing costs are given by the (amortized) cost of computing the password hash function. Most password hashing algorithms (e.g., Argon2i, SCRYPT, BCRYPT) have time/memory parameters which can be tuned to increase/decrease marginal guessing costs. We are currently working on using our economic model to provide concrete recomendations about how to set the parameters of a password hashing algorithm to ensure that the % of passwords which would be cracked by an offline attacker in the event of a breach is acceptably small.
Students: Ben Harsha Samson Zhou
- CASH: A Cost Asymmetric Secure Hash Algorithm for Optimal Password Protection. with Anupam Datta. CSF 2016.
Client-CASH: Protecting Master Passwords against Offline Attacks. with Anirudh Sridhar. AsiaCCS 2016.
On the Economics of Offline Password Cracking. with Ben Harsha and Samson Zhou. (Working Paper)
Keywords: Cost Asymmetric Secure Hash, Game Theory, Password Cracking