Password Security and the Fundamental Counting Principle

It’s Sunday night, so you’re probably thinking wistfully about your MDM4U class, wishing that it didn’t have to wait until Monday afternoon.

Fear not: I have some problems (and later their solutions) here to keep you occupied until then.

When you create a password for most web services you have to follow some “password strength” rules. These are things like minimum password length, variety of character types, and limited repetition of characters.

Character types in passwords

In the standard English alphabet there are 26 letters. Passwords are case-sensitive, meaning upper- and lowercase letters are different. So there are 26 lowercase letters and 26 uppercase letters.

There are also numeric characters, or digits: 0-9.

Last, some (not all!) web services allow (or require) special characters like punctuation. There are 33 of these characters.

How strong is a password?

If a password is not “guessable” (like your birthday, the name of your cat, or any dictionary word), an attacker (someone trying to guess your password) will eventually have to just try every possible password out there. This isn’t a reasonable thing to do if two conditions are satisfied:

2. Your password has a lot of character types

We’re going to see why.

An example

Let’s say you have a simple password that uses lowercase letters and a number, like “phone8”. If the attacker tries all passwords with lowercase letters and numbers, how many would he/she have to try to be guaranteed to get yours?

Solution

There are 26 lowercase letters and 10 digits, for a total of 36 characters available to use. Your password is 6 characters long, so using the Fundamental Counting Principle we see there are $36\times36\times36\times36\times36\times36=2,176,782,336$ possible passwords of length 6.

That’s not quite enough, though, since the attacker first tries all passwords of length 1 through 5 as well. So the complete search space is of size $36^{1}+36^{2}+36^{3}+36^{4}+36^{5}+36^{6}=2,238,976,116$.

Not a lot more, is it? That tells you that adding that sixth character on the end made a big difference.

Try these

Figure out the number of passwords an attacker would have to try to “brute force” the following passwords:

1. 32850
2. MyDogMax
3. you_and_me
4. This-is14chars