  A central challenge in password security is to characterize the attacker's
guessing curve i.e., what is the probability that the attacker will crack a
random user's password within the first $G$ guesses. A key challenge is that
the guessing curve depends on the attacker's guessing strategy and the
distribution of user passwords both of which are unknown to us. In this work we
aim to follow Kerckhoffs' principle and analyze the performance of an optimal
attacker who knows the password distribution. Let $\lambda_G$ denote the
probability that such an attacker can crack a random user's password within $G$
guesses. We develop several statistically rigorous techniques to upper and
lower bound $\lambda_G$ given $N$ independent samples from the unknown
distribution. We show that our bounds hold with high confidence and apply our
techniques to analyze eight password datasets. Our empirical analysis shows
that even state-of-the-art password cracking models are often significantly
less guess efficient than an attacker who can optimize its attack based on its
(partial) knowledge of the password distribution. We also apply our techniques
to re-examine the empirical password distribution and Zipf's Law. We find that
the empirical distribution closely matches our bounds on $\lambda_G$ when $G$
is not too large i.e., $G \ll N$. However, for larger values of $G$ our
empirical analysis rigorously demonstrates that the empirical distribution
(resp. Zipf's Law) overestimates the attacker's success rate. We apply our
techniques to upper/lower bound the effectiveness of password throttling
mechanisms (key-stretching) which are used to reduce the number of attacker
guesses $G$. Finally, if we make an additional assumption about the way users
respond to password restrictions, we can use our techniques to evaluate the
effectiveness of password composition policies which restrict the passwords
users may select.
