Security of the Android Pattern Lock

When my wife and I bought new Android smart phones recently, we sat down together to experiment with configuring and using them.  One interesting feature was the choice of several schemes for locking the screen when the phone is not in use, among them:

1. A password of 4-16 characters.
2. A PIN of 4-16 digits.
3. A swipe “pattern” consisting of a sequence of 4-9 positions of dots arranged in a 3×3 grid.

The following figure shows a couple of examples of patterns.  The dots are identified by numbers 0 through 8, starting with 0 in the top-left corner.

(a) Pattern 104258. (b) Pattern 104257368. A pattern may pass over a dot more than once (in this case, dot 7), but only its first “use” is considered part of the pattern.

A natural question to ask is: which scheme is most secure?  Ok, I should be honest.  This is not exactly the same as the simpler question that I actually asked, namely, how many possible patterns are there?  Given the restriction that a dot must be used the first time it is passed over, it is not as simple as counting the number of permutations of dots:

Although there are some obvious symmetries here that we could take advantage of (for example, there are the same number of patterns starting with dot 0 as with 2, 6, or 8), it is relatively simple to just recursively enumerate all possible patterns.  Following is Mathematica code that does this:

findPatterns[pattern_List] :=
 Module[
  {moves},
  moves = Complement[Tuples[Range[3], 2], pattern];
  If[moves === {},
   Sow[pattern], (* no more moves left, so record pattern *)
   Scan[ (* otherwise try all remaining moves *)
    If[pattern === {} || (* don't pass over unused dots *)
       ! MemberQ[moves, Mean[{Last[pattern], #}]],
      findPatterns[Append[pattern, #]]
      ] &,
    moves
    ]
   ]
  ]

fullPatterns = Reap[findPatterns[{}]][[2, 1]];
patterns = Join @@ Table[
    fullPatterns[[All, Range[dots]]] // Union,
    {dots, 4, 9}
    ];

This yields 389,112 possible patterns, less than 40% of the total number of permutations calculated above.  I think the key simplification here is to represent each dot as an ordered pair of Cartesian coordinates instead of just an index 0-8, since this makes it very easy to express the restriction on valid “moves” from one dot to the next.

If we compare this with the total number of possible PINs (11,111,111,111,110,000) or passwords (more than 10^28, even without the use of special characters), then the pattern lock is the clear loser.  However, there is always a tradeoff between security and convenience, and I know of no one who locks their phone with a 16-digit PIN, let alone a 16-character password.  There are only 110,000 PINs with 4 or 5 digits, for example, making the comparison with pattern locks more interesting.

But to be fair, we should similarly consider the inconvenience of “complex” patterns.  I think there are two important measures of pattern complexity:

1. The number of swipes, or straight line segments, in the pattern.  For example, the two patterns in the figure above have 4 and 8 swipes, respectively.
2. The use of “knight moves.”  For example, when moving from dot 0 directly to dot 5, I find that I must be annoyingly careful to miss dots 1 and 4 in between… assuming they have not both already been used in the pattern.

The following table shows the cumulative number of possible patterns of increasing complexity according to these metrics.

Max. Swipes	Patterns (total)	w/o Knight Moves
2	168	104
3	2,712	1,208
4	13,760	5,136
5	50,920	16,456
6	141,352	41,016
7	282,952	76,208
8	389,112	100,320

Based on this table, if we prohibit the difficult knight moves, then the security of a pattern lock is comparable to that of a 4- or 5-digit PIN… I think.  The paper referenced below describes an interesting analysis of the feasibility of “smudge attacks,” or determining the lock pattern from the visible oily residue from swiping the touch screen surface of the phone.  It is an interesting paper in its own right, but I refer to it here particularly because it mentions the difficulty of knight moves (see Section 6.2, page 8), suggesting that prohibiting them reduces the number of possible patterns to 158,410, not 100,320 as I calculated above.

[Edit: After communicating with Adam Aviv, the author of the paper, he made some changes to his code and was able to reproduce the 100,320 figure, so it appears to be correct.]

Reference:

1. Aviv, Adam J. et. al., Smudge Attacks on Smartphone Touch Screens, WOOT’10 Proceedings of the 4th USENIX conference on Offensive technologies, 1-7 (2010). [PDF]