Upper and Lower Bounds for Android Unlock Patterns

Abstract

The Android pattern unlock is a graphical password system that was introduced on Android version 1.0 as an alternative to traditional text-based password systems. To unlock a locked screen, a user needs to draw a secret pattern, which consists of a sequence of four or more contact points arranged in a grid and the security level of the pattern password is determined by the size of the pattern space. The number of possible pattern is only known for 3 X 3 and 4 X 4 grids, which was computed by brute-force enumeration (For example, in a 3 X 3 grid, there are 389,112 patterns, which can provide more choices than 4-digits PINs). However, humans do not choose a pattern uniformly at random and have some bias in the pattern selection process. Hence, the entropy of patterns is rather low and to increase the security of patterns, schemes with larger grids have been proposed. For example, CyanLockScreen allows user to select from grid sizes ranging from 3 X 3 to 6 X 6. The largest grid that we can find in real life is the 25 X 25 grid by Security Lock Screen. The only mathematical formula for the number of possible patterns is a permutation-based upper bound, which simplifies the counting by ignoring an important restriction on a valid pattern; unvisited points in a valid pattern cannot be jumped over but the permutation-based upper bound allows all kinds of jump. This thesis first studies an improved upper bound by reducing the number of jumps. To refrain from jumping over unvisited points, we use the concept of visibility, i.e., the maximum number of points that are directly reachable from a point. Secondly, this thesis present the first lower bound by computing the minimum number of visible points from each point in a various subgrids. Upper bounds enable people to avoid exaggerating or overestimating the security of pattern unlock but it is a lower bound that guarantees the minimum security level of pattern unlock. For example, lower bound is needed to answer questions such as "what size of grid should be used for 2^80 security level?".