PaperlayerView exact revision on arXiv

Source-linked AI summary

Investigating the Distribution of Password Choices

David Malone, Kevin Maher

arXiv:1104.3722v1cs.CR

TL;DR

The paper investigates whether Zipf’s Law describes password choices, which tend to favor memorable passwords over uniform selection. It fits password-frequency distributions, compares security statistics and cross-list guessing, and finds Zipf a reasonable but imperfect fit while proposing a way to make choices more uniform.

  • Problem

    The paper asks whether Zipf’s Law, observed in word frequencies, can describe password frequencies, which are shaped by users’ preference for memorable choices over uniform selection.

    Source: §1 · p. 1

  • Method

    The paper fits Zipf’s Law to leaked password lists, compares modeled and observed statistics and cross-list guessing, and proposes probabilistically prompting users to choose a different password.

    Source: §1 · pp. 1–2, §3 · p. 3

  • Results

    Zipf’s Law is a relatively good, though imperfect, fit; larger lists guide password rankings in other lists and can speed guessing or cracking with moderate guesses.

    Source: §7 · p. 13

  • Takeaways & Limitations

    The findings may help algorithm designers account for password-choice distributions, while the proposed scheme can guide users toward a more uniform distribution.

    Source: §7 · p. 13, §8 · p. 13

    The password lists were collected by differing methods and may contain random, possibly biased samples of users.

    Source: §2 · p. 2

Abstract

from arXiv · show

In this paper we will look at the distribution with which passwords are chosen. Zipf's Law is commonly observed in lists of chosen words. Using password lists from four different on-line sources, we will investigate if Zipf's law is a good candidate for describing the frequency with which passwords are chosen. We look at a number of standard statistics, used to measure the security of password distributions, and see if modelling the data using Zipf's Law produces good estimates of these statistics. We then look at the the similarity of the password distributions from each of our sources, using guessing as a metric. This shows that these distributions provide effective tools for cracking passwords. Finally, we will show how to shape the distribution of passwords in use, by occasionally asking users to choose a different password.

1 Introduction

The paper asks whether Zipf’s Law can model password frequencies, since users favor memorable choices rather than choosing uniformly. It finds Zipf a reasonable, though imperfect, fit and examines the security implications of skewed and similar password distributions, alongside a method for making choices more uniform.

1 Introduction

  • The study investigates Zipf’s Law using password lists from four sites, each made public after a security incident.The lists range from 1,800 to 32 million users.Source: §1 · p. 1
  • Because users favor memorable passwords over uniform choices, some passwords occur more often than others.The paper notes that passwords differ from natural-language word choices and that password advice may be arduous or hard to remember; the cost of choosing a compliant password has been argued to exceed the cost of losing protected information.Source: §1 · p. 1
  • Zipf’s Law provides a reasonable model of password frequencies, particularly in their long tail, but does not fully describe the data.The paper fits the law’s parameter s to password-frequency data.Source: §1 · pp. 1–2
  • Zipf-based estimates of guesswork and Shannon entropy are within a factor of two of actual values and usually outperform a uniform model.Source: §1 · p. 2
  • Passwords from one list can speed guessing passwords from another, showing that password-choice distributions share useful information.Source: §1 · p. 2
  • A Metropolis-Hastings-based technique probabilistically asks users setting or resetting passwords to choose a different one to make the distribution more uniform.Source: §1 · p. 2

2 Overview of Datasets

The section describes password lists made public after security incidents, their cleaning, and their differences in size and composition. It reports common-password and demographic patterns, and notes that localized password dictionaries can improve cracking.

2 Overview of Datasets

  • The lists came from four hacked sites, but differing collection methods mean they may be random, possibly biased samples of users.Source: §2 · p. 2
  • Table 1 compares users and distinct passwords by site; smaller lists have relatively more unique passwords.Source: Table 1 · p. 2, §2 · p. 2
  • After retaining each user's last listed password and omitting whitespace passwords, the authors ranked passwords by frequency; smaller lists had relatively more unique passwords.Source: §2 · p. 2
  • “123456” accounts for 0.7% of Hotmail passwords, 3.3% of flirtlife passwords, and 2.0% of RockYou passwords; “password” accounts for 1.2% of computerbits passwords.Table 2 summarizes the top ten passwords in each list.Source: §2 · p. 2, Table 2 · p. 3
  • Top passwords reflect site demographics: the Hotmail list was believed to come from Latino-targeted phishing, flirtlife showed German and Turkish names, and computerbits included Irish place names.The computerbits and RockYou lists also included their website names among their top ten passwords.Source: §2 · p. 2
  • Obvious passwords and site demographics can inform a targeted dictionary, and localized dictionaries can increase passwords recovered when cracking hashes.Source: §2 · pp. 2–3

