Password Complexity vs Usability (Part 2)

At my place of work, we have a number of safes. Most of them require access by more than one person. The local security policy demands the combinations be changed periodically. People in general are not very good at remembering a lot of numbers. So someone started the custom of using a word mnemonic for the combinations. The locks use 3 2-digit numbers between [00..99]. So someone used a standard telephone keypad and mapped the digits to letters. Of course, done at random, this is unlikely to result in a valid English word or phrase. So the generation of the numbers gets done the other way around. A word is selected first and then mapped to numbers.



That's pretty clever and is certainly an easy system to use and have a dozen people remember.
And when we have multiple containers in the same room, we use a series of related words so the "theme" further helps you remember them. In our defense, most of us do not have to access them very often, so using a thematic set of words really does help the usability side of the situation.

Quick sidebar... why do we call them combination locks? In mathematics, a combination is a selection of items where order does not matter. The order you enter the numbers of the lock matters very much. If the "combination" is {1, 2, 3}, then you cannot open the lock by entering {3, 2, 1}. When order matters, that's called a permutation. So rightfully, it should be called a permutation lock. End digression.

As discussed in previous posts, there is always a trade-off between security and usability. In this case,
the trade-off sacrifices a significant portion of the number space for the sake of usability convenience.
The combination is no different than a password. We know that you can make passwords stronger by
increasing their length and/or the character space. If you can use digits in addition to letters, you increase the number of character options from 26 to 36 which makes guessing take longer on average due to the larger number of possibilities.

With the safe lock using [00..99], you have 100 numbers to choose from. You cannot use the same 2-digit number twice in the combination, so you you have permutations without repeats. The formula for the total number of permutations of n choose r without repeats is n! / (n - r)!

Using all 100 numbers, the lock has 970,200 different permutations.

But let's look carefully at the telephone pad mapping. There are no letters mapped to the digits 0 or 1.
That eliminates any 2-digit number containing either or both digits. So that eliminates [00..20] and every x0 and x1 up through 90 and 91. After removing all those, we are left with only 64 2-digit numbers. That reduces the number of permutations to 249,984. That just eliminated approximately 75% of the  search space.

And it gets worse. Out of all those permutations, how many map back to an English word?
I wrote a Perl program to take the list of words from the "words" 3.0 package on Linux and map them
to their telephone pad numbers. Then I hashed them using the number as the key and looked at the
total number of keys at the end. There are 40562 6-letter words in the file. I'm going to fudge a little
here and not consider short phrases consisting of two smaller words like "GO LONG" and such.
The situation improves a little if you consider those, but there is no easy way to compute how many
such phrases there might be. I also cannot consider local slang, acronyms, abbreviations and in-jokes.

So if you take those 40562 6-letter words and map them to numbers, you find they map to 28420
unique number permutations. That is only 2.9% of the total space of 970,200 permutations.
Let us assume that if you did throw in the other things mentioned above, you might get to say 5% or maybe 10% at best. That is still sacrificing the majority of your the search space by an order of magnitude.