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.

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]

I like this month’s IBM Research puzzle for several reasons.  First, it is really three puzzles in one, where each component is relatively self-contained.  Second, it has some very “nice” elegant mathematics in it, but will also yield to computer simulation… up to a point.  And third… I think it is hard.

Problem: Alice and Bob are playing two games: they start simultaneously and the first one to win his game is the winner.

Alice is given an urn with N balls, colored in N different colors and in every second she randomly picks two balls, colors the first ball in the color of the second ball and returns both to the urn.

Her game is over once all the balls in the urn have the same color.

Bob is given an urn with M balls, all colorless, and in every second he picks a random ball, color it, and puts it back to the urn. Bob’s game is over once all his balls are colored.

Our question is: what are the possible values of M for which (on average) Bob is expected to lose for N=80 and win for N=81?

The three pieces of the puzzle are to: (1) analyze Alice’s game, (2) analyze Bob’s game, and then (3) compare the two.  I think the original intent of the problem was that Alice’s game should be the really “interesting” part.  Consider computing the expected number of seconds for each player to finish.  Bob’s game is a rather standard problem in thin disguise. Alice’s game, on the other hand, requires a bit more work.

However, it is that part (3) of the puzzle that motivated this post.  I think a key question is, what is meant by “Bob losing on average“?  More precisely, once Alice and Bob have completed their games, what does the winner win?  There are two reasonable possibilities:

1. The loser pays the winner a dollar for every additional second needed to finish the (loser’s) game.
2. The loser pays the winner a dollar.

An update to the problem in response to this question confirms, as I suspected, that (1) is actually the intended interpretation.  Good thing, too, because in that case the problem essentially reduces to simply finding the expected number of seconds for Alice to finish.  But it seems to me that the original problem, as written, implies (2), which I think makes the problem much harder… or at least, much harder for me.