Guess Again (and Again and Again): Measuring Password Strength by Simulating Password-Cracking Algorithms

Guess Again (and Again and Again): Measuring Password Strength by Simulating Password-Cracking Algorithms. Patrick Gage Kelley and colleagues presented this work at the IEEE Symposium on Security and Privacy in 2012. They examined password strength by asking when a configured cracking model would try each password, then compared that evidence with entropy estimates—formula-based scores meant to represent uncertainty. The practical question is whether policy choices still look sensible when measured through an attacker’s guessing order. Their results show that the entropy measures did not consistently reproduce cracking magnitude across different search depths, while the simulated search itself had a defined cutoff.

A guess number is the position at which a particular deterministic cracking model would try a plaintext password. Deterministic means the same configuration produces the same ordering, and a lower rank means the password is guessed sooner. Instead of generating every earlier candidate, the calculator maps the password directly to its rank, making enormous simulated searches manageable. This is more concrete than an abstract bit score, but it is not a property of the password alone: changing the algorithm or its training material can change the result. That dependence is part of what the experiments tested.

The comparison asks more than which rule receives the highest formula-based score. It asks how passwords created under different policies fare at different guessing budgets, meaning different limits on how far the simulated attacker searches. It also examines whether richer or more closely matched training data changes the outcome and whether entropy estimates track the cracking results. Finally, the analysis tests whether passwords collected under one rule and merely filtered to satisfy another behave like passwords actually created under that target rule. These distinctions can materially change how a password policy appears to perform.

The study collected 12,000 passwords under several policy conditions, then evaluated them using 31 configurations that differed in both their guessing algorithms and training data. Representative approaches included a brute-force and Markov-style model and the Weir probabilistic context-free grammar model. In plain terms, these systems learned different password patterns from material such as RockYou and Openwall, then turned those patterns into an ordered sequence of guesses. Each plaintext password was mapped to the point where a configured model would try it, allowing the researchers to compare policies without generating every preceding guess.

The practical result is a budget-dependent reversal. Basic-sixteen eventually became more resistant than comprehensive-eight, although their ordering was opposite at lower guessing budgets. At the lower comparison point, the configured model also cracked far fewer passwords from comprehensive-eight than from basic-eight. These are names for separate policy conditions, and the comparisons apply to the particular models and budgets tested rather than establishing universal strength ratings.

Two additional comparisons explain why dataset construction matters. For groups governed by the study’s stronger policies, adding Openwall and closely matched study passwords to the baseline training material almost doubled average cracking, while basic-eight changed little. Separately, passwords created under comprehensive-eight were cracked more often on average than passwords created elsewhere and later filtered because they happened to satisfy that rule. The measurements therefore differed when the training material changed and between the created and filtered password sets, but the latter comparison alone does not establish that creation under the policy caused the difference.

The estimates belong to specific deterministic models and training configurations; a guess number is not a universal property of a password. The Weir lookup stopped at 50 trillion guesses, so that configuration did not assign later ranks. The authors also cautioned that a 16-character minimum was unusual, that the cracking algorithms might not have been optimized for it, and that the study did not model every attack type. These limits undermine any claim that one simulated rank captures all password risk or that the same policy ordering must hold under other attacks.

For password-policy work, a reasonable operational interpretation is to compare candidate rules under more than one relevant guessing budget and with training data resembling the password population being assessed. The experiments show why: the ordering changed as the budget grew, and closely matched training improved cracking against stronger-policy groups. Coarse entropy formulas are a poor substitute for this exercise. They roughly grouped policies but missed the size of cracking differences, and the evaluated formula gave basic-sixteen and comprehensive-eight the same 30-bit estimate. The authors preferred a 16-character minimum over comprehensive-eight in their tested setting, but framed that recommendation cautiously.

Kelley and colleagues contributed a tractable way to place plaintext passwords in the guessing order of configured cracking models. Their comparisons showed that policy rankings can depend on search budget, training material, and whether passwords were genuinely created under a rule or only filtered to satisfy it. Identity teams, password-policy owners, and security architects should evaluate policy choices with attacker-aware models and representative inputs, while remembering that one guess number is not universal and these experiments do not cover every attack type.