Numeric impact of constraints on sets (passwords)

[Randy_Abrams]

Hi folks,

I've got everything I need to write a paper on the effect of constraints on passwords... except the math. I actually could write it, but the math would make it much meatier.

Here is what I know about math. If the answer to a math problem is obvious, it is probably wrong. If the answer is incomprehensible the chances of the answer being wrong are statistically insignificant.

I understand that I am really talking about sets, but I'll say passwords since it is an application of the math that engages me. So here is the problem.

I have 4 character sets; (L)owercase letter s(26), (U)ppercase letters (26), (N)umbers (10), and (S)pecial characters (33). The total character set count is 95. I know that the number of combinations is 95^X. So the number of possible combinations for a 12 character password 95^12, or roughly the national debt :) Now let's add some constraints. The password must be at least 12 characters long. If I haven't already got my math wrong that means the number of possible valid combinations is (95^12)-(95^11). My bad (Scott). If the password had to be 12 characters long then there are 95^11 invalid combinations of passwords that created from the printable ASCII set.

Now we add an additional constraint. The password must contain at least one lowercase letter. So now, not only are all passwords less than 11 characters in length invalid, all passwords that contain combinations of only U, N, S, UN, US, or NS are also invalid. What is the number of valid combinations that are left? If the password must contain only an uppercase letter the numbers should be the math should be same since the character sets have the same number of characters.

Now we further constrain the passwords. They must contain at least one L and one U. How many valid combinations are left?

You see this coming, don't you? Must contain at least LUN. What's left?
And must contain LUNS. What's left?

And you thought I was done? What if the password cannot have the same symbol 3 times in a row? 2 times in a row?

I really appreciate any help with this. It's been driving me nuts for weeks. I tried to do the math but I was pretty sure I got it wrong when I was able to manipulate a constraint and ended up a very large negative number of valid combinations. I will be blogging my analysis, which is more than just data, and most certainly give conspicuous credit to those who help me and to the forum.

We can deal with entropy another time. When it comes to passwords and passphrases, entropy is a mathematical formula that proves we humans aren't as clever as we think we are.

I hope this will be an engaging challenge that is also educational for many other people too.

Thank you in advance!

Randy

 

[.Scott]

I understand that I am really talking about sets, but I'll say passwords since it is an application of the math that engages me. So here is the problem.

Yes, ordered sets.

I have 4 character sets; (L)owercase letter s(26), (U)ppercase letters (26), (N)umbers (10), and (S)pecial characters (33). The total character set count is 95.

Fine, the printable ASCII character set.

I know that the number of combinations is 95^X. So the number of possible combinations for a 12 character password 95^12, or roughly the national debt :)

So far so good. You number 95^12 is for passwords that are exactly 12 characters (no less0.

Now let's add some constraints. The password must be at least 12 characters long. If I haven't already got my math wrong that means the number of possible valid combinations is (95^12)-(95^11).

No, it would be (95^12)+(95^13)+...+(95^N) where N is you maximum password length.

Now we add an additional constraint. The password must contain at least one lowercase letter. So now, not only are all passwords less than 11 characters in length invalid, all passwords that contain combinations of only U, N, S, UN, US, or NS are also invalid. What is the number of valid combinations that are left? If the password must contain only an uppercase letter the numbers should be the math should be same since the character sets have the same number of characters.

For exactly 12 characters, it would be: 95^12 - (95-26)^12
That's all possible combinations minus all combinations with no L.

Now we further constrain the passwords. They must contain at least one L and one U. How many valid combinations are left?

All - noL - noU + no L or U: 95^12 - (95-26)^12 - (95-26)^12 + (95-52)^12

You see this coming, don't you? Must contain at least LUN. What's left?
And must contain LUNS. What's left?

Out of time. I might have time later.

But don't forget, this is only 12 characters. For a range, you will need to add up the value for 12, 13, 14, ... N.

But think of (1-U)(1-L)(1-N)(1-S) = 1 - U - L - N - S + UL + UN + US + LN + LS + NS - ULN - ULS - UNS - LNS + ULNS
Then work out the formula from that: All - NoU - NoL - ...