3 Distribution of Passwords

The section compares password-frequency data with Zipf models using rank-frequency and count-frequency views, logarithmic fitting, and maximum-likelihood estimation. The fits show heavy-tailed behavior but indicate that several datasets are unlikely to follow Zipf’s Law exactly.

3 Distribution of Passwords

  • Log-log rank-frequency plots show heavy-tailed behavior; logarithmic rank bins reduce the shallow-slope bias from many passwords appearing once or twice.The bins sum frequencies for ranks 2^n through 2^(n+1)−1, producing a slope that better fits the data.Source: §3 · p. 3, Figure 3.2 · p. 4, Figure 3.3 · p. 4
  • The alternative n_k-versus-k view should also be binned before fitting; its Zipf line has slope −(1 + 1/s), with computerbits showing the largest discrepancy.Here n_k is the number of passwords used by exactly k users.Source: §3 · p. 3, Figure 3.4 · p. 5, Figure 3.5 · p. 5
  • A truncated-Zipf maximum-likelihood estimator assigns rank r probability proportional to r^−s for ranks 1 through N, where N is the number of passwords with nonzero frequency.Source: §3 · p. 3
  • Small fitted s values and p-values indicate that hotmail, computerbits, and rockyou are unlikely to be exactly Zipf-distributed; flirtlife and rockyou MLE estimates are close to least-squares estimates.Table 4 reports the MLE parameters.Source: §3 · p. 6, Table 4 · p. 6
  • For hotmail and computerbits, the largest Zipf discrepancies occur among the first few passwords, while their tails could fit Zipf with a higher p-value.Source: §3 · p. 6
  • The p-values are estimated by simulating fitted-Zipf samples and comparing their Anderson-Darling-modified K-S statistics with the statistic for the observed data.Source: §3 · p. 6

4 Password Statistics

The section compares password-security statistics computed from observed lists with estimates from Zipf and uniform models. Zipf generally approximates entropy well, but its guesswork estimates vary by dataset and can underestimate the observed values.

4 Password Statistics

  • For real lists, each password’s probability is its observed frequency divided by the total number of passwords.The section evaluates guesswork, α-guesswork, and entropy using observed lists and two models.Source: §4 · p. 6
  • Shannon entropy measures uncertainty but does not directly measure password guessability; min-entropy is also used as a conservative security measure.The section uses α = 0.85 to count guesses needed to cover most of the distribution while avoiding its tail.Source: §4 · pp. 6–7
  • Zipf underestimates guesswork for flirtlife and rockyou, while the uniform model predicts hotmail and computerbits relatively well but overestimates required guesses overall.For flirtlife and rockyou, shared passwords are more common and observed guesswork is far below the uniform estimate.Source: §4 · p. 7
  • Zipf provides relatively good approximations for Shannon, min-, and Rényi entropy; both models and data are close for Rényi entropy.The uniform model tends to overestimate entropy.Source: §4 · p. 7

5 The Relation between Distributions

The section tests how password orderings transfer across leaked lists and against Gawker hashes. Larger password lists can yield substantial recovery across datasets, though the return depends on the reference list and comparison method.

5 The Relation between Distributions

  • After 1,000 guesses, cross-list recovery varied by almost an order of magnitude depending on the reference list.The passage identifies the reference list as consequential for fast guessing.Source: §5 · pp. 8–9
  • Rockyou’s top million passwords covered close to 40% of users in the other lists, and larger reference lists yielded more successes after 10–100 guesses.The pattern suggests a more general password ordering beyond the most popular passwords.Source: Figure 5.1 · p. 9, §5 · p. 9
  • Large lists recovered 40% of Gawker users in fewer than one million trials, while smaller lists recovered more than 10,000 users in around 1,000 trials.The smaller-list recovery required less than one minute of CPU time.Source: §5 · p. 9, Figure 5.2 · p. 10
  • For distinct-password recovery, other lists reached about 40% in roughly 500,000–5,000,000 guesses, except when guessing rockyou passwords, where they lacked enough guesses.The result is measured against an optimal rate of one recovered password per guess.Source: Figure 5.3 · p. 10, §5 · p. 10
  • For Gawker, the rockyou-based guessing curve stayed relatively close to the optimal line from 10 to 10,000 guesses, indicating almost 100% success; all 14 million passwords cracked close to 40%.The dictionary-word curve stayed far from the optimal line, suggesting less than 10% of dictionary words were used as Gawker passwords.Source: §5 · p. 10
  • Large password sets recovered 40% of passwords in fewer than 10 million guesses, compared with over 100 million for other techniques unless trained on similar data.Once exhausted, a password list cannot provide more guesses, whereas mangling and Markov methods can theoretically produce unbounded candidate sets.Source: §5 · p. 11

