Abstract or Summary:
Textual passwords are perhaps the most prevalent mechanism for access control over the Internet. Despite the fact that human-beings generally select passwords in a highly skewed way, it has long been assumed in the password research literature that users choose passwords randomly and uniformly. This is partly because it is easy to derive concrete (numerical) security results under the uniform assumption, and partly because we do not know what’s the exact distribution of passwords if we do not make a uniform assumption. Fortunately, researchers recently reveal that user-chosen passwords generally follow the Zipf’s law, a distribution which is vastly different from the uniform one.

In this work, we explore a number of foundational security implications of the Zipf-distribution assumption about passwords. Firstly, we how the attacker’s advantages against password-based cryptographic protocols (e.g., authentication, encryption, signature and secret share) can be 2–4 orders of magnitude more accurately captured (formulated) than existing formulation results. As password protocols are the most widely used cryptographic protocols, our new formulation is of practical significance. Secondly, we provide new insights into popularity-based password creation policies and point out that, under the current, widely recommended security parameters, usability will be largely impaired. Thirdly, we show that the well-known password strength metric \(\alpha \)-guesswork, which was believed to be parametric, is actually non-parametric in two of four cases under the Zipf assumption. Particularly, nine large-scale, real-world password datasets are employed to establish the practicality of our findings.