March 30, 2013 at 12:59Graphic Password Vulnerability
Background: my wife constantly strives to screw me up somehow: set the alarm at 3 a.m., change the ringtone, tear down the synchronization settings, delete her SMS and then prove that she did not say that.
Joking as a joke, but at some point I decided: “Enough!” - and put the graphic password on your android.
The wife grinned and said she would pick it up. I laughed in response, and they parted. Only now she was worried about the question of how to pick it up, but what probability of this event was for me.
The very first and logical thought is to come up with a mathematical way to calculate combinations.
It is necessary to set the initial conditions:
Attempts to calculate options mathematically were unsuccessful. The imposed conditions did not allow to reveal the rules.
Next step: busting. Not that I was hoping to go through all the tens of thousands of options. The main idea was to find patterns.
I spent several hours drawing diagrams. But all the laws rested on symmetry and the fact that all the corner points are equivalent, like all the intermediate ones (except the central one).
But when did the difficulties scare us?
I started all the same with one hop. 1 hop - easier than steamed turnip - 56 options, 2 hop - nothing complicated - 320 options 3 hop - had to work hard - 1624 options 4 hop - it was, ahem, tiring - 7152 options
5 hop - mom mia and torn hair - the result is unknown.
Then I decided not to rape my brain and remember the long-forgotten programming.
He uncovered the turbopascal, dusted off the variables and began to develop an algorithm.
After 4 years of pause and simple scripts on the bash, it took me a whole evening to debug the program. Even though the algorithm was born in about 20 minutes.
Here is the output of the number of options for each number of hopes. As you can see, from 1 to 4, the figure coincides with practical calculations, and when the number of hopes is more than 8, there are no ways, which is logical.
Pascal has a limit of 64 KB on the size of the array. Therefore, an array even from Byte of several tens of thousands of elements is impossible. I did not want to bother with dynamic memory allocation or records, so you can only calculate the paths in detail up to 4 hopes:
UPD. when calculating, the possibility of passing through an already used point was not taken into account before .
In the new version, the bug is fixed.
This is the result for the sequence 11-22-31-32-12:
And here is the long-awaited result:
So, 389488 possible options.
Even if we exclude from them 50% of the perverted options that not every person deprived of schizophrenia can dial from the first try (however, why the schizophrenic is an android), 194744 options remain. The
Android gives 20 attempts, after which the phone blocks.
So 20/194744 =, 0001. That is, the probability is 0.01%. One hundredth of a percent!
“Well, well,” I said to my wife, showing the calculations. “Well, well,” my wife told me, showing me the unlocked phone.
Joking as a joke, but at some point I decided: “Enough!” - and put the graphic password on your android.
The wife grinned and said she would pick it up. I laughed in response, and they parted. Only now she was worried about the question of how to pick it up, but what probability of this event was for me.
The very first and logical thought is to come up with a mathematical way to calculate combinations.
It is necessary to set the initial conditions:
- Direction matters
- Each point can be reached only once.
- To connect two points, they must be in direct line of sight. That is, the first can be connected with the second finger, but not with the third.
- Number of points: from 5 to 9. Let's call one stroke, one connection - hop. That is, we can have from 4 to 8 hop.
Attempts to calculate options mathematically were unsuccessful. The imposed conditions did not allow to reveal the rules.
Next step: busting. Not that I was hoping to go through all the tens of thousands of options. The main idea was to find patterns.
I spent several hours drawing diagrams. But all the laws rested on symmetry and the fact that all the corner points are equivalent, like all the intermediate ones (except the central one).
But when did the difficulties scare us?
I started all the same with one hop. 1 hop - easier than steamed turnip - 56 options, 2 hop - nothing complicated - 320 options 3 hop - had to work hard - 1624 options 4 hop - it was, ahem, tiring - 7152 options
5 hop - mom mia and torn hair - the result is unknown.
Then I decided not to rape my brain and remember the long-forgotten programming.
He uncovered the turbopascal, dusted off the variables and began to develop an algorithm.
After 4 years of pause and simple scripts on the bash, it took me a whole evening to debug the program. Even though the algorithm was born in about 20 minutes.
Code itself
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
{We will calclate only path amount, but not detailed paths, because of
limitation to array size.
Actually you can make detailed path up to 5 hops. You just should uncomment
calculating of array 'Bom'}
A[cur_i,cur_j]:=1;
for i:=1 to 3 do
begin
for j:=1 to 3 do
begin
{ Bom[path_num,k]:=cur_i*10+cur_j;}
if k1)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
{We will enlarge path number if hop amount in path is
qual to actual hop amount only}
if k=hop_count then
begin
path_num:=path_num+1;
{ Bom[path_num,k+1]:=i*10+j;}
end;
A[i,j]:=1;
{Recursive running of path calculation}
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
{Enlarge path number after exit out of procedure}
{ Bom[path_num,k+1]:=i*10+j;}
path_num:=path_num+1;
end;
end;
end;
end;
end;
begin
{A[x,y] - Array of 0 and 1.
0 - this point isn't in path yet. You can move here.
1 - this point is in path already. You can't move here.
}
ClrScr;
writeln ('Hello, Habrahabr. 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
{ Bom[path_num,k]:=10*i+j;}
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);
{Output of full list of paths.}
{for m:=1 to path_num do
begin
write('Path ', m,': (');
for n:=1 to hop_count+1 do
begin
write(Bom[m,n],' ');
end;
writeln(')');
readln;
end;{}
readln;
end.
Here is the output of the number of options for each number of hopes. As you can see, from 1 to 4, the figure coincides with practical calculations, and when the number of hopes is more than 8, there are no ways, which is logical.
Pascal has a limit of 64 KB on the size of the array. Therefore, an array even from Byte of several tens of thousands of elements is impossible. I did not want to bother with dynamic memory allocation or records, so you can only calculate the paths in detail up to 4 hopes:
UPD. when calculating, the possibility of passing through an already used point was not taken into account before .
In the new version, the bug is fixed.
This is the result for the sequence 11-22-31-32-12:
And here is the long-awaited result:
So, 389488 possible options.
Even if we exclude from them 50% of the perverted options that not every person deprived of schizophrenia can dial from the first try (however, why the schizophrenic is an android), 194744 options remain. The
Android gives 20 attempts, after which the phone blocks.
So 20/194744 =, 0001. That is, the probability is 0.01%. One hundredth of a percent!
“Well, well,” I said to my wife, showing the calculations. “Well, well,” my wife told me, showing me the unlocked phone.