In a recent post I discussed how to use the InclusionExclusion 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.
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:

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

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

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^61 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 nonempty 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 nonzero 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 n1 characters to exclude lower case letters, which can be done in (94  26)^(n1) ways. Thus there are
n*26*(96  26)^(n1)
ways to have exactly one lowercase letter, and in total there are then
(94  26)^n + n*26*(96  26)^(n1)
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)^(n1) 
No  Yes  n*26*(96  26 26)^(n1) 
Yes  Yes  n*(n1)*(26^2) *(94  26  26)^(n2) 
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)^(n1) 
U  +  (94  26)^n + n*26*(96  26)^(n1) 
N  +  (94  10)^n 
S  +  (94  32)^n 
LU    (94  26 26)^n + 2*n*26*(96  26 26)^(n1) + n*(n1)*(26^2)*(94  26  26)^(n2) 
LN    (94  26 10)^n + n*26*(96  26  10)^(n1) 
LS    (94  26 32)^n + n*26*(96  26  32)^(n1) 
UN    (94  26 10)^n + n*26*(96  26  10)^(n1) 
US    (94  26 32)^n + n*26*(96  26  32)^(n1) 
NS    (94  10  32)^n 
LUN  +  (94  26  26  10)^n + 2*n*26*(96  26  26 10)^(n1) + n*(n1)*(26^2)*(94  26  26  10)^(n2) 
LUS  +  (94  26  26  32)^n + 2*n*26*(96  26  26 32)^(n1) + n*(n1)*(26^2)*(94  26  26  32)^(n2) 
LNS  +  (94  26  10 32)^n + n*26*(96  26  10  32)^(n1) 
UNS  +  (94  26  10 32)^n + n*26*(96  26  10  32)^(n1) 
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.
3 comments:
Interesting article. What is the reason to restrict a password to containing certain specific characters instead of certain classes of characters?
Luke, I should have read more carefully. So my first comment is not valid, except for saying that it is an excellent article.
I'm trying to understand the logi i want to hijacked password account.
Laby[seersucker suit]
Post a Comment