January 8th, 2011


Password Quality

Earlier this week, I did some calculations on the number of unique passcodes possible using Android's matrix login. In the comments to that post, I mentioned that I thought there were very, very few such passwords that were symmetric, but failed to quantify now few that was. locallunatic took a couple of stabs at it before giving up, but I spent some time this morning working my way through it.

So, what I'm looking for precisely are any passwords in which are symmetric about the center up-down axis. For instance, the password "1 8 3" would be symmetric.

To that end, there are several classes of such passwords that will make counting easier:

Trivial Passswords: the single digit passwords "2", "5", and "8". 3 Total

Passwords with 2+ digits all on the central axis:
Example "2, 5". There are 2 possible length 2 passwords and 2 possible directions (up to down and down to up) and 1 possible length 3 password with 2 possible directions.

2 * 2 * 2 + 1 * 2 = 10 Total

Passwords of form 'stuff in column 1, a digit in column 2, and the reverse of column 1 in column 3':

Passwords of this form are all odd in length and can further be subdivided based on total password length.

Length 3: Passwords with one digit on the left, a center digit, and the compliment.

There are three left digits to choose from, then three digits to choose from for the center and one for the final column. Also, since passwords going left to right and passwords going right to left are unique in the password quality, we double the total number of choices.

Therefore 3 * 3 * 2 = 18 Total .

Length 5: Passwords with a two-digit sequence in column one, a center digit and the inverse of the sequence in column three. Example: "1 4 9 6 3". There are two possible two digit cominations. Each combination can be oriented either up or down. There are still three choices for the center digit and two possible directions.

So, 2 * 2 * 3 * 2 = 24 Total

Length 7: Passwords with a three-digit sequence in column one, a center digit, and the inverse in the last column. There is one possible choice of numbers, but two up-down orderings and two left-right orderings.

Thus, 2 * 3 * 2 = 12 Total

Add up all of these and you get the total number of possible passwords: 67


Incidentally, I believe my earlier calculation is probably incorrect as it doesn't count passwords like "2 1 3" which is valid, but not envisioned by my previous program. This will increase the count somewhat, but I've not yet run the calculation.

Published by XPostGTK+