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:

- A password of 4-16 characters.
- A PIN of 4-16 digits.
- 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 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:

- 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.
- 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:

- 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]

Very interesting and useful. Thank-you. Just leaves me wondering what type of screen lock you finally decided to use. But of course you wouldn’t want to announce that on the internet 😉

I use a pattern lock– I’m ok with “announcing” this :), according to Kerckhoff’s principle. I find it much faster and easier, which is always the tradeoff we struggle with (between security and convenience).

Very interesting, I have been looking for a clarification of the pattern combination for a while, now i can admit that I have found what i was looking for.

Kindly, I would like to seek your help in explaining what i should do to calculate the possible combination for a password pattern with 4×4 matrix, please?

Thanks in advance,

This is a good question. The bad news is that it is no longer feasible to take the approach in the code in the original post, explicitly enumerating each individual pattern, since there are so many more of them. The good news, though, is that we can approximate the number to any desired accuracy, by a simple sampling method:

It is easy to generate a random permutation of the 16 points, then check whether it corresponds to a *valid* password pattern– that is, does the “swipe” from each point to the next *not* pass through some other point not already used in the pattern?

If we assume that a valid pattern must involve at least 4 of the 16 points (as in the original), then the total number of possible patterns is approximately 4.3 trillion (4.3*10^12). Note that this is only about 7.6% of all possible permutations (compared with almost 40% in the original 3×3 case).

Here is a pastebin showing the Mathematica code for this calculation.

I currently have a Samsung Galaxy S4 and wanted to know if it’s possible to have a lock pattern that could utilize a dot more than once… Thank you! 😊

Not with the built-in screen locking function.

Hi again,

Is allowing utlization of the dot more than once provide more security and larger number of compinations?

Allowing repeats would yield more possible patterns… but how *many* more depends on the rules, so to speak– that is, how such “repeated dots” would actually work. For example, how does one “swipe” a pattern consisting of the *same* dot just repeated consecutively? Or if we instead require each swipe to be a “real” swipe to a different dot, then what is the limit on how many swipes and/or repetitions of individual dots?

In other words, the problem isn’t so much counting the number of possible patterns, but defining precisely what characterizes patterns with repetitions allowed.