{'fraction_non_alphanumeric': 0.0489019926799512, 'fraction_numerical': 0.01191202385793683, 'mean_word_length': 3.911534620505992, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 24, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 23, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Optimizing Password Composition Policies

A password composition policy restricts the space of allowable passwords to eliminate weak passwords that are vulnerable to statistical guessing attacks. Usability studies have demonstrated that existing password composition policies can sometimes result in weaker password distributions; hence a more principled approach is needed. We introduce the first theoretical model for optimizing password composition policies. We study the computational and sample complexity of this problem under different assumptions on the structure of policies and on users' preferences over passwords. Our main positive result is an algorithm that -- with high probability --- constructs almost optimal policies (which are specified as a union of subsets of allowed passwords), and requires only a small number of samples of users' preferred passwords. We complement our theoretical results with simulations using a real-world dataset of 32 million passwords.


INTRODUCTION
Imagine a web surfer, an online shopper, or a reviewer in a prominent CS and Economics conference 1 who logs on for the first time to a server; so that she can sign up for some service, place a shopping order, or view a list of assigned papers. Such a user registers on the server by choosing a username and picking a password. Naturally, our user's first attempt at picking a password is her favorite combination '123456', which the server declines. She then has to pick a password that follows certain guidelines: of suitable length, involving lower-and upper-case letters, with numbers or special characters, etc. Such password composition policies defend against the "first line" of attack -guessing attacks by uninformed attackers (attackers with no previous knowledge of the user whose account they are trying to break into).
Password composition policies are a necessity because -without them -userselected passwords are predictable. Indeed, many unrestricted users would select simple passwords like '123456', 'password' and 'letmein' [Doel 2012]. Furthermore, this issue is of great importance to today's economy. Passwords are commonly used in electronic commerce to protect financial assets. In fact, the passwords themselves have financial value. Symantec reported that compromised passwords are sold for between $4 and $30 on the black market [Fossi et al. 2008], and a 2004 Gartner case study [Witty et al. 2004] estimated that it cost a large firm over $17 per password-reset call. Nevertheless, existing password composition policies are typically not principled, and do not necessarily result in less common passwords. For example, studies show that users respond to restrictions in predictable ways [Komanduri et al. 2011], or pick weaker passwords due to user-fatigue [Clair et al. 2006;Kruger et al. 2008].
In this paper, we initiate the algorithmic study of password composition policies. Such policies restrict the space of passwords to a subset of allowed passwords, and force each user to pick a password in this subset. Thus, n users induce a distribution over passwords where for a password w, Pr[w] = 1 n |{i : i picks w}|. By declaring different subsets of allowed passwords, different password composition policies induce different distributions. Our work formalizes and addresses the algorithmic problem a server administrator faces when designing a password composition policy; we ask: In what settings can the information about the users' preferences over passwords allow us to design a password composition policy that is guaranteed to induce a password distribution as close to uniform as possible?
We wish to stress at this point that we do not take a cryptographic approach to the problem: we do not design a protocol aimed at amplifying a password's strength, nor do we rely on standard cryptographic assumptions or techniques in designing our password composition policies. Single-factor authentication does not defend against an attacker who learns about the most probable password from an external source. Furthermore, because password systems often allow users multiple attempts in entering their password, an attacker can make a small number of guesses with impunity. Therefore, we instead focus on the design and analysis of algorithms for optimizing the password composition policy's induced distribution over passwords, and in our theoretical results compare the performance of our algorithm to the optimal policy among exponentially many potential policies in the worst case.

Our Model
We study the algorithmic problem of optimizing password composition policies along multiple dimensions: the goal, the user model, and the policy structure. Goal. We focus on designing a policy that maximizes the minimum-entropy of the resulting password distribution. Specifically, we assume the server deals with n users, each picking a password from some space of passwords P that respects the server's password composition policy. These n passwords form a distribution over the domain of all allowed passwords and our goal is to minimize the probability of the most likely password. This is a natural goal (see Section 7), as opposed to maximizing the Shannon-entropy of the distribution, which for example is still high even if half the people choose the same password and the other half choose a password uniformly at random from P. From a security standpoint, the minimum entropy represents the fraction of accounts that could be compromised in one guess. For example, an adversary would be able to crack 0.9% of RockYou passwords [Imperva 2010] with only one guess. Alternatively, should the attacker attempt to break into only one account, the minimum entropy represents the likelihood that the account is compromised on the first guess. We also consider a slightly stronger goal of minimizing the fraction of accounts that could be compromised using k guesses, that is, the overall probability of the k most likely passwords [Boztas 1999]. User model. We consider two models for how users select passwords when presented with a password composition policy.
In the ranking model, each user has an implicit ranking over passwords, from the most preferred to the least preferred. Given a password policy, each user selects the highest-ranking password among those allowed by the policy. There is a distribution over the space of rankings that determines the fraction of users with each possible ranking. Note that for any password composition policy, such a distribution over rankings induces a distribution over the most preferred allowed passwords.
In the normalization model, there is a distribution D over the space of all passwords. This distribution tells us the likelihood that an unrestricted user would select a given password. Given a password composition policy, D induces a new distribution over the allowed passwords (which can be obtained by normalizing the probabilities under D of the allowed passwords). When we ban a password the fraction of users that prefer each allowed password grows; the natural interpretation is that users who preferred an allowed password still use that password, but users who preferred a banned password are redistributed among the allowed passwords according to the induced distribution.
As we show, the normalization model is strictly more restrictive than the ranking model: any distribution in the normalization model can be simulated in the ranking model, but there exist hardness results for the ranking model that do not hold for the normalization model. Policy structure. We consider the best policy that is restricted to manipulation of a given set of rules -each rule is simply a predefined subset of potential passwords. These rules are given to us as part of the problem (see Section 7 for a discussion of this point). If we interpret a rule as a subset of banned passwords (e.g., passwords shorter than seven characters), its complement (e.g., passwords of at least seven characters) can be interpreted as a subset of allowed passwords. As such, when we take the union of rules we get either a set of banned passwords (negative rules) or allowed passwords (positive rules); this is our password composition policy. While the distinction between the two cases may at first seem a mere technicality, it is in fact quite significant due to the following observation. If we ban the union of rules then in order to ban a password that was picked by too many users, we may ban any rule that contains this password. In contrast, if we allow a union of rules then in order to ban this password we must not allow any rule that contains it. In other words, when our goal is to discard a password in the negative rules setting, we have multiple ways to do so. When our goal is to discard a password in the positive rules setting, we have only one way to do so -excluding all rules that allow this password. As we shall see, this seemingly small difference leads to a clear separation between the two scenarios in terms of the complexity of designing optimal policies.
We pay special attention to the case where each password has its own singleton rule. In this setting, a policy can be interpreted as a "blacklist" of banned passwords that do not necessarily share common characteristics. Note that when each password has its own singleton rule, it does not matter whether these rules are positive or negative.

Our Results
As we noted above, a password composition policy induces a distribution over most preferred passwords (in both user models). Hence we can study algorithms that sample these distributions. One can obtain such samples by asking random users to choose a password that is constrained by a certain policy. Clearly, though, we need the number of samples to be "small". The size of the space of all passwords P -which we denote by N -is typically very large (e.g., P can include all passwords that are no longer than 32 ASCII characters). We wish to maximize entropy using a number of samples that does not depend on N . Before tackling this goal directly, we study the problem in a simpler setting where the preferences of all users are given to us as input (i.e., there is no uncertainty). In particular, here P is a part of the input and algorithms are allowed to run in time polynomial in N . The computational complexity of problems in this setting informs their study in the sampling setting: it is hopeless to design efficient sampling algorithms for problems that are computationally hard, but computationally tractable problems may (or may not) have efficient sampling algorithms. Table I summarizes our complexity results. The parameter k refers to our optimization target: minimizing the likelihood of the k most likely passwords. Some results are direct corollaries of others -using the fact that singleton rules are a special case of positive rules and the fact that the normalization model is a special case of the ranking model (see Section 2). Looking at the table one immediately notices a clear separation between negative rules and positive rules: optimization using the latter is much easier.
We therefore focus on positive rules in our attempt to design an efficient sampling algorithm. Our main result is the best one could hope for in this setting. We design an algorithm that works in the more general ranking model, and finds a policy whose entropy is ǫ-close to optimal with probability 1 − δ, for any given ǫ, δ > 0. The required number of samples is polynomial in 1/ǫ, log(1/δ), and the number of positive rules m. We can assume that m is small, because each rule corresponds to a subset of passwords that can be concisely described to users.
These results can be applied in a practical setting, and we show this through simulated sampling experiments using natural rules and a large dataset of real passwords. The experimental results provide evidence for the difficulty of the negative rules setting: we search all combinations of rules to find the optimal policy and then attempt to discover this policy by making decisions both randomly and with a heuristic. In the negative rules setting, neither approach succeeded at finding the optimal policy after hundreds of iterations at various sample sizes, and average-case performance did not improve with sample size. In the positive rules setting, the average-case performance of our efficient algorithm improved with sample size and, with a moderate sample size, found policies that were either optimal or very close to optimal.

Related Work
It has been repeatedly demonstrated that users tend to select easily guessable passwords [Imperva 2010;Doel 2012;Bonneau 2012] and NIST recommends that organizations "should also ensure that other trivial passwords cannot be set," to thwart potential attackers [Scarfone and Souppaya 2009]. Unfortunately, this task is more difficult than it might appear at first. Policies were initially developed without empirical data to support them, since such data was not available to policy designers [Burr et al. 2006]. When hackers leaked the RockYou dataset to the Internet, both researchers (and attackers) suddenly had access to password data, leading to many insights into true passwords [Weir et al. 2010]. However, recent research analyzing leaked datasets from non-English speakers, notably Hebrew and Chinese-language websites, shows that trivial password choices can vary between contexts, making a simple blacklist approach ineffective [Bonneau and Xu 2012]. This means that, depending on the context, a policy based on leaked password data might provide no security guarantee, and it has ethical issues as well.
To combat this issue, researchers have turned to a sampling approach. Bonneau [2012] added a system for sampling to the Yahoo! password infrastructure. This system allows one to gain empirical data about the frequency distribution of passwords without revealing the passwords themselves. Such approaches provide a way of gathering empirical data about passwords while maintaining the anonymity of users. Our algorithms could be used in conjunction with such an infrastructure to optimize policies. Komanduri et al. [2011] studied the effectiveness of several basic password composition policies by using Amazon's Mechanical Turk to conduct a large scale user study. They found that people often respond to restrictions in predictable ways (e.g., if the password needs to contain a capital letter users might tend to capitalize the first letter of a password) and provide very general recommendations for password composition policies. However, no theoretical model has been proposed for studying the password composition problem. Schechter et al. [2010] suggest using a popularity oracle to prevent individual passwords that have been used too frequently from being selected by new users. They also proposed using the count-min sketch data structure [Cormode and Muthukrishnan 2005] to build such a popularity oracle. Malone and Maher [2012] suggest a similar system using a Metropolis-Hastings scheme to force an approximately uniform distribution on passwords. Usability results on the effectiveness of dictionary checks [Komanduri et al. 2011] suggest that such policies would be very frustrating since the policy is hidden from users behind an oracle. In contrast, we seek to construct optimal policies from combinations of rules that are visible to the user and can be described in natural language.
This consideration of users is important to electronic commerce, even where security is concerned. Florencio and Herley [2010] studied the economic factors that drive institutions to adopt strict password composition policies and find that they often value the user experience over security. An e-mail provider like Yahoo! might adopt simple composition policies because a frustrated user could easily switch to Gmail, while universities are free to adopt strict policies because users cannot switch easily.

A MODEL OF PASSWORD COMPOSITION POLICIES
We use P to denote the space of all possible passwords. N = |P| is used to denote the total number of passwords. We denote the number of users by n.
A password composition policy may be specified in terms of rules. A rule is a subset of passwords R ⊆ P (e.g., the set of all passwords with more than seven characters). We use R 1 , ..., R m to denote a list of rules that may be active or inactive. We consider two schemes.
-Positive Rules: A password w is allowed if and only if it is allowed by some active positive rule. Formally, a password composition policy A S = i∈S R i is specified by a set S ⊆ [m] = {1, ..., m} of active rules. In this setting rules should consist of sets of passwords which we expect to be strong (e.g., R i might be the set of all passwords longer than 10 characters, or the set of all passwords that use both upper and lowercase letters, or the set of all passwords that do not include a dictionary word). -Negative Rules: A password w is allowed if and only if it is not contained in any active negative rule. Formally, a solution A S = w ∈ P w / ∈ i∈S R i is given by a subset S ⊆ [m] of active rules. A negative rule should consist of passwords that we expect to be weak (e.g., R i might be the set of all passwords without an uppercase letter, or the set of all passwords shorter than 6 characters, or the set of all passwords that include a dictionary word).
We also consider the special case of singleton rules, where our rules are {w 1 }, . . . , {w N }. Equivalently, we are allowed to ban or allow any individual password.
We use Pr[w A] to denote the probability of a password w given composition policy A. For w / ∈ A we have Pr[w A] = 0. Given a set W ⊆ A we will also use Pr to denote the probability of the k most popular passwords. Intuitively, p (k, A) represents the probability that an adversary can successfully guess a password using k attempts. To avoid cumbersome notation we sometimes use p 1 = p (1, A) to denote the probability of the most popular password. Similarly, we use p 2 (resp., p k ) to denote the probability of the second (resp., k'th) most popular password.
We consider two user models that determine how users choose passwords under a given password composition policy.
-The ranking model: A ranking is simply a permutation of P, which represents a user's password preferences. It can be represented using an ordered list ℓ i = w 1,i , ..., w N,i ; user i prefers password w j,i to w j+1,i for all j. The ranking ℓ i naturally tells us which password i will pick under any composition policy A. Specifically, i will use password w A,i = w j,i where j = argmin{t : w t,i ∈ A}. Given a distribution D over rankings, we have -The normalization model: Let D be an initial distribution over P, and let Pr [w] = Pr x∼D [w = x]. If we select the composition policy A then the probabilities of all w ∈ A are simply re-normalized so that Clearly it holds for both models that the probability of an allowed password monotonically increases as one bans more passwords. Formally, for all w ∈ A and B ⊆ P such that w / ∈ B we have Another important observation is that for our purposes the ranking model is more general than the normalization model. Indeed, we argue that a distribution D over passwords in the normalization model induces an equivalent distribution over rankings. To generate the most highly ranked password, draw a password w 1 from D. Next, let A 1 = P \ {w 1 }, and draw the next most preferred password w 2 , where w 2 = w with probability Pr[w |A 1 ]. In the following round we ban w 2 to obtain a policy A 2 , and so on, until all passwords have been banned. Given then we say that S is a (c, ǫ)-approximation. To simplify notation we sometimes use c-approximation instead of (c, 0)-approximation.

RANKING MODEL: COMPLEXITY RESULTS
In this section we consider the complexity of finding the optimal password composition policy in the more general ranking model when the organization is given complete in-formation about users' preferences. Specifically, the organization is given the rankings ℓ 1 , ..., ℓ n of every user.
Our first result is for the positive rules setting. Given positive rules R 1 , ..., R m we show that p (k, A S ) can be computed efficiently for constant values of k (see Theorem 3.2). In fact, for the special case k = 1 we present a very simple algorithm that suffices. Both algorithms can be easily extended to the less general normalization model. Our algorithms are based on three simple ideas: (1) Reduced Preference Lists -each preference list ℓ i can be efficiently reduced to a short (length ≤ m) preference listl i . (2) Guess and Check -start by guessing the 'structure' of the optimal solution and find the resulting solution.
(3) Iterative Elimination -find the most popular password w and eliminate all positive rules that contain w. Our sampling algorithms are based on the same core ideas.
Unfortunately, the picture is different in the negative rules even when k is a constant. Given negative rules R 1 , ..., R m we show that it is hard to even n 1/3 -approximate p (1, A S ). Also, for non-constant values of k we show that it is hard to compute p (k, A S ) in the singleton rules setting, which immediately implies hardness in both the positive rules setting and in the negative rules setting. Given a stronger complexity assumption known as the Unique Games Conjecture [Khot 2002] it is also hard to c 0 -approximate p (k, A S ) in the singleton rules setting for some constant c 0 . However, our hardness results do not rule out the possibility of a c-approximation for a larger constant c.

Positive Rules: Efficient Algorithm for Constant k
We first show that p (k, A S ) can be computed efficiently for constant values of k in the positive rules setting. In this section the organization is given positive rules R 1 , ..., R m as well as preference lists ℓ 1 , ..., ℓ n . We assume that the organization can efficiently query the preference lists (e.g., given S ⊆ [m] the organization can efficiently find ℓ i (A S ) -user i's preferred password given policy A S ).
We elaborate on the key algorithmic ideas listed above. First, we can efficiently reduce each preference list ℓ i to a listl i of at most m passwords (Claim 3.1). While the reduced listl i is much shorter than ℓ i it is still sufficient to determine user i's preferred password given policy A S for any S ⊆ [m]. We useP to denote the reduced space of potential passwords.

Input:
⊲ Deactivate all rules that contain w i ← i + 1 returnl CLAIM 3.1. Algorithm 1 makes at most m queries to ℓ and m 2 membership queries and outputs a reduced preference listl over at most m passwords such that for every PROOF. Clearly, the algorithm's main loop iterates at most m times because for each i we eliminate at least one rule (e.g., |S i+1 | < |S i |), so the bound on queries and the length ofl are immediate. (Because we assume that we can query ℓ efficiently Algorithm 1 is also efficient.) By construction we havel(S i ) = ℓ(S i ) for each S i . Fix any S ⊆ [m]. Let S i be such that S ⊆ S i yet S ⊆ S i+1 and let w i be the most preferred word in ℓ out of all words in j∈Si R j . If it is the case that w i ∈ j∈S R j , then w i is the most preferred word in S too and we're done. Otherwise, w i ∈ j∈Si\S R j which means that removing the set {j ∈ S i : Second, the "guess and check" idea means that our algorithm starts by guessing what the optimal solution looks like (e.g., what the k most popular passwords will be in the optimal solution and what the probability of the k'th most popular password is). There are at most (mn) O(k) potential solutions to brute-force try. As we show, for each solution, it is easy to figure out which sets must be eliminated.

Input:
Preference Lists: ℓ 1 , ..., ℓ n Positive Rules: Candidates ← Candidates ∪ {S G,p } return arg min (G,p)∈Candidates p k, A SG,p THEOREM 3.2. Algorithm 2 runs in time polynomial in n k , m k and outputs a set of positive rules S ⊆ [m] of positive rules such that PROOF. It is evident that the running time of the algorithm is poly(n k , m k ) since we only have O((nm) k ) potential solutions to try.
Let A S * denote an optimal solution and let G * denote the k most popular passwords in this solution. Suppose we start with the correct guess (G = G * and p is the probability of the k'th most popular password), then we claim that our algorithm must produce the optimal solution. In particular, we maintain the invariant that A S * ⊆ A SG,p until we converge to the optimal solution. Clearly, this is true initially -before we have eliminated any passwords.
Suppose that the invariant holds and that our algorithm bans a password w ∈ P \ G by deactivating all rules in S G,p that contain w. Then by the definition of our algorithm we must have Pr w A SG,p > p. If w ∈ A S * then by Equation (1) we have which contradicts the choice of G. Therefore w / ∈ A S * , so all rules that contain it are deactivated in A S * and the invariant still holds. By definition Algorithm 2 terminates when every password w ∈ A SG,p \ G has probability at most p. Because our invariant still holds we can apply Equation (1) again to get Hence, A SG,p is an optimal solution.
For the special case k = 1 the simple algorithm IterativeElimination (Algorithm 3) suffices. The basic idea is very simple: iteratively eliminate the most popular password w by deactivating all positive rules that contain w. We repeat this process until no passwords remain. We claim that one of the solutions along the way was the optimal solution.

Input:
Preference Lists: ℓ 1 , ..., ℓ n Positive Rules: PROOF. Let T denote the optimal policy. Clearly if T = [m] then our algorithm returns S * = T because that is the first set we try. Otherwise, T [m]. Let S be the last set our algorithm considers that has the property that T ⊆ S. Again, if T = S, our algorithm returns S. Let w(T ) be the most popular word in A T , and because of optimality Now, because we modify S to not contain T in the next iteration, then the most popular word in S, w(S) has to belong to some rule R j where j ∈ T . Therefore w(S) ∈ j∈T R j , and by the definition, the most popular word in But observe, because w(S) ∈ j∈T R j , we must have that w(S) is at least as popular in T . Indeed, if ℓ is a preference list where we disallowed P \ j∈S R j and the most preferred word is w(S), then as long as we disallow more words but keep allowing w(S) the word w(S) remains at the top of the list. Therefore, Combining together all inequalities we get Pr[w(T ) | A T ] = Pr[w(S) | A S ], which means our algorithm returns S * = S.

Singleton Rules: Hardness for Large k
Now we turn our attention to the problem of optimizing p (k, A S ) for large values of k. Theorem 3.4 says that unless P = N P no polynomial time algorithm can compute p (k, A S ) even with singleton rules. If we are willing to make the Unique Games Conjecture (UGC) [Khot 2002] then it is hard to even c 0 -approximate p (k, A S ) for some constant c 0 . These results immediately imply hardness in both the positive and negative rules setting because these settings are a generalization of the singleton rules setting.
THEOREM 3.4. Unless P = N P there is no poly(k, n, N )-algorithm that gets as input an arbitrary set of n preference-lists ℓ 1 , ..., ℓ n over P and an integer k, and outputs the optimal p(k, A) in the singleton rules setting.
PROOF. We prove the theorem using a reduction from the Vertex-Cover problem. Given a graph G over g vertices and e edges and an integer t, we first define and observe that |P| = g + e. We also construct the following n = 2e preference-lists, where for every edge (u, v) ∈ E(G) we have the two lists: where the choice of passwords below position 2 is arbitrary, but both rankings must be identical from position 2 onwards. Finally, we set k = g + e − t − 1.
Given a policy A ⊆ P, we denote all banned words as B = P \ A. We denote by L B as the set of words that at least one user ranks first after banning all words in B. Observe, L ∅ = {w u : u ∈ V (G)}. Using this notation, we show this reduction indeed proves N P -hardness.
First, suppose G has a vertex cover C of size ≤ t. Then by banning all passwords B = {w v : v ∈ C} we now have L B = P \ B, because for every (u, v) ∈ E(G) either w u or w v are banned, so the word w u,v appears at the top of at least one of the two lists {ℓ u,v , ℓ v,u }. Therefore, the n preference-lists induce a distribution whose support contains g + e − |B| ≥ g + e − t words, thus p(g + e − t − 1, A) < 1.
Conversely, suppose all vertex covers of G are of size at least t+ 1. Let A be any set of banned words. Clearly, if |B| ≥ t + 1 then the distribution induced by the n preferenceslists has support of size at most g + e − t − 1, which means that p(g + e − t − 1, B) = 1. Otherwise, |B| ≤ t, and we denote the set of vertices C = {v : w v ∈ B}. Observe, since any vertex cover of G must contain ≥ t + 1 vertices, then there has to be at least t + 1 − |C| edges that C does not cover (since we can always complete C to a vertex cover by adding one vertex from each uncovered edge). Therefore, there have to be at least t + 1 − |C| words that do not appear at the top of any preference list. We conclude that the distribution induced by the n preference-lists has a support of size at most From the same reduction described in Theorem 3.4 we get U GC-hardness of approximation. While there are sub-exponential time algorithms to solve the Unique Games problem [Arora et al. 2010], there are no known polynomial time algorithms. Many famous approximation hardness results are based on the Unique Games Conjecture (e.g., 2 − ǫ hardness for vertex cover [Khot and Regev 2008]). Our reduction relies on a result in [Austrin et al. 2011], which says that vertex cover is hard to approximate up to a (say) 1.5-factor even on bounded degree graphs. Because we start with a bounded degree graph we can argue that each password in our reduction appears at the top of at most d preference-lists for some constant d. See the appendix for a formal proof. THEOREM 3.5. There exists a constant c > 1 such that it is U GC-hard for a poly(n, N, k)-time algorithm to c-approximate the optimal p(k, A) in the singleton rules setting and the rankings model.

Negative Rules: Hardness of Approximation for k = 1
We next turn to negative rules, where we show that the problem is extremely difficult even for k = 1. Though the proof appears in the appendix, it is quite interesting and we encourage the reader to take a look.
THEOREM 3.6. Let ǫ > 0. Unless P = N P there is no polynomial time algorithm (in N, n, m) that approximates min S⊆[m] p(1, A S ) to a factor of n 1/3−ǫ in the negative rules setting and the rankings model.

NORMALIZATION MODEL: COMPLEXITY RESULTS
In this section we focus on complexity results for the normalization model. Here the structure of the input to our problem is a bit different: For each password w ∈ P we are given the probability Pr[w] that w is selected by a random user when A = P. Note that now we can give the distribution explicitly because it requires N numbers (whereas a distribution over rankings requires N ! numbers). This distribution induces a distribution over P for any password composition policy A by normalizing probabilities, as explained in Section 2.
Because the normalization model is a special case of the ranking model our algorithms for the ranking model can also be applied in the normalization model. The question is whether or not the hardness results carry over.
We first consider the singleton rules setting with large k, and show that that we can compute arg min A⊆P p (k, A) in polynomial time in N (Theorem 4.1). This result separates the normalization model from the ranking model (e.g., compare Theorems 4.1 and 3.4). However, it does not extend to the positive rules setting. In fact, we show that optimizing p (k, A S ) is NP-Hard when k is a parameter (Theorem 4.4).
With negative rules R 1 , ..., R m we show that it is hard to c 0 -approximate arg max S⊆[m] p (1, A S ) (Theorem 4.2). However, we cannot rule out the possibility of an efficient c-approximation algorithm for some constant c in the normalization model (recall that Theorem 3.6 ruled out the possibility of a c-approximation algorithm in the ranking model for any c).

Singleton Rules: Efficient Algorithm for large k
We present SortAndOptimize -an efficient algorithm to optimize p (k, A) in the singleton rules setting for any value of k. The key intuition behind our algorithm is that if w 1 ∈ P is the most likely password then w 1 will remain the most likely allowed password unless we ban it -a property that does not hold in the rankings model. A formal proof of Theorem 4.1 can be found in the appendix.

Negative Rules: Hardness for k = 1
We next prove an inapproximability result that is somewhat weaker than the one that we obtained for the more general ranking model.

Input:
Password space P and a probability distribution over P. Integer k. Sort the words in P from highest to lowest probability, w 1 , w 2 , . . . , w N . return the set A i = {w j : j ≥ i}, where i minimizes the ratio THEOREM 4.2. There exists some constant c 0 > 1 such that unless N P = BP P no polynomial time algorithm (in n, N, m) can c 0 -approximate min S⊆[m] p (1, A S ) in the negative rules setting and the normalization model.
We will require the following construction; the proof is given in the appendix. That is, each set in this family contains exactly the same fraction of the domain, and furthermore -any union of |C| ≤ s sets has the property that its cardinality is proportional to Ω(|C|)|F i |.
PROOF OF THEOREM 4.2. We reduce from Set-Cover -one of the classic N P -Complete problems [Karp 1972]. We are given sets S 1 , ..., S m ⊆ U , universe U = {1, ..., g}, and an integer t ≤ m, and we are asked whether there is a set C ⊆ [m] of size ≤ t such that U = i∈C S i .
It is a known fact that there exist Set-Cover instances, with (g, m, t) all polynomially dependent of each other, that are hard to approximate to a factor of c ln n [Alon et al. 2006]. That is, on this particular family of instances, it is N P -hard to distinguish whether there exists a cover of size t or all covers have size (1 − ǫ)c · t ln n.
We now describe the reduction. Given a (g, m, t)-Set Cover instance, we set s = c · t ln g = Θ(t ln t) and construct a domain D and m sets F 1 , F 2 , . . . , F m ⊆ D as in Lemma 4.3. We then create the following password-banning instance. First P is the union of D with additional disjoint g words denoted w 1 , ..., w g . Now, for each set S i in the Set-Cover we add a rule R i where R i = {w j } j∈Si ∪ F i . Finally, we set the words' probabilities as follows. Fixing some arbitrarily small δ > 0, we set for every i the probability Pr[w i ] = 1−δ g , and for every x ∈ D we set the probability Pr[x] = δ |D| . Without loss of generality we can assume that |D| ≥ 100g (because, for example, we can take 100g copies of the original D). Therefore, any policy that bans all of {w 1 , w 2 , . . . w g } yet leaves a constant (say > 1/10) fraction of D has p 1 ≤ 10/|D|, whereas any policy that keeps even one of the words in {w 1 , w 2 , . . . , w g } has p 1 ≥ 1/(2g). Therefore, if the Set-Cover instance has a cover of size ≤ s = Θ(t ln g), then a c 0approximation of the optimal banning-policy must find a cover for {w 1 , w 2 , . . . , w g }. We will assume from now on that our Set-Cover instance is such that it has a cover of size ≤ s. (Indeed, if s > t log(t) then the instance is no longer N P -hard, since the greedy algorithm must return a cover of size > t log(t) which causes us to deduce that the optimal cover must have size > t.) So now, suppose our Set-Cover instance has a cover of size t. Then the respective union of rules bans every password in {w 1 , w 2 , . . . , w g } and no more than t 2s |D| words of D (we get an upper bound by multiplying the size of each set by the number of sets). This leaves a collection of 1 − t 2s |D| equally likely words, so p 1 = 1 − t 2s −1 |D| −1 = (1 − O(1/ log(g))) −1 |D| −1 = (1 + o(1))|D| −1 . In contrast, if all covers of our Set-Cover instance have size s ′ ≥ c·t ln(g) (where, because we assume some cover has size ≤ s, we have s ′ ≤ s,) then any collection of rules that bans all words in {w 1 , w 2 , . . . , w g } must also ban at least s ′ 8s |D| words out of D. This leaves at most (1 − Ω(1))|D| words in D and so p 1 ≥ (1 − Ω(1)) −1 |D| −1 . Denoting the latter constant as c −1 0 , we have that any c 0 − ǫ approximation of the optimal banning-policy indicates the existence of a cover of cardinality < c · t ln(g).

Positive Rules: Hardness of Approximation for Large k
While we can show that it is possible to optimize p (k, A) in the singleton rules setting our result does not extend to the more general positive rules setting. We are able to show that it is NP-Hard to compute arg min S⊆[m] p (k, A S ). However, our reduction does not imply approximation hardness so we cannot rule out the existence of a PTAS. The theorem's proof is relegated to the appendix.

EFFICIENT SAMPLING ALGORITHMS
In a sense, our complexity results are not "realistic", and in particular in the ranking model our positive algorithmic results assume access to each user's full preferences. Moreover, some algorithms are allowed to run in polynomial time in the number of passwords N , which can be huge. In this section we use our complexity results as guidelines in the design of practical sampling algorithms.
In more detail, we are given oracle access to rules R 1 , ..., R m (e.g., we can ask whether or not a password w ∈ R i ) and we are allowed to sample from the distribution induced by the password composition policy A S for any S ⊆ [m]. Less formally, a sample is equivalent to asking a random user what her favorite password is given the current policy.
We will work in the more general ranking model, so there is essentially only one positive result we can build on: Theorem 3.2, a polynomial time algorithm for constant k in the positive rules setting. When adapting this algorithm to the sampling setting, we cannot expect it to work perfectly due to the inherent uncertainty of this domain. Instead we expect the algorithm to find an ǫ-optimal password composition policy with probability at least 1 − δ, for any given ǫ and δ. Crucially, the number of samples must not depend on the number of passwords N , and must have a polynomial dependence on the other parameters.
Formally, we let S * ⊆ [m] denote the optimal collection of positive rules to activate We first present Algorithm 5 that achieves our goal for k = 1; this algorithm is an adaptation of Algorithm 3.

PROOF. Let
denote the event that our probability estimates are off during iteration i. Claim 5.2 bounds the probability of any bad event. The proof of Claim 5.2 can be found in the appendix. The proof involves bucketing the passwords based on their probability, applying Chernoff Bounds to upper bound the probability of a bad estimate for our passwords in each bucket, and repeatedly applying union bounds.
For the rest of the analysis we assume that no bad event occurs. Let p * = min S⊆[m] p (1, A S ) and suppose that A S * ⊆ A Si . Clearly, this is true when i = 0. If p i ≥ ǫ/2 + p * then Pr [w * A S * ] ≥ Pr [w * A Si ] > p * so that w * / ∈ A S * . Hence, A S * ⊆ A Si+1 and the property is maintained for at least one more iteration. If insteadp i < ǫ/2 + p * then we havep i * ≤p i ≤ p * + ǫ/2 so for each w ∈ A S i * we have Pr [w A S i * ] ≤ p * + ǫ. We conclude that the solution S i * is a (1, ǫ)-approximation.
We next explain how to extend Algorithm 2 to (1, ǫ)-approximate the optimal p (k, A S ) for any constant k. PROOF SKETCH. To extend Algorithm 2 to (1, ǫ)-approximate p (k, A S ) for constant k we need one more idea. We cannot simply obtain a reduced password spaceP by reducing preference lists because we can only sample from our distribution. Notice that for any S ⊆ [m] such that i ∈ S we have Pr [w A S ] ≤ Pr w A {i} so to obtain a (1, ǫ)-approximation it is sufficient to limit our attention to passwords in the following setP We can obtain a superset ofP by sampling. For each positive rule R i we draw s independent samples from the distribution A {i} and set Intuitively, a password w is included in T i if and only if our estimated probability is sufficiently large. Let T = i T i . For a sufficiently large sample size s = O (poly (m, k, 1/ǫ, 1/δ)) we can apply Chernoff Bounds to argue that with probability 1 − δ (1) |T | is small, i.e., O (poly (m, k, 1/ǫ, 1/δ)), and (2) T ⊃P .

EXPERIMENTS
To demonstrate how our ideas could apply in a real-world scenario, we simulated runs of Algorithm 5 by sampling with replacement from the RockYou leaked password set [Imperva 2010]. The set contains over 32 million passwords with a frequency distribution similar to that of many other password sets [Bonneau 2012]. Note that all results presented here are limited by the dataset and assume the normalization model. Working in the normalization model is crucial because we cannot ask the Rock-You users for their preferred password under a specific policy; an initial distribution over P -which is available to us -is sufficient though, because it induces a distribution for any policy A.
We selected 21 positive rules that mirror commonly used password composition rules that are used in practice, and looked at sample sizes s of 100, 500, 1000, 5000, and 10000. The rules included length requirements, character class requirements, combinations of requirements, a dictionary check, etc. (See Appendix C for a complete listing of the rules we selected.) For each run with a particular value of s, the algorithm returns a policy A S for which we can measure p (1, A S ) in the original dataset and compare with the optimal p (1, A S * ), determined from running Algorithm 3 on the original dataset. We performed 500 runs for each of the five values of s.
To gain an understanding of how policies based on negative rules perform, we took the complement of the 21 positive rules selected above to get 21 negative rules. We then determined the optimal negative rules policy by calculating S * = arg min S⊆[m] p (1, A S ) via brute-force. This was required because we have no equivalent to Algorithm 3 for negative rules. With this baseline in hand, we designed two naïve algorithms, similar in spirit to Algorithm 5. There are multiple ways to discard a password in the negative rules setting, and one algorithm makes this decision randomly while the other bans the smallest subset as determined from the current sample. Again, 500 runs were performed for each s ∈ {100, 500, 1000, 10000, 50000}.

Baselines
We examined several baselines for comparison with our algorithm. Table II shows these baselines, the probability of the most frequent password in the resulting policy, and the optimal policy as a union or intersection of rules (for clarity, the complement of the union of negative rules is shown as the intersection of positive rules). As shown in Table II from the means across policies, randomly selecting a policy from the power set of rules can be worse than having no policy. The "one rule maximum" baseline was selected because, if decided based on sampling, only m distributions need be sampled. Our efficient algorithm requires the same amount of sampling, but can find the optimal policy over S ⊆ [m] rather than S ∈ {1, ..., m}. Also of interest is the optimal policy with negative rules, which is over 3x better than the optimal policy with positive rules. However, as shown in the following section, the performance of our sampling algorithms with negative rules was far worse than in the positive rules setting.

Performance
In the positive rules setting (see Table III), the algorithm performed extremely well even at moderate sample sizes. The average policy selected with s = 500 was almost 10x better than having no policy. At s = 1000, the optimal policy was found 10% of the time (50 out of 500 times).
In the negative rules setting (see Table IV), however, neither algorithm found the optimal policy. The "Ban Smallest" heuristic, when faced with a choice between multiple subsets that contain the most likely password, decides to ban the smallest available subset, disrupting the space the least. This might seem like an intuitively good choice but, in fact, it fails to find a better policy than the empty set at large sample sizes. The randomized algorithm does better (it cannot actually do worse) but still has much worse average case performance than using our efficient algorithm with positive rules.

DISCUSSION
We conclude by discussing some key points.
Where do the rules comes from? Throughout the paper we have assumed that the rules (whether positive or negative) are given as part of the input; it is not up to us to find these rules. Our experiments indicate that a collection of intuitive and practical rules can already give very good results on real data. However, the question of deciding which rules should be added to our collection is outside the scope of this paper. Much like the problem of feature selection, it is an interesting problem with real-life implications, which we suspect will be very difficult in practice.
Alternate policy goals. Our goal [Boztas 1999] has been to minimize p (k, A S ). Intuitively, p (k, A S ) represents the probability that an adversary with no background knowledge can successfully guess the password of a randomly selected user in k tries. A small value of k optimizes security guarantees against an online guessing attack in which the adversary is locked out after k failed attempts to login. A much larger value of k (e.g., 2 32 ) is necessary to optimize security against an adversary who has obtained the cryptographic hash of a password and is able to mount a brute-force dictionary attack [Seeley 1989]. However, the optimal solutions for p (1, A S ) and p 2 32 , A S might be completely different. One stronger goal that we might hope to achieve is to optimize both goals simultaneously. More formally, can we find a policy S ⊆ [m] such that for every S ′ ⊆ [m] and every k ≤ N we have p (k, A S ) ≤ c · p (k, A S ′ ) for some constant c?
Unfortunately, the answer is no. For any constant c this universal approximation goal is impossible to satisfy in the ranking model (see Theorem B.1).
Other natural goals include α-work factor [Pliam 2000] and a refinement called αguesswork [Bonneau 2012] (e.g., maximize the total number of guesses needed to compromise α-fraction of the accounts). While α-guesswork is an useful metric to analyze the security of 70 million Yahoo passwords [Bonneau 2012], it may not be a desirable optimization goal for the organization because it might allow the adversary to crack up to α − ǫ-fraction of the accounts with relatively few guesses.
Another interesting direction is to account for an adversary with basic background information about the user (e.g., e-mail address, username, birthday). It may not always be realistic to assume that the adversary has no background knowledge because the adversary can often easily obtain some background knowledge about a user by searching for publicly available information on the internet. One approach might be to design a rule R to specify different passwords for different users (e.g., the set of passwords that contain the username or birthday of the user).
Open Questions. While we were able to prove several hardness results about finding the optimal password composition policy in the negative rules setting, it is possible that these hardness results could be circumvented by making mild (hopefully realistic) assumptions about the underlying password distribution or the rules R 1 , ..., R m . Are there efficient algorithms to optimize p (k, A S ) in the negative rules setting given realistic assumptions? It is also possible that mild realistic assumptions could be used to circumvent the impossibility result of Theorem B.1, and design a universal approximation algorithm.
There are also several interesting technical questions that remain open: (1) Normalization model with negative rules: Can we efficiently c-approximate p (1, A S * ) for any constant c? Is there a sub-exponential algorithm (in m) to compute p (1, A S * )?
(2) Ranking model with positive rules: Can we efficiently c-approximate p (k, A S * ) for some constant c when k is a parameter?
The future. There is a real need for a principled approach to optimizing password composition policies. We have taken a first step in this direction by providing an intuitive theoretical model and showing that it leads to algorithms that perform well on real data. We can only hope that our work will spark a fundamentally new interaction between theory and practice in passwords research.

Reminder of Theorem 3.5.
There exists a constant c > 1 such that it is U GC-hard for a poly(n, N, k)-time algorithm to c-approximate the optimal p(k, A) in the singleton rules setting and the rankings model.
Proof of Theorem 3.5. We begin with a construction of a bounded degree graph which is hard approximate up to a (say) 1.5-factor. As shown in [Austrin et al. 2011], for every constant d there exists a family of d-regular graphs for which it is U GC-hard to determine whether there exists a vertex cover of size t, or all vertex-covers have size at least (2 − O(log log(d)/ log(d)) − ǫ) t. Fixing d to be a large enough constant such that this factor is > 1.5, we now reduce this family of instances to a password problem using the exact same construction as in the proof of Theorem 3.4, with the exception that we set k = g + e − (1.5 − ǫ)t.
Observe, for this family of instances, e = O(g) so |P| = O(g), but also the size of the optimal vertex-cover has to be Θ(g) (at most g and at least g/d). Furthermore, each password appears at the top of at most d preference-lists. Therefore, by allowing A and banning B = P \ A, we not only have a distribution whose support is of size |L B |, but it also holds that the probability of each word in L B is Ω(1/|L B |).
Therefore, if the graph has a vertex-cover C of size t, then by banning all words B = {w u : u ∈ C} we have that the n preference-lists induce a distribution over |L B | ≥ g + e − t. Since we set k = g + e − (1.5 − ǫ)t we have that the set of most uncommon passwords contain at least (0.5 − ǫ)t = Ω(|L B |) words, each with Ω(1/|L B |) probability, thus p(k, A) = 1 − Ω(1). (And, in particular, for the optimal policy A * we have p(k, A * ) = 1 − Ω(1).) In contrast, applying the same argument from the proof of Theorem 3.4, we have that if G has all vertex-covers of size > (1.5 − ǫ)t then p(k, A) = 1. The O(1)-hardness of approximation follows. ✷ Reminder of Theorem 3.6. Let ǫ > 0. Unless P = N P there is no polynomial time algorithm (in N, n, m) that approximates min S⊆[m] p(1, A S ) to a factor of n 1/3−ǫ in the negative rules setting and the rankings model.
Proof of Theorem 3.6. Fix ǫ > 0. Our reduction is from the Max-Independent-Set problem, which is known to be hard to approximate up to a factor of n 1−ǫ [Håstad 1996]. We are given a graph G with g vertices and e edges, and we must determine whether the size of G's largest independent set is g 1−ǫ or g ǫ . Given a Max-Independent-Set instance, we denote K = g ǫ and create the following password policy instance, which is composed out of the following set of possible words: We now describe the n = g + ge + g 2 K 2 ≤ g 3 + g 2+2ǫ users' preference-lists. We start with the g rankings specified in Table V(a). We continue with ge more rankings, where for each edge (u, v) ∈ E(G) we add g more rankings, as detailed in Table V(b). Lastly, we add g 2 K 2 more rankings, where for each triple (v, i, j) where v is a vertex of G and i = j ∈ [K] we add g rankings, as detailed in Table V(c). (Observe, the tables detail the first few words in each list, then end with ". . ." mark, which indicates that from that point on the remaining words may appear in any order.) Finally, we detail our rules. For every i ∈ [K] and u ∈ V (G) we have a rule which roughly corresponds to deciding that u is a member of the independent set: Our analysis now follows from a series of observations.
Observation 1: If we do not ban all of the passwords A 1 , ..., A K then p 1 ≥ g/n. Therefore, for every i, we must choose at least one of the rules {R u,i } to activate, or else we have that p 1 ≥ g/n Observation 2: If we ban C v u,1 , . . . , C v u,g and C u v,1 , . . . , C u v,g then we must have p 1 ≥ g/n. Therefore, for any i = j it must not be the case that we ban R u,i and R v,j where (u, v) ∈ E(G), or else we have that p 1 ≥ g/n.
Observation 3: If we ban D v,i,j,1 , . . . , D v,i,j,g , and D v,j,i,1 , . . . , D v,j,i,g then p 1 ≥ g/n. Therefore, for any i = j it must not be the case that we ban R u,i and R u,j , or else we have that p 1 ≥ g/n.
These observations lead us to the following conclusion. If G contains an independent set v 1 , ..., v K of size K, then activating the rules {R v1,1 , R v2,2 , . . . , R vK ,K } leads to a setting where each truncated ranking begins with a unique word, so p 1 = 1/n. In contrast, if G does not have an independent set of size K, then p 1 = g/n. Since n = O(g 3 ) we have an Ω(n 1/3 )-hardness of approximation. Observe also that the number of total words is N = K + g + 2eg + g 2 K(K − 1) + 1 = O(g 3 ) = O(n) so it is also hard to approximate the problem to a factor of Ω(N 1/3 ). Proof of Theorem 4.1. Let A * denote the optimal solution, denote its most k popular passwords as w i1 , . . . , w i k , and denote also P * as the total probability mass of the words in A * according to the initial distribution: Clearly, all words w j s.t. j > i k belong to A * -otherwise, we could add such a word and decrease the probability of the top k words. Similarly, all words w j s.t j < i 1 must not belong to A * , otherwise they would belong to the set of most popular k words. We now claim that w i1 , . . . , w i k are k consecutive words.
Suppose that there was some word w ′ between some w ij and w ij+1 . Then A * clearly banned it, otherwise it would be one of the most popular k words. We claim that the policy A ′ where we ban w i1 and allow w ′ instead satisfies p(k, A ′ ) ≤ p(k, A * ).
We denote p 1 = Pr[w i1 ], q = k j=2 Pr[w ij ] and p ′ = Pr[w ′ ], and we know p 1 ≥ p ′ . Then p(k, A * ) = (p 1 + q)/P * , whereas Our goal is to show p(k, A ′ ) ≤ p(k, A * ), which holds iff By some algebraic manipulations, this holds iff which clearly holds because p 1 − p ′ is a non-negative quantity, and p 1 + q = So assuming |C| ≥ 8 we have that C is mapped to at least |C|/2 distinct images by φ w.p.> 3/4. Also, if |C| ≤ 7 then probability of even two elements getting mapped to the same image is at most 7 2 1 2s < 0.25 for s > 42. We now construct D by taking d independently chosen such φ-mappings, which we denote as φ 1 , φ 2 , . . . , φ d , and so D = [2s] × [d]. We construct the family F i = {(φ 1 (i), 1), (φ 2 (i), 2), . . . , (φ d (i), d)} for every i ∈ [m]. Clearly, for every i it holds that |F i | = d = |D|/2s. Supposed for the sake of contradiction that there exists some C ⊆ [m] of size ≤ s such that i∈C F i ≤ |C| 4 |F i |. By construction, we have that |φ j (C)| so by the Markov inequality we have that at least d/2 functions where the cardinality of the image of C is less than |C|/2. Let X C,j be the indicator random variable of φ j Suppose that there is no set cover of size k. For every set of k or more rules S we have at least k t's in our solution so For every set of rules S that does not cover all the W i 's we have at most 1 − 1 n 1 − 1 n 3 -fraction of the total probability mass so Observe that a ≤ Pr[τ ] ≤ b so it suffices to set x s.t. Pr[t] = a+b 2 . We can solve for x to get x = m −3 + 2n + 2n 3 − 2n 4 + k (n − 1) 2 1 + n + n 2 m (−3 + 2n + 2n 3 − 2n 4 ) + k 2 (2 − 2n − n 3 + n 4 ) + k −2 + 4n + n 3 − 2n 4 + m (n − 1) 2 (1 + n + n 2 ) . ✷ Reminder of Claim 5.2. Pr [∃i, BAD i ] ≤ δ .
Proof of Claim 5.2. By the union bound it suffices to show that Our first step is to divide the passwords w ∈ P into buckets B j based on their probability. For j > 0 we define B j = w ǫ 2 j ≤ Pr [w A Si ] ≤ ǫ 2 j−1 , and for j = 0 we set Let w ∈ B j be given (j > 0) then by the Chernoff Bounds: Pr [s w > s Pr [w A Si ] + sǫ/2] ≤ exp −2 j−1 log 4m δǫ ≤ 4 −2 j−1 δǫ m .
Notice that the bucket B j contains at most |B j | = 2 j /ǫ passwords.

B. IMPOSSIBILITY OF CONSTANT-FACTOR UNIVERSAL APPROXIMATION
In this section we consider the following goal: given a constant c find a password composition policy A such that for any other policy A ′ and every value of k ≤ N . Such a policy -if it exists -would provide a nearly optimal defense against both online attacks and dictionary attacks simultaneously [Seeley 1989]. Unfortunately, Theorem B.1 rules out the possibility of a constant universal approximation in the rankings model. Our impossibility result holds even in the singleton rules setting. We show that it is possible to construct a distribution D over rankings for which no universal approximation exists. We construct our distribution D (algorithm 6) over rankings by merging two distributions D 1 and D 2 over preference lists.
Intuition: Passwords sampled from D 2 are highly secure, but passwords sampled from D 1 are highly insecure. To make improve the security of D 1 it is necessary to ban all passwords in W , but this reduces the security of D 2 significantly.
We make two claims (1) We must ban all but a small subset of passwords if we want to even approximately optimize p (1, A). (2) We must keep a larger subset of passwords to even approximately optimize p (k, A) for large values of k.
THEOREM B.1. For all constants c > 0 there exists distribution D over rankings such that ∀A ⊆ P, ∃A ′ , k ∈ N, such that p (k, A) > c · p (k, A ′ ) .

PROOF. (sketch) Let
. . , w i,t } -and X = {x 1 , . . . , x L } are two disjoint sets of passwords, where the parameters are set as follows q = 1 2c , t = L = log N and r = N −L t . Our distribution over preference lists is given by algorithm 6.

C. EXPERIMENT RULES
We selected rules based on common types of rules used in constructing password composition policies, e.g., the policies recommended by NIST [Burr et al. 2006]. The rules we selected are shown in Table VI. Positive and negative forms of each rule are shown. In the positive rules setting, a password is allowed if it matches any positive rule. In the negative rules setting, a password is banned if it matches any negative rule.
The dictionary check used the cracking dictionary from openwall.com. This dictionary is used by one of the most well-known password crackers, John the Ripper [Designer 2010]. Since this dictionary contains all alphabetic strings up to size 3, it was pruned to only include entries of 4 characters or more for the "contains a dictionary word" dictionary check.