TL;DR
This paper challenges the current "three random words" password advice by proving that human bias makes such passwords weaker than theoretically expected. By applying a mathematical framework based on Zipf’s Law to real-world leaked datasets, the authors demonstrate that a five-word password policy is necessary to provide the security level that experts originally intended.
What Problem Does This Paper Address?
There is a frustrating lack of consensus on Password Composition Policies (PCPs). While the US NIST suggests a minimum length of 8 characters with no complexity requirements, the UK NCSC advocates for a "three random words" approach. Meanwhile, many websites still enforce arbitrary rules (e.g., "must contain a symbol and a digit") that often lead users to create predictable patterns like Password1!.
The core issue is that current policies lack a theoretical foundation that accounts for actual human behavior. Most security models assume users pick words or characters uniformly at random, but in reality, humans are highly predictable. This paper seeks to bridge the gap between theoretical security and the messy reality of how people actually choose passwords.
Methods
The authors developed a novel theoretical framework to analyze password structures. Key components include:
- Structural Decomposition: Instead of looking at a password as a string of characters, they broke it down into constituents like words ($w$), names ($n$), dates ($d$), and symbols ($s$).
- Probabilistic Modeling: They moved beyond simple Shannon entropy (which assumes all characters are equally likely) to a model that accounts for dependencies between elements in a password structure.
- Zipf’s Law Application: The researchers modeled word selection using a power-law distribution. This accounts for the fact that a few words (like "password" or "love") are chosen much more frequently than others, significantly lowering the actual entropy of a passphrase.
Datasets
The study utilized the PasswordNinja dataset, which consists of human- and machine-labeled passwords decomposed into their structural parts. This includes:
- Hotmail Dataset (2009): 8,929 records procured via phishing.
- LizardSquad Dataset (2015): 11,808 records from a gaming-related breach.
- SecLists: A well-known collection of multiple types of lists used during security assessments, used here for ethical benchmarking.
Key Insights and Ideas
- The "Three Words" Fallacy: The NCSC’s recommendation of three random words assumes a uniform distribution. Because humans follow a Zipfian (power-law) distribution when picking words, three words chosen by a human provide much less security than three words chosen by a computer.
- Structure is Predictable: Password structures themselves follow a power law. A tiny fraction of structures (like
word + digit) accounts for the vast majority of user-created passwords. - The Entropy Gap: As the available vocabulary increases, the difference in entropy between a uniform distribution and a human (Zipfian) distribution actually grows. This means simply having a larger dictionary doesn't solve the problem of human predictability.
- Strength Meter Blind Spots: The authors found that popular tools like
zxcvbn(used by Dropbox) can be over-optimistic, awarding high security scores to common phrases likegirlsruledaworldbecause they lack a structural understanding of passphrases.
Key Results
- The 5-Word Rule: To achieve the same level of security that a truly random 3-word passphrase provides, a human user needs to select 4 to 5 words.
- Cracking Benchmarks: Using an NVIDIA RTX 4090 for testing, the authors showed that single-word passwords ($w$) are cracked almost instantaneously. In contrast, a four-word structure ($wwww$) can resist offline attacks for thousands of years, even when using fast hashes like MD5.
- Quantitative Support: The paper provides a formal mathematical proof (Equation 11) showing that total entropy $H$ is the product of the number of words $n$ and the entropy per word $H_{word}$, allowing admins to calculate exactly how many words are needed to meet a specific security threshold.
Limitations and Future Work
- Dataset Age: The primary datasets are from 2009 and 2015. While the authors argue that password patterns remain relatively stable, more modern datasets might reflect changes in user behavior due to the rise of password managers.
- Language Constraints: The analysis focused primarily on English and Spanish. Different linguistic structures might impact the Zipfian distribution of word choices.
- Semantic Relationships: The current model assumes words are chosen independently. Future work could incorporate "memorability" and semantic links (e.g., users picking words that form a coherent, and thus more guessable, sentence like "I love my dog").
Summary updated