More on Counting Restrictive Password Spaces

In a recent post I discussed how to use the Inclusion-Exclusion Principle (IEP) to count restrictive password spaces. In particular, the post considered how the number of passwords satisfying a restricted composition policy (at least one character that is lowercase L, uppercase U, numeric N, and a symbol S) reduced the size of the unrestricted password space (any combination of those character sets). In this post we will refer to this policy as ALO (at least one), and we examine the impact of two more restrictive policies using the same methods.

The first additional policy we consider is the Windows Server 2000/2003 (Win2KSvr) policy which requires at least 3 characters from the sets L, U, N and S. The second additional policy is from Sun and states that passwords must have at least 2 characters from L and U, as well as at least one character from N and S. The Win2KSvr policy is less restrictive than the ALO policy, while the Sun policy is substantially more restrictive than ALO.

For the impatient, the counting results are presented in the table below. For each password length n, 100% corresponds to (94)^n, denoting all possible passwords based on the 94 printable ASCII characters (26 uppercase characters, 26 lowercase characters, 10 numbers and 32 symbols). The numbers in the table denote reduction percentages of the password space due to the stated policy restrictions, and have been rounded to the nearest whole number.

Length	Win2KSvr	ALO	Sun
6	85	27	1
7	91	37	6
8	95	46	14
9	97	54	23
10	98	60	32
11	99	65	41
12	99	70	49
13	100	74	56
14	100	77	63
15	100	80	68
16	100	82	73
17	100	84	77
18	100	86	80
19	100	88	83
20	100	89	85
30	100	97	96
40	100	99	99
50	100	100	100

We see from the results that the Win2KSvr policy is not very restrictive when passwords are at least 6 characters (85% satisfy the policy), and at 8 characters, a common password length, 95% of passwords satisfy the policy. So this policy should not be very burdensome for users to follow. The Sun policy is very restrictive and is only satisfied by a mere 1% of length 6 passwords, and just 14% of length 8 passwords. Clearly users and administrators will need to make deliberate password selections to satisfy this policy.

These results may seem alarming, in that the restrictive policies are severely reducing the set of possible passwords. However we cannot assess the nature of the threat here without the full context. I would recommend to read Password Exhaustion: Predicting the End of Password Usefulness, a technical report from researchers at Pennsylvania State University, which provides an excellent review of password strength in the near future.

Read on to see how the numbers in the above table were calculated.

Using the IEP for counting

We are interested in counting the set of passwords that satisfy a given restrictive policy (filter). We will determine the size of the restrictive password set as follows:

1. Define a collection of sets whose union fully characterizes the set of passwords that do not satisfy the restrictive policy.

2. Use the IEP to compute the size of the union of the sets defined in Step 1.

3. Subtract the result from Step 2 away from the number of unrestricted passwords (the full password space).

Windows Server 2000/2003 Policy

As expected, we start by defining the sets for Step 1. If a password does not satisfy the Win2kSvr policy then characters from at least two of L, U, N or S must be missing (not selected by the user). Let LU be the set of passwords that do not contain lowercase or uppercase letters. Similarly define LN, LS, UN, US and NS as sets of passwords that do not contain characters from the two stated sets from L, U, N and S. It should be clear that if a password fails to meet the Win2kSvr policy then it must be a member of at least one of the 6 sets LU, LN, LS, UN, US or NS . Equivalently, the union of these 6 sets characterizes passwords that are constructed from at most two of the sets L, U, N and S. Thus we have completed Step 1.

To apply the IEP we must determine the size of intersecting these 6 sets taken individually, 2 at a time, 3 at a time and so on, up to 6 at a time. All in all there are 63 = 2^6-1 intersections to consider, but thankfully most of these intersections will have a size of zero.

To simplify notation, the intersection of LU and LN will be written as LUN, which denotes the set of passwords that do not contain a character from L, U or N (equivalently, the passwords must be all symbols). Similarly intersecting LU with NS will be denoted as LUNS and interpreted as a password that has no characters from L, U, N or S.

The LUNS set is empty as it is not possible to avoid all character sets, and therefore has size 0. It is easy to see that if we intersect 4 or more of LU, LN, LS, UN, US and NS then the intersection must be LUNS. Thus to compute the IEP we need only consider intersections of 3 or less sets. In the table below we show only the non-empty intersections.

