Popularity is everything A new approach to protecting passwords from statistical-guessing attacks
Stuart E. Schechter, Cormac Herley, Michael Mitzenmacher · 2010
We propose to strengthen user-selected passwords against statistical-guessing attacks by allowing users of Internetscale systems to choose any password they want—so long as it’s not already too popular with other users. We create an oracle to identify undesirably popular passwords using an existing data structure known as a count-min sketch, which we populate with existing users ’ passwords and update with each new user password. Unlike most applications of probabilistic data structures, which seek to achieve only a maximum acceptable rate false-positives, we set a minimum acceptable false-positive rate to confound attackers who might query the oracle or even obtain a copy of it. 1.