Предыстория: моя жена постоянно норовит как-нибудь мне напортачить: поставить будильник на 3 часа ночи, поменять мелодию звонка, снести настройки синхронизации, удалить свою смс и потом доказывать, что она этого не говорила.
Шутки шутками, но в какой-то момент я решил: “Довольно!” — и поставил графический пароль на свой андроид.
Уязвимость графического пароля
Жена усмехнулась и сказала, что подберёт. Я посмеялся в ответ, на том и разошлись. Только теперь её волновал вопрос, как подобрать, а меня какова вероятность этого события.
Самая первая и логичная мысль придумать математический способ вычисления комбинаций.
Нужно задать начальные условия:
Направление имеет значение
Каждую точку можно пройти лишь однажды
Для соединения двух точек они должны быть в прямой видимости. То есть первая может быть соединена пальцем со второй, но не с третьей.
Количество точек: от 5 до 9. Назовём один росчерк, одно соединение — хопом. То есть у нас может быть от 4 до 8 хопов.

Попытки влоб просчитать варианты математически не увенчались успехом. Накладываемые условия не позволили выявить правила.
Следующий шаг: перебор. Не то чтобы я надеялся перебрать все десятки тысяч вариантов. Основная мысль была — найти закономерности.
Я потратил на рисование схем несколько часов. Но все закономерности упирались в симметрию и то, что все угловые точки равнозначны, как и все промежуточные (кроме центральной).
Уязвимость графического пароля
Уязвимость графического пароля
Но когда нас пугали трудности?
Начал я всё-таки с одного хопа.
Уязвимость графического пароля
1 хоп — проще пареной репы — 56 вариантов,
2 хопа — ничего сложного — 320 вариантов
3 хопа — пришлось потрудиться — 1624 варианта
4 хопа — это было, кхм, утомительно — 7152 варианта
5 хопов — мама миа и вырванные волосы — результат неизвестен.
Дальше я уже решил не насиловать свой мозг и вспомнить давно забытое программирование.
Расчехлил турбопаскаль, стряхнул пыль с переменных и начал разрабатывать алгоритм.
После 4 лет паузы и простеньких скриптов на баше мне потребовался целый вечер на отладку программы. Даром, что алгоритм родился минут за 20.
Уязвимость графического пароля
Вот вывод количества вариантов для каждого количество хопов. Как видно, с 1 по 4 цифра совпадает с практическими рассчётами, а при количестве хопов больше 8 — путей нет, что логично.
Уязвимость графического пароля
Паскаль имеет ограничение в 64 кБ на размер массива. Поэтому массив даже из Byte в несколько десятков тысяч элементов невозможен. Заморачиваться с динамическим выделением памяти или записями не хотелось, поэтому просчитать сами пути в подробностях можно только до 4 хопов:
Уязвимость графического пароля
UPD. при расчёте прежде не была учтена возможность проходить сквозь уже использованную точку.
В новой версии баг исправлен.
Это результат для последовательности 11-22-31-32-12:
Уязвимость графического пароля
И вот долгожданный результат:
Уязвимость графического пароля
Итак, 389488 возможных вариантов.
Даже если из них исключить 50% извращённых вариантов, которые не каждый человек, лишённый шизофрении, сможет с первого раза набрать (впрочем, зачем шизофренику андроид), остаётся 194744 вариантов
Уязвимость графического пароля
Андроид даёт 20 попыток, после которых блокирует телефон.
Итак, 20/194744=,0001. То есть, вероятность 0,01%. Одна сотая процента!
“Ну-ну” — сказал я жене, показывая расчёты. “Ну-ну” — сказала мне жена, показывая разблокированный телефон.
Уязвимость графического пароля