Set	Intersection	Sign	Size
LU	LU	+	(94 - 26 - 26)^n
LN	LN	+	(94 - 26 - 10)^n
LS	LS	+	(94 - 26 - 32)^n
UN	UN	+	(94 - 26 - 10)^n
US	US	+	(94 - 26 - 32)^n
NS	NS	+	(94 - 10 - 32)^n
LU, LN	LUN	-	(94 - 10 - 32)^n
LU, UN	LUN	-	(94 - 26 -26 - 10)^n
LU, LS	LUS	-	(94 - 26 -26 - 32)^n
LU, US	LUS	-	(94 - 26 -26 - 32)^n
LN, UN	LUN	-	(94 - 26 -26 - 10)^n
LN, LS	LNS	-	(94 - 26 -10 - 32)^n
LN, NS	LNS	-	(94 - 26 -10 - 32)^n
UN, US	UNS	-	(94 - 26 -10 - 32)^n
UN, NS	UNS	-	(94 - 26 -10 - 32)^n
LS, US	LUS	-	(94 - 26 -26 - 32)^n
LS, NS	LNS	-	(94 - 26 -10 - 32)^n
US, NS	UNS	-	(94 - 26 -10 - 32)^n
LU, LN, UN	LUN	+	(94 - 26 -26 - 10)^n
LU, LS, US	LUS	+	(94 - 26 -26 - 32)^n
LN, LS, NS	LNS	+	(94 - 26 -10 - 32)^n
UN, US, NS	UNS	+	(94 - 26 -10 - 32)^n

We see from the table above that when LU, LN, LS, UN, US and NS are intersected in pairs then at least 3 of the underlying character sets (L, U, N, S) are included, or covered, by the intersection. Thus LUN, LUS, LNS and UNS are the only non-zero intersections produced by the IEP. For example, LUN is generated in the table 4 times from in the following intersections

• Either intersecting pairs from LU, LN, UN ,which can be done in the following 3 ways (LU, LN), (LU, UN) or (LN, UN), or
• Intersecting all three of LU, LN, UN, which can only be done in one way

So the contribution of LUN to the password count is the 3*Size(LUN) - Size(LUN) = 2*Size(LUN). The same observation is true of LUS, LNS and UNS. Thus the computations in the previous table can be simplified as follows

Intersection	Sign	Size
LU	+	(94 - 26 - 26)^n
LN	+	(94 - 26 - 10)^n
LS	+	(94 - 26 - 32)^n
UN	+	(94 - 26 - 10)^n
US	+	(94 - 26 - 32)^n
NS	+	(94 - 10 - 32)^n
2*LUN	-	2*(94 - 26 -26 - 10)^n
2*LUS	-	2*(94 - 26 -26 - 32)^n
2*LNS	-	2*(94 - 26 -10 - 32)^n
2*UNS	-	2*(94 - 26 -10 - 32)^n

The table describes the computations to complete Step 2 as outlined above, and to complete Step 3 we need only subtract this value from the total number of passwords which is (94)^n.

A Sun Policy

The Sun policy, as referenced by researchers at Pennsylvania State University, states that passwords must have at least 2 lowercase and uppercase characters, as well as at least one character that is numeric and a symbol. In our case the judicious choice of sets for Step 1 is

• L - the set of passwords that contain at most one lowercase letter

• U - the set of passwords that contain at most one uppercase letter

• N - the set of passwords that do not contain a number

• S - as the set of passwords that do not contain a symbol

The union of L, U, N and S is the set of passwords that has at least one of the four character sets missing, and this represents all passwords that do not satisfy the stated Sun policy. The tricky counting comes for L and U. L denotes passwords that have at most one occurrence of a lower case letter, which we decompose into the two cases of zero occurrences or exactly one occurrence. Counting zero occurrences is just (94 - 26)^n. To count exactly one occurrence in a length n password we first select the position where the lower case letter will occur (there are n such choices), then choose amongst 26 possible letters to assign in the position, and select the remaining n-1 characters to exclude lower case letters, which can be done in (94 - 26)^(n-1) ways. Thus there are

