  We develop an economic model of an offline password cracker which allows us
to make quantitative predictions about the fraction of accounts that a rational
password attacker would crack in the event of an authentication server breach.
We apply our economic model to analyze recent massive password breaches at
Yahoo!, Dropbox, LastPass and AshleyMadison. All four organizations were using
key-stretching to protect user passwords. In fact, LastPass' use of
PBKDF2-SHA256 with $10^5$ hash iterations exceeds 2017 NIST minimum
recommendation by an order of magnitude. Nevertheless, our analysis paints a
bleak picture: the adopted key-stretching levels provide insufficient
protection for user passwords. In particular, we present strong evidence that
most user passwords follow a Zipf's law distribution, and characterize the
behavior of a rational attacker when user passwords are selected from a Zipf's
law distribution. We show that there is a finite threshold which depends on the
Zipf's law parameters that characterizes the behavior of a rational attacker --
if the value of a cracked password (normalized by the cost of computing the
password hash function) exceeds this threshold then the adversary's optimal
strategy is always to continue attacking until each user password has been
cracked. In all cases (Yahoo!, Dropbox, LastPass and AshleyMadison) we find
that the value of a cracked password almost certainly exceeds this threshold
meaning that a rational attacker would crack all passwords that are selected
from the Zipf's law distribution (i.e., most user passwords). This prediction
holds even if we incorporate an aggressive model of diminishing returns for the
attacker (e.g., the total value of $500$ million cracked passwords is less than
$100$ times the total value of $5$ million passwords).
  See paper for full abstract.
