To ile jest tych wzorków?

Wygoda i bezpieczeństwo zwykle nie idą w parze. Jeśli system jest bezpieczny, zwykle wpływa to na wygodę jego użytkowania. Jeśli z kolei jest wygodny, cierpi na tym bezpieczeństwo. Ważne jest, by znaleźć taki punkt, w którym wygoda spełnia oczekiwania użytkowników, ale bezpieczeństwo ciągle jest na akceptowalnym poziomie. Ważne jest też to, by rozumieć skutki (dla bezpieczeństwa) przyjętych rozwiązań.

Dzisiaj zajmę się bezpieczeństwem “logowania przez wzorek”, a w szczególności porównaniem jego mocy z “normalnym” hasłem. Tak, chodzi mi o to rozwiązanie, gdzie użytkownik na kropkach rysuje wzorek. I nie, nie będę się zajmował atakami związanymi ze smugami zostawionymi na ekranie.

Jeśli mamy “normalne” hasło, wyliczenie ilości możliwych kombinacji jest proste. Wystarczy określić ilość dopuszczalnych znaków i wykonać operację potęgowania, gdzie wykładnikiem będzie długość hasła. Na przykład PIN użytkownika składający się z czterech cyfr daje nam 10^4 możliwości, czyli 10 000 możliwych kodów PIN. Jak dokonać analogicznych wyliczeń dla “wzorków”?

Po pierwsze trzeba się zastanowić czy potrzebna jest nam dokładna wartość, czy wystarczy nam pewne szacowanie. Jeśli chcemy porównać moc dwóch metod uwierzytelnienia, być może wystarczy nam określenie relatywne typu “mocniejsza” i “słabsza”. W tym przypadku możemy posłużyć się pewnymi dodatkowymi uproszczeniami (coś na zasadzie idealnie kulistych kurczaków w próżni).

No więc zacznijmy nasz eksperyment myślowy. Zacznijmy od siatki 3 na 3, ale nie jest to specjalnie istotne dla rozważań. Rozpoczynamy rysowanie wzoru na jednym z tych punktów, czyli jeśli wzorek składałby się tylko z jednej “kropki”, istniałoby 9 unikalnych wzorków.

Przedłużmy ten wzorek o kolejną kropkę. W tym miejscu trzeba się zastanowić na ile sposobów możemy wykonać ruch. Praktyczna zasada jest taka, że łączymy sąsiadujące z sobą kropki, czyli w najlepszym przypadku mamy możliwość wybrania ośmiu sąsiadujących kropek. Piszę o najlepszym przypadku, gdyż w naszej hipotetycznej sytuacji taka ilość możliwości jest dostępna wyłącznie dla kropki środkowej. Jeśli kropka, na której się aktualnie znajdujemy umieszczona jest na krawędzi siatki lub w jej rogu, ilość dostępnych możliwości zmniejsza się. W rogu mamy tylko trzy możliwości, na krawędzi – pięć.

Zmieńmy teraz siatkę w idealnie kulistego kurczaka i wyobraźmy sobie, że siatka jest “zawinięta”. To znaczy jeśli “wychodzę” za siatkę, to zostaję “teleportowany” na przeciwległy kraniec siatki. Dzięki temu eksperymentowi myślowemu możemy przyjąć, że zawsze możemy kolejną kropkę wybrać na 8 sposobów.

Przy takich założeniach ilość wzorków możemy określić z poniższego wzoru:

a * 8 ^ (n-1)

Gdzie a oznacza ilość kropek na siatce, a n długość wzorku. Dlaczego tak? Bo zgodnie z tym, co pisałem pierwszą “kropkę” możemy wybrać na tyle sposobów, ile jest kropek. Kolejną na 8 sposobów, potem znów na 8 sposobów, potem znów (...). Proste?

Co już wiemy? To, że moc “wzorka” jest mniejsza, niż moc hasła złożonego z samych cyfr o tej samej długości, co ilość “kropek” we wzorku. Bo na przykład dla zwykłego PIN składającego się z 4 cyfr mamy 10 000 możliwości, dla wzorku będzie to tylko 9 \* 8 \* 8 \* 8, czyli mniej. Możliwych jest mniej kombinacji, nawet mimo tego, że łaskawie “zawinęliśmy” siatkę. W rzeczywistości ta ilość możliwości jest jeszcze mniejsza.

Trzeba też zauważyć, że zwiększanie rozmiaru siatki ma umiarkowany efekt. Zwiększamy wyłącznie pierwszy element wzoru. Jeśli dysponowalibyśmy siatką o rozmiarze 72 punktów, to wówczas efekt byłby taki sam, jak zamiast czterech kropek połączylibyśmy ich pięć.

W dalszych rozważaniach przyjmijmy, że mamy siatkę 3x3, ale każdy może sobie policzyć te wartości również dla innych rozmiarów siatek.

Poniższa tabela zawiera porównanie ilości możliwych kombinacji kodów PIN i wzorków (siatka 3 na 3) w zależności od długości. Jak widać przewaga jest zdecydowanie po stronie PIN i rośnie drastycznie wraz ze wzrostem długości.

Długość PIN Wzorek %25
4 10000 4608 46,08%25
5 100000 36864 36,86%25
6 1000000 294912 29,49%25
7 10000000 2359296 23,59%25
8 100000000 18874368 18,87%25
9 1000000000 150994944 15,10%25
10 10000000000 1207959552 12,08%25

Przypominam, że powyższe zestawienie wciąż jest wyliczane z “litościwie” dla wzorku zapętloną siatką.