n*26*(96 - 26)^(n-1)

ways to have exactly one lowercase letter, and in total there are then

(94 - 26)^n + n*26*(96 - 26)^(n-1)

passwords with at most one lowercase letter. The same calculation applies to counting U. An trickier intersection case to count is LU, or passwords that have at most one occurrence of both L and U. The subcases are considered in the table below.

Occurrence of L?	Occurrence of U?	Size
No	No	(94 - 26 -26)^n
Yes	No	n*26*(96 - 26 -26)^(n-1)
No	Yes	n*26*(96 - 26 -26)^(n-1)
Yes	Yes	n*(n-1)*(26^2) *(94 - 26 - 26)^(n-2)

Give these calculations, it is not difficult to created the full intersection table for the IEP as shown below.

Intersection	Sign	Size
L	+	(94 - 26)^n + n*26*(96 - 26)^(n-1)
U	+	(94 - 26)^n + n*26*(96 - 26)^(n-1)
N	+	(94 - 10)^n
S	+	(94 - 32)^n
LU	-	(94 - 26 -26)^n + 2*n*26*(96 - 26 -26)^(n-1) + n*(n-1)*(26^2)*(94 - 26 - 26)^(n-2)
LN	-	(94 - 26 -10)^n + n*26*(96 - 26 - 10)^(n-1)
LS	-	(94 - 26 -32)^n + n*26*(96 - 26 - 32)^(n-1)
UN	-	(94 - 26 -10)^n + n*26*(96 - 26 - 10)^(n-1)
US	-	(94 - 26 -32)^n + n*26*(96 - 26 - 32)^(n-1)
NS	-	(94 - 10 - 32)^n
LUN	+	(94 - 26 - 26 - 10)^n + 2*n*26*(96 - 26 - 26 -10)^(n-1) + n*(n-1)*(26^2)*(94 - 26 - 26 - 10)^(n-2)
LUS	+	(94 - 26 - 26 - 32)^n + 2*n*26*(96 - 26 - 26 -32)^(n-1) + n*(n-1)*(26^2)*(94 - 26 - 26 - 32)^(n-2)
LNS	+	(94 - 26 - 10 -32)^n + n*26*(96 - 26 - 10 - 32)^(n-1)
UNS	+	(94 - 26 - 10 -32)^n + n*26*(96 - 26 - 10 - 32)^(n-1)
LUNS	-	0

The table describes the computations to complete Step 2 as outlined above, and to complete Step 3 we need only subtract this value from the total number of passwords which is (94)^n.

Counting Restricted Password Spaces

(A second post on this topic - May 29, 08)

I came across an August 2007 post from Bruce Marshall in the Password Research blog where he was considering the following issue:

A recent discussion on a SecurityFocus.com mailing list raised a concern about password policies that I hadn't previously given much thought to. The post author commented that he wanted to enforce a policy that required passwords to have lowercase, uppercase, number, and symbol characters. By this he meant every password must have at least one character from each of these characters sets. One reader responded that by requiring the use of all four character sets he would reduce the total number of possible passwords, causing a negative impact on password security.

The concern here is that the security implied by a large password space (the set of all possible passwords) can be significantly reduced by restricting the actual set of passwords that can be chosen by a user through additional character composition requirements. To understand the implications we need to count the number of restricted passwords (those having at least one character that is lowercase, uppercase, number, and a symbol) as compared to the unrestricted password space (any combination of characters).

Choosing a Counting Tool

There are several ways to count the number of restricted passwords and the method I describe here will be the Inclusion-Exclusion Principle, or IEP for short (sometimes the letters are written as PIE because it rolls of the tongue better). I have used the IEP to solve many problems and here is an example from the security of anonymity systems. The IEP is a general counting method used to solve problems of the following type: given a set of objects and a corresponding set of properties, determine

• How many of the objects have none of the properties?
• How many of the objects have at least one of the properties?
• How many objects have some combination of the properties?

To explain the IEP, imagine that we wish to calculate the size of the union of the sets A, B, and C shown in the diagram below

This can be achieved as follows

size(A + B + C) = size(A) + size(B) + size(C) - size(AB + AC + BC) + size(ABC)

