Secure Your Phone with Pretty Pictures

March 29, 2011

A good friend of mine is moving on up in the world, and to prove it, he recently upgraded his cell phone.  His new phone is one of several that has a clever password feature - instead of entering a traditional password, one creates a shape within a 9 point grid, like a miniature connect the dots.  Here's one video explaining the feature:

The rules for the patterns are fairly simple, but to make things crystal clear, let me label the dots in the grid as follows:

Here are the rules constraining the types of patterns you can make:

  1. The pattern must connect at least 4 dots.
  2. No dot may be used more than once.
  3. The order in which the dots are connected matters.
  4. Two dots which are on opposite sides of the grid (e.g. 1 and 9, 2 and 8, 1 and 3) cannot be connected together directly without going through the dot between them, unless the dot between them has already been used.
To give some examples, the first rule prohibits patterns that are too small, such as 1-2-3.  The second one prohibits patterns like 1-2-3-5-7-4-1, although a pattern like 1-5-2-3-7 is allowed by the fourth rule - in other words, we can jump from 3 to 7 since the 5 has already been used.


Images of the paths described above.

The third rule tells us, for example, that 1-2-3-6 and 6-3-2-1 are DIFFERENT passwords, even though the shape they make is the same.  Thus, the password is determined not only by shape, but also by direction.


Same paths, different directions.

I should also point out that it is possible to connect dots that are not immediately adjacent - for example, one can draw a line from 2 to 7.  So, for example, if one starts at 1, it is possible to move to every dot except for 3, 7, and 9.

Given these rules, my friend is interested in determining how many unique passwords one can make.  For comparison's sake, we can think about the iPhone, which can be secured with a 4-digit passcode.  Since each digit can run from 0 to 9, we see that there are 10,000 = 104 possible iPhone passwords.  How does the number of patterns compare, say, to this number?

Without too much work, we can provide an upper bound for the number of passwords one can make using these pattern rules.  To see how this is done, let's forget about the pretty pictures, and focus only on the sequence of digits (for example, the paths above can be viewed as the sequences 1236 and 6321).  From this perspective, the second rule tells us that no digit can appear in our sequence more than once, and so in combination with the first rule this tells us that the sequence must be between 4 and 9 digits long.  Suppose for a moment that these we ignore the fourth rule.  Then the number of allowable patterns would be the same as the number of ordered strings of digits of length 4 to 9, where in each string the same digit can appear no more than once.

The fact that the order is important tells us we are dealing with permutations.  These can be counted easily.  For example, the number of ways to make a 4 digit password if no digit from 1 to 9 can appear more than once is 987*6 = 9!/5!.  Similarly, the number of ways to make a 5 digit password if no digit can appear more than once is 9!/4!.  Adding all these up (for lengths from 4 to 9), we find that under these conditions, the number of passwords equals

9!/5! + 9!/4! + 9!/3! + 9!/2! + 9!/1! + 9!/0! = 985,824.

That's a nearly 100 fold increase in the number of possible passwords!  Of course, this doesn't reflect the number of patterns one can make, because we have ignored some of the rules.  This means, for example, that we have counted the string of digits 1397, even though this doesn't represent an allowable pattern.

How can we modify this argument to eliminate the digit strings that don't correspond to patterns?  This requires a more careful analysis.  For simplicity, let's suppose that 3 digit passwords are acceptable, and focus only on them.

In this analysis, there are three types of dots that matter: the dots in the corners, the dots on the sides, and the dot in the middle.  Let's label these classes of points by C, S, and M.  The first dot in your pattern can be any one of these three types, but the number of options you have depends on the type; in other words, you have 4 choices for a corner dot, 1 choice for a middle dot, and 4 choices for a side dot.

Moreover, the number of options for your second choice depends on what type of dot you start with.  If you choose a corner dot, you have 5 options for your next dot (either the middle, or one of the four sides).  Meanwhile, if you choose the middle dot, the next dot in your pattern can be any of the remaining 8 dots.  Similarly, if you start at a dot on the side, you have 7 options for the next dot, since you can move to any dot except for the one directly opposite your starting dot.

Similarly, the number of options for the third dot depends on your choice for the second dot.  If you choose the corner dot and then the middle dot, you will have 7 choices for the third dot.  Meanwhile, if you choose the center dot and then a side dot, you'll have 6 choices for the third dot.  And so on - the number of options is summarized in the following chart.


Number of options for a 3 dot pattern (notation explanation below)

In particular, note that if you start at a side dot, the number of patterns you can create depends on whether your choice for the second dot is the middle dot, a corner adjacent to your starting dot (or a "close corner," labeled cC), a corner not adjacent to the starting dot (or a "far corner," labeled fC), or another side.  Moving from a side to a close corner gives 5 choices for the third dot, while moving from a side to a far corner gives only 4 choices for the third dot.


There are 5 viable candidates when moving from a side to a close corner, but only 4 when moving from a side to a far corner.

The point is that even in this (relatively) simple example, the number of options for any given point in the pattern is highly dependent upon the choices made up to that point.  In the case of 3 dots, the chart above tells us that the total number of allowable patterns is 4 × 1 × 7 + 4 × 4 × 6 + 1 × 4 × 5 + 1 × 4 × 7 + 4 × 1 × 7 + 4 × 2 × 5 + 4 × 2 × 4 + 4 × 2 × 6 = 320.  This is in contrast to the upper bound of possible permutations of 3 of the 9 digits, which is given by 9 × 8 × 7 = 504.

As you can see, just counting the number of patterns connecting three dots is a little annoying.  Doing the same for patterns of lengths 4 through 9 is even worse.  Although conceptually it's not difficult to count patterns, technically the task quickly becomes arduous.  Thankfully, we can easily delegate technical calculations to those lovable sidekicks, computers.

After realizing that the calculations would be no fun to do by hand, I went online and discovered that this question has already been answered here.  If you click on the link, you'll find some savvy folk who wrote programs to count all possible paths.  Final answer: 766,752 (incidentally, this is 7/9ths of the upper bound we calculated above).

So, we still have an over 75 fold increase in the number of possible passwords when compared to a device like the iPhone.  Whether or not this actually makes for a more secure device is a question I can't answer.  I will point out that many of these phones lock you out for 30 seconds after five failed password attempts - if we assume that a crude hacker could make 5 password attempts per minute, then 766,752 different password options means that it could take over 100 days of continuous guessing before your password is cracked.  Of course, an actual hacker undoubtedly has more sophisticated methods.  Even so, if more celebrities locked their phones with pretty pictures, perhaps hackers would have a harder time stealing all of their naked photographs.

(Big ups to Matt for suggesting this problem!)

Psst ... did you know I have a brand new website full of interactive stories? You can check it out here!

comments powered by Disqus