Graphical Password Vulnerability

My wife constantly tries to mess with my phone: setting the alarm for 3 AM, changing the ringtone, wiping sync settings, deleting her own text messages and then claiming she never said that.

Jokes aside, at some point I decided: "Enough!" — and set up a graphical pattern lock on my Android.

My wife smirked and said she'd figure it out. I laughed in response, and we left it at that. Only now she was preoccupied with how to crack it, while I was curious about the probability of that happening.

The Problem Setup

The very first and most logical thought was to come up with a mathematical method for calculating combinations. We need to establish the initial conditions:

• Direction matters
• Each point can only be visited once
• To connect two points, they must be in direct line of sight. That is, the first point can be connected by finger to the second, but not to the third (if the second is in between and hasn't been visited yet).
• Number of points: from 5 to 9. Let's call one stroke, one connection — a hop. So we can have from 4 to 8 hops.

Manual Calculations

Attempting to brute-force the calculations mathematically didn't work out. The imposed conditions prevented finding any patterns.

The next step: enumeration. Not that I hoped to enumerate all tens of thousands of combinations. The main idea was to find patterns. I spent several hours drawing diagrams. But all the patterns came down to symmetry and the fact that all corner points are equivalent, as are all edge midpoints (except the center point).

But when have difficulties ever scared us? I started with one hop anyway.

• 1 hop — easy as pie — 56 combinations
• 2 hops — nothing complicated — 320 combinations
• 3 hops — had to put in some effort — 1,624 combinations
• 4 hops — that was, ahem, exhausting — 7,152 combinations
• 5 hops — mama mia and pulled-out hair — result unknown.

After that, I decided to stop torturing my brain and recall my long-forgotten programming skills.

The Code

I dusted off Turbo Pascal, blew the dust off my variables, and started developing the algorithm. After a 4-year hiatus with only simple bash scripts, it took me an entire evening to debug the program. Even though the algorithm itself was born in about 20 minutes.

Program First;
Uses Crt;

VAR
i,j,k,cur_i,cur_j,hop_count:byte;
A:array[1..3,1..3] of byte;
Bom:Array[1..10000,1..5] of byte;
path_num,total,m,n:longint;

Procedure PATH(cur_i,cur_j:byte; k:byte);
VAR
i,j:byte;
m,n:integer;
begin
A[cur_i,cur_j]:=1;
for i:=1 to 3 do
begin
    for j:=1 to 3 do
    begin
        if k<hop_count then
        begin
             if (A[i,j]=0)and
             not(
             ((i=cur_i)and(abs(j-cur_j)>1)and(A[i,2]=0))
             or
             ((j=cur_j)and(abs(i-cur_i)>1)and(A[2,j]=0))
             or
             ( (abs(i-cur_i)>1) and (abs(j-cur_j)>1) and (A[2,2]=0))
             )
             then
                begin
                     if k=hop_count then
                     begin
                          path_num:=path_num+1;
                     end;
                     A[i,j]:=1;
                     PATH(i,j,k+1);
                     A[i,j]:=0;
                end;
        end
        else
        begin
             if (A[i,j]=0)and
             not(
             ((i=cur_i)and(abs(j-cur_j)>1)and(A[i,2]=0))
             or
             ((j=cur_j)and(abs(i-cur_i)>1)and(A[2,j]=0))
             or
             ( (abs(i-cur_i)>1) and (abs(j-cur_j)>1) and (A[2,2]=0))
             )
             then
             begin
                     path_num:=path_num+1;
             end;
        end;
    end;
end;
end;

begin
ClrScr;
writeln ('Hello, a. Let''s count amount of Android Graphical passwords.');
writeln;
i:=1; j:=1; k:=1;
for hop_count:=4 to 8 do
begin
     path_num:=1;
     for i:=1 to 3 do
         for j:=1 to 3 do
         begin
            PATH(i,j,k);
            a[i,j]:=0;
         end;
     writeln('Hops: ',hop_count,'. Path amount: ',path_num-1);
     total:=total+path_num-1;
end;
writeln('===========================');
writeln('Total amount:         ',total);
readln;
end.

Results

Here's the output showing the number of combinations for each hop count. As you can see, from 1 to 4 hops the numbers match the manual calculations, and with more than 8 hops there are no paths, which is logical.

Pascal has a 64 KB limitation on array size. Therefore, an array of even Bytes with several tens of thousands of elements is impossible. I didn't want to bother with dynamic memory allocation or records, so calculating detailed paths is only possible up to 4 hops.

UPDATE: The previous calculation didn't account for the ability to pass through an already-used point. In the new version, this bug has been fixed.

This is the result for the sequence 11-22-31-32-12.

And here is the long-awaited result:

The Verdict

So, 389,488 possible combinations. Even if we exclude 50% of the "twisted" combinations that not every person free of schizophrenia could enter on the first try (although, why would a schizophrenic need an Android?), that still leaves 194,744 combinations.

Android gives you 20 attempts before locking the phone.

So, 20/194,744 = 0.0001. That is, a probability of 0.01%. One hundredth of a percent!

"Well, well," I said to my wife, showing her the calculations. "Well, well," my wife said to me, showing my unlocked phone.