Уязвимость Графического Пароля

Предыстория: моя жена постоянно пытается меня каким-то образом подставить: поставить будильник на 3 часа ночи, изменить мелодию звонка, удалить настройки синхронизации, удалить свои СМС, а потом доказать, что она этого не говорила.

Шутки шутками, но в какой-то момент я решил: «Хватит!» - и установил графический пароль на своем Android.

Уязвимость графического пароля

Моя жена улыбнулась и сказала, что заберет его.

Я посмеялся в ответ, и всё.

Только вот ее волновал вопрос, как ее забрать, а меня волновала вероятность этого события.

Самая первая и логичная идея — придумать математический способ расчета комбинаций.

Вам необходимо задать начальные условия:

Направление имеет значение
Каждую точку можно пройти только один раз
Чтобы соединить две точки, они должны находиться в прямой видимости.
То есть первый можно соединить пальцем со вторым, но не с третьим.
Количество баллов: от 5 до 9. Назовем один удар, одно соединение прыжком.
То есть у нас может быть от 4 до 8 прыжков.

Попытки просчитать варианты математически не увенчались успехом.

Навязанные условия не позволили выявить правила.

Следующий шаг: перебор.

Не то чтобы я ожидал просмотреть все десятки тысяч вариантов.

Основная идея заключалась в поиске закономерностей.

Я потратил несколько часов на рисование диаграмм.

Но все схемы упирались в симметрию и в то, что все угловые точки равнозначны, как и все промежуточные (кроме центральной).

Уязвимость графического пароля

Но когда нас пугали трудности? Я все равно начал с одного прыжка.

1 хмель – проще пареной репы – 56 вариантов, 2 хмеля - ничего сложного - 320 вариантов 3 хмеля - пришлось потрудиться - 1624 варианта 4 прыжка - это было, кхм, утомительно - 7152 варианта 5 прыжков – Мама Миа и вырванные волосы – результат неизвестен.

Тогда я решил не насиловать свой мозг и вспомнить давно забытое программирование.

Я раскрыл турбопаскаль, стряхнул пыль с переменных и начал разрабатывать алгоритм.

После 4 лет паузы и простых скриптов на Bash у меня ушел целый вечер на отладку программы.

Это подарок, что алгоритм родился примерно за 20 минут.

Уязвимость графического пароля

Сам код

   

 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 k<hop_count then
         begin
 
         {Checking possibility of doing next-hop}
 
              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
 
                      {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.

Вот результат количества опций для каждого количества переходов.

Как видите, от 1 до 4 число совпадает с практическими расчетами, а если количество прыжков больше 8, путей нет, что логично.

Уязвимость графического пароля

В Паскале ограничение размера массива составляет 64 КБ.

Поэтому массив даже Байта из нескольких десятков тысяч элементов невозможен.

Мне не хотелось заморачиваться с динамическим выделением памяти или записями, поэтому детально просчитать сами пути можно только до 4-х прыжков:

Уязвимость графического пароля

УПД.

расчет ранее не учитывал возможность прохождения через уже использованный пункт. Ошибка исправлена в новой версии.

Это результат для последовательности 11-22-31-32-12:

Уязвимость графического пароля

И вот долгожданный результат:

Так, 389488 возможные варианты.

Даже если исключить из них 50% извращенных вариантов, которые не каждый человек без шизофрении сможет набрать с первого раза (впрочем, зачем шизофренику Андроид), остается 194 744 варианта

Уязвимость графического пароля

Андроид дает 20 попыток, после чего блокирует телефон.