You can verify that each region of the diagram is counted exactly once, and thus produces the correct value for the size of the union of A, B and C. The rule for the calculation is easily observed. Start by adding the sizes of the individual sets, then subtract off the sizes of intersecting sets taken 2 at a time, then add back the size of intersecting sets taken 3 at a time. If we had 5 sets to consider (A, B, C, D, E) we would continue this process of intersecting sets taken 4 and then 5 at a time. When we take an odd number of intersections, the term is added; when a even number of intersections is taken, the term is subtracted. The IEP is the underlying theory as to why adding and subtracting the sizes of increasingly larger intersections can be used to count the size of a set union.

Counting Restricted Passwords

Returning to our present context, we are interested in counting the set of passwords that satisfy a given restrictive policy (filter). Let the underlying password characters be the 94 printable ASCII characters, which consists of 26 uppercase characters, 26 lowercase characters, 10 numbers and 32 symbols. If passwords have length 8, then the unrestricted password space will have size (94)^8. We will determine the size of the restrictive password set as follows:

1. Define a collection of sets whose union fully characterises the set of passwords that do not satisfy the restrictive policy.
2. Use the IEP to compute the size of the union of the sets defined in Step 1.
3. Subtract the result from Step 2 away from the number of unrestricted passwords (the full password space).

In our case the judicious choice of sets for Step 1 is

• L - the set of passwords that do not contain a lowercase letter
• U - the set of passwords that do not contain an uppercase letter
• N - the set of passwords that do not contain a number
• S - as the set of passwords that do not contain a symbol

The union of L, U, N and S is the set of passwords that has at least one of the four character sets missing, and this represents all passwords that do not satisfy the restrictive policy. The table below shows the full IEP expansion for computing the size of the union of L, U, N and S, where n is the general length of the password. The table has 15 = 2^4-1 rows corresponding to the 15 non-empty intersections of the 4 sets. The Size column shows the number of passwords contained in each intersection. For example, the LUN row represents the set of passwords that do not have lower, upper or number characters, of which there are (94 - 26 -26 - 10)^n = 32^n. Equivalently, this is simply the number of passwords that consist only of symbols. The last row corresponding to the intersection LUNS must have a zero size since there are no passwords that do not contain a character from L, U, N or S.

Intersection	Sign	Size
L	+	(94 - 26)^n
U	+	(94 - 26)^n
N	+	(94 - 10)^n
S	+	(94 - 32)^n
LU	-	(94 - 26 -26)^n
LN	-	(94 - 26 -10)^n
LS	-	(94 - 26 -32)^n
UN	-	(94 - 26 -10)^n
US	-	(94 - 26 -32)^n
NS	-	(94 - 10 - 32)^n
LUN	+	(94 - 26 -26 - 10)^n
LUS	+	(94 - 26 - 26 -32)^n
LNS	+	(94 - 26 - 10 -32)^n
UNS	+	(94 - 26 - 10 -32)^n
LUNS	-	0

The size of the union is simply the sum of the terms in the Size column, added or subtracted according to the Sign column. Then following Step 3 above in our process, the table below shows the number of restricted passwords and their percentage as compared to unrestricted passwords, for lengths in the range 6 to 20 characters.

Length	Unrestricted	Restricted	Percentage
6	.689 x 10^12	.188 x 10^12	27%
7	.648 x 10^14	.241 x 10^14	37%
8	.609 x 10^16	.280 x 10^16	46%
9	.572 x 10^18	.307 x 10^18	53%
10	.538 x 10^20	.323 x 10^20	60%
11	.506 x 10^22	.331 x 10^22	65%
12	.475 x 10^24	.333 x 10^24	70%
13	.447 x 10^26	.330 x 10^26	74%
14	.420 x 10^28	.324 x 10^28	77%
15	.395 x 10^30	.315 x 10^30	80%
16	.371 x 10^32	.305 x 10^32	82%
17	.349x 10^34	.294 x 10^34	84%
18	.328x 10^36	.282 x 10^36	86%
19	.308 x 10^38	.270 x 10^38	88%
20	.290 x 10^40	.258 x 10^40	89%

For practical password lengths (6 to 10 characters) we see that the restrictive policy reduces the set of possible passwords by at least 40%. For passwords with 8 or less characters the reduction is more than 50%. On the other hand, as the password length increases, the fraction of passwords that satisfy the restrictive policy also increases. This just merely indicates that it is increasingly unlikely that one of the character sets will be excluded in longer and longer passwords. For 50 (!) character passwords, 99.6% of all passwords satisfy the restrictive policy.

Discussion

The original question we set out to consider was how to quantify the impact of a restrictive password policy on an unrestricted password space - to what extent are password choices reduced? The IEP shows us that the reduction in the password space due to the restrictive policy is between 73% to 40% for password lengths in the range 6 to 10 characters.

This may seem a significant reduction in the password space over practical password lengths, but I don't think this observation is too alarming. For length 8 passwords the password space is halved by the restrictive policy, but even so, we are still talking about 10^16 passwords to the nearest power of ten. That is still a large number of passwords to search or guess.

FreeMind and Flash

I have been investing quite a bit of time lately looking at various tools that can help me better organize and correlate information. In the mind mapping camp, FreeMind is making a concerted comeback after a period of arrested development since the last major release in 2005 (v0.8). The new and upcoming features are quite impressive for an open source development, and FreeMind may yet rival more professional tools such as MindManager.

One of the interesting features in the current version of FreeMind is the ability to publish interactive mind maps onto web pages using a Flash plugin. The FreeMind wiki contains a gallery showing many uses of mind maps rendered with the Flash plugin, and I have added a map I brainstormed on Issues in Publish and Subscribe systems for content distribution (this is a biggish map so right click the central node, selecting fold all from Node, to start from the main topic).

You can also find the mindmap used to write Anonymity on the Edge in an interactive Flash format here.

I often use mind maps as the first stage in defining the scope of a risk or threat assessment. There are several interesting examples of security mind maps available on the web on including threats to mobile devices, ISO17799:2005 areas, general IT security, and a colourful map on password awareness.

Related Posts

• FreeMind and Flash #2
• Three Security Mind Maps
  

Does IT Security matter?

In November last year I was invited to QUT in Brisbane to give a talk on a topic of my choice. I finally decided upon Does It Security Matter?, a play on the well-known book from Nicholas Carr.

My main message was (and remains)

• There is a dependency between IT and IT Security but not a strategic relation
• IT and IT Security are good neighbours but not good friends
• IT Security is one area competing for attention and funding, amongst many
• If you don’t make IT security matter, it won’t
• Focus on securing business processes not the process of securing
• •Excel is your new best friend - make your spreadsheets work with their (business) spreadsheets

You can find the full powerpoint here.

The No Tricks Blog Name

When I was in grad school, some time ago, my office mate showed me a cartoon of two businessmen - one American and one Japanese. The American was big and fleshy with a cigar, while the Japanese businessman was slender, stylish and alert. The American basically asked "Why are you guys doing so much better than us?". The Japanese businessman is shown extending his fingers and counting off as he says "Your managers are greedy, your workers are lazy, and ...". But before he can finish even just the most obvious reasons, the American interrupts impatiently and says "I know, I know! But what's the trick?"

Marcus Ranum expressed a similar sentiment during a recent interview when he said that IT people will practically do anything to make their network secure except design it correctly. He compared this perverseness to people who will do anything to lose weight except diet and excercise. What's the trick? No tricks.

And last month, John Pescatore of Gartner reiterated his Security 3.0 position that prevention is better than cure, and that we should have a strategy for fixing bugs at source. I take his recommendation, which could easily be made 10 or 15 years ago, as a statement that security professionals need to return to the basics. This will not be particularly useful news for "what's-the-trick?" IT managers, but by now even they must realise that their hats are rabbitless and that their sleeves are aceless. What's the trick? No tricks.

Entrust PKI v5 Overview

A few years ago now I was working quite intensely in PKI, in particular with the Entrust PKI product suite. The team was having some conceptual difficulties in following the intricacies of PKI and their deployment in Entrust v5 so I wrote an overview document. The paper contains quite a few diagrams and protocol flows, which can help to understand how the product functioned in v5. I had hoped to be given something like this when I attended the formal Entrust training.