No to teraz przestańmy być tacy litościwi i rozetnijmy tę siatkę. Jak policzyć rzeczywistą ilość możliwych do uzyskania wzorków? Tym razem wzoru nie podam, ale na poczekaniu wymyśliłem sposób liczenia interesującej mnie wartości. Jaki?

Zacznijmy dla uproszczenia od siatki 2 na 2 i wzorku o długości 3 kropek. A jeszcze lepiej popatrzmy na ten rysunek:

Prawda, że oczywiste? :) Jeśli ktoś nie zrozumiał co się dzieje, to tłumaczę – liczę na ile sposobów można umieścić ostatnią kropkę. Następnie sumując ilość ostatnich kropek możliwych do umieszczenia na siatce, uzyskuję ilość unikalnych wzorków.

Jeśli wzorek ma długość 1 znaku (kropki), to ostatnią kropkę (i pierwszą przy okazji) mogę umieścić na 4 sposoby. Na każdym z dostępnych miejsc.

Teraz dodajmy kolejną kropkę. Idąc od prawego górnego rogu (0,0), to kolejną kropkę mogę umieścić w pozycjach (0,1), (1,0), (1,1). W każdym z tych miejsc umieszczam ilość “źródeł”, czyli ilość różnych kropek w polu (0, 0). Potem ćwiczenie powtarzam dla kropek źródłowych (0,1), (1,0) i (1,1). W efekcie mam w każdym z pól trzy jedynki, co w sumie daje 12 różnych wzorków o długości 2 możliwych do narysowania na tym gridzie.

W kolejnym kroku (trzecia kropka) postępuję dokładnie tak samo. Tylko, że zamiast z (0,0) przepisywać wartość 1, przepisuję wartość 3. Po prostu w tej chwili istnieją trzy różne wzorki, w których ostatni punkt znajduje się w (0,0). Tak więc mogę wygenerować kolejne 3 różne wzorki idące na pole (0,1), (1,0) i (1,1). I dalej analogicznie.

Oczywiście nie liczyłem tego ręcznie, dalej robotę robi prosty skrypt. I to z jego pomocą można uzyskać następującą tabelkę:

Długość PIN Wzorek %25
4 10000 952 9,52%25
5 100000 4624 4,62%25
6 1000000 22272 2,23%25
7 10000000 107648 1,08%25
8 100000000 519552 0,52%25
9 1000000000 2509056 0,25%25
10 10000000000 12113920 0,12%25

W tej chwili dopiero widać, jak bardzo przeszacowana było to “szacowanie z góry” i jak żenująco słabo wypada ilość możliwych wzorków o określonej długości w porównaniu do możliwych PIN o tej samej długości.

No dobrze, liczenie mamy za sobą, załóżmy nawet, że otrzymany rezultat jest prawidłowy. Mogłem się pomylić, jeśli ktoś wykaże błąd w tych wyliczeniach, to się nie obrażę. Co prawda sprawdziłem (częściowo) poprawność wyliczeń drugim skryptem, który po prostu generował unikalne wzorki i porównałem rezultaty – zgadzały się. Oczywiście ten drugi sposób liczenia (generowanie wzorków) jest dużo wolniejszy, więc takie dodatkowe sprawdzenie wykonałem tylko dla kilku pierwszych przypadków.

Wracając do tematu – mamy liczby, ale co to w praktyce oznacza? Odpowiedź na to pytanie zależy od tego, w jakie moce wyposażymy naszego atakującego.

Jeśli nasz atakujący ma przed sobą wyświetlacz z siatką 3 na 3 i ma odgadnąć właściwą kombinację, to jego szanse powodzenia są znikome. Oczywiście zakładam, że po kilku nieudanych próbach odgadnięcia wzorku, dostęp zostanie skutecznie zablokowany. Atakujący może zwiększyć swoje szanse powodzenia wykorzystując fakt, że prawdopodobieństwo wystąpienia poszczególnych wzorków o określonej długości nie jest jednakowe. Może na przykład z kieszeni wyciągnąć podobną do tej analizę typowych wzorków i spróbować kilka najbardziej prawdopodobnych.

Dla kodu PIN wygląda to w ten sposób, że atakujący próbując kody 1234, 1111 i 0000 ma ponad 18%25 szans na osiągnięcie sukcesu, w porównaniu do 3/10000, które miałby, gdyby wszystkie kody PIN były równie prawdopodobne, a atakujący dysponował tylko trzema próbami.

Co w sytuacji, gdy atakujący uzyskał dostęp do hashy haseł? Możemy przecież wyobrazić sobie sytuację, w której pod każdą kropką na siatce kryje się określony znak i użytkownik rysując wzorek, w rzeczywistości wpisuje hasło.

Jeśli atakujący ma hashe, to może je sprawdzać do woli. Jedyne czynniki, które chronią hasło przed złamaniem to:

Poprzez zastosowanie mechanizmów takich jak bcrypt, scrypt czy PBKDF2 możemy manipulować jednym z tych parametrów – czasem. Jeśli jednak przestrzeń możliwych haseł jest niewielka, skuteczność takiego podejścia jest ograniczona. Teraz proponuję ponownie odczytać zawartość powyższej tabelki (tej drugiej z wartościami wyliczonymi dla “niezawijanej” siatki) i popatrzeć jak bardzo różni się przestrzeń możliwych haseł dla “wzorka” oraz kodu PIN.

Oryginał tego wpisu dostępny jest pod adresem To ile jest tych wzorków?

Autor: Paweł Goleń