6 Making Password Choices More Uniform

The section proposes a Metropolis–Hastings scheme that probabilistically asks users to choose another password to make password use more uniform. In a rockyou-based simulation, the most common password frequencies fell by more than two orders of magnitude, with users asked for 1.28 passwords on average.

6 Making Password Choices More Uniform

  • The scheme targets a uniform distribution by tracking users’ suggested-password frequencies online and probabilistically accepting or rejecting a new choice.It chooses a previously seen password as a reference and uses the tracked frequencies to decide whether to accept the new choice.Source: §6 · pp. 11–12
  • The Metropolis–Hastings scheme reduced the most common password frequencies from over 1,000 to just over 10, a drop of more than two orders of magnitude.The simulation generated passwords for 1,000,000 users from the rockyou dataset; Figure 6.1 plots the rank-frequency distributions.Source: §6 · p. 12, Figure 6.1 · p. 12
  • Users were asked for an average of 1.28 passwords per trial, with variance 0.61, despite the possibility that repeated rejection could frustrate them..Source: §6 · p. 12
  • The stored frequency information concerns users’ password choices rather than passwords currently in use, which the authors say offers an advantage if the table is stolen.They note that frequencies of hashed passwords could be stored instead of plaintext passwords.Source: §6 · p. 12
  • Unlike schemes that limit only popular passwords, this approach aims to make the whole distribution more uniform, including mid-ranked passwords relevant to guessing attacks.The authors say moderating mid-ranked passwords reduces the effectiveness of attacks using both high- and mid-ranked passwords.Source: §6 · p. 12

7 Discussion

Zipf’s law is an imperfect but passable description of password frequencies, and fitted distributions approximate several security statistics. The discussion also connects password-list overlap to cracking, describes password-reuse risks, and presents a way to encourage more uniform choices.

7 Discussion

  • Zipf’s law is not an exact match but provides a passable description of password frequencies, with parameter s estimates considerably below one.As s approaches zero, the distribution becomes uniform, which the authors describe as desirable for passwords.Source: §7 · p. 13
  • Fitted distributions approximate Shannon entropy and guesswork, while a uniform model can poorly estimate min-Entropy.Uniform models reasonably approximate data sets with smaller s.Source: §7 · p. 13
  • User demographics can appear in popular passwords, including website names, supporting locally tailored dictionaries for password checks.The authors note that some sites ban common passwords, including their own names, and recommend custom dictionaries of locally used terms.Source: §7 · p. 13
  • Larger password lists guide rankings in other lists and can speed guessing with moderate numbers of guesses, including against several guess-generating techniques.The reported speedup is particularly notable over simple dictionary attacks.Source: §7 · p. 13
  • Leaked passwords from one website can help crack hashed passwords elsewhere, reinforcing the risk of reusing passwords across sites.The authors describe the case where one site stores passwords unhashed and a leak facilitates later cracking on a system storing hashes.Source: §7 · p. 13
  • A Metropolis–Hastings scheme aims to make password choices more uniform without a precompiled list of common passwords.The authors report that fewer than 15,000 of more than 220,000 dictionary words appeared as passwords in the Gawker data set, and say a basic implementation could be incorporated into a PAM module.Source: §7 · p. 13

8 Conclusion

The paper concludes that Zipf’s law reasonably matches password frequencies and that password lists have similar orderings. It also presents a scheme to guide users toward more uniform password choices.

8 Conclusion

  • Zipf’s law is a relatively good match for the frequencies with which users choose passwords.Source: §8 · p. 13
  • Passwords found in the studied lists have relatively similar orderings, making passwords from one list good candidates for guessing or cracking another.Source: §8 · p. 13
  • The paper presents a scheme to guide users toward distributing their passwords more uniformly.Source: §8 · p. 13
Loading 1104.3722v1…