Playing with models.

Are Android unlock patterns as secure as numeric PINs?

Posted in Mathematics by Alexander Lobkovsky Meitiv on April 14, 2010

An example of the Android unlock pattern

Unlock pattern may be easier to remember than a string of numbers.


This post is a digression. It’s not about constructing mathematical models of real world phenomena. It’s about sequences of numbers like the famous Fibonacci sequence and the Android pattern unlock screen shown here.

The rationale for a graphical pattern instead of a numeric PIN is clear. Humans are much better at remembering patterns than strings of digits. But is the pattern as secure? Other issues aside, such as traceability of fingerprint smudges that allows an attacker to recover the pattern, are there as many patterns as there are numeric PINs of the same length?

Well that’s where understanding recursion relations is useful. A recursion relation defines a sequence of numbers a_n by a relationship between a_n and all preceding sequence members. For example the Fibonacci sequence is defined via

a_n=a_{n-1}+a_{n-2}, \quad a_1=1, \quad a_2=1.

Depending on the type of recursion relation (whether it is linear, for example), there are a variety of methods for solving them. Let’s use the power of recursion to find the number of possible Android unlock patterns that connect N dots.

To make the problem seemingly more complicated (but really simpler) let’s separately compute the number of patterns that start at the center, side and corner of the 3×3 grid of dots. Let’s call those numbers O_N, S_N, and C_N. The total number of unlock patterns is

T_N=O_N+4S_N+4C_N.

Because there are 4 corner and 4 side dots in the 3×3 grid.

Let’s now derive a recursion relation for O_N,\ S_N,\ C_N. The first step is to note that when the pattern consists of only one dot (that would not be a very secure pattern) we trivially get O_1=1,\ S_1=1, and C_1=1.

Now let’s imagine that we managed to compute O_{N-1},\ S_{N-1}, and C_{N-1} for some N. We can then compute C_N noticing that the very first link that is made from the center dot can only go to a side dot (4 possible ways) or to a corner dot (also in 4 possible directions). Therefore

O_N=4S_{N-1}+4C_{N-1}.

When starting from the side dot, there are 4 ways to get to a corner dot, one way to get to the center dot and 2 ways to get to other side dots, therefore

S_N=4C_{N-1}+O_{N-1}+2S_{N-1}.

And finally when starting from a corner dot, there are 4 ways to get to a side dot and one way to get to the center dot, thus

C_N=4S_{N-1}+O_{N-1}.

The above three relationships can be summarized as

V_N=A\,V_{N-1}\quad\quad\quad \mathrm{(1)},

using matrix notation by defining a vector V_N=(O_N,S_N,C_N)^{T}, and a matrix

A=\left(\begin{array}{ccc}0&4&4\\1&2&4\\1&4&0\end{array}\right).

Hang on tight, we are almost there. The simple recursion relation (1) means that we can obtain the numbers of patterns connecting N dots from those for N - 1 dots by just applying the matrix A. Applying this reasoning recursively we arrive at

V_N=A^{N-1}\,V_1.

I won’t bore you with the rest of the calculation which is quite routine. As my eccentric math tutor used to say: “After this point it’s just algebra!”

Here is the result of the calculation:

N Number of patterns connecting N dots Number of numeric PINs of N digits
2 56 100
3 360 1,000
4 2,280 10,000
5 14,544 100,000
6 92,448 1,000,000
7 588,672 10,000,000
8 3,745,152 100,000,000

Clearly, the number of patterns grows slower than the number of numeric PINs. This may not matter, however, if patterns are easier to remember and therefore one can comfortably have a longer pattern.

The only sure way to determine whether it is indeed easier to remember patterns, is through careful experiments with human subjects. Until such data are available, all statements about memorability and security of patterns vs PIN’s are pure speculation…

PS:
The restriction that a dot cannot be used more than once in a pattern *dramatically* reduces the number of allowed patterns. Please see comments for the true number of unlock patterns.