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 | % |
4 | 10000 | 4608 | 46,08% |
5 | 100000 | 36864 | 36,86% |
6 | 1000000 | 294912 | 29,49% |
7 | 10000000 | 2359296 | 23,59% |
8 | 100000000 | 18874368 | 18,87% |
9 | 1000000000 | 150994944 | 15,10% |
10 | 10000000000 | 1207959552 | 12,08% |
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 | % |
4 | 10000 | 952 | 9,52% |
5 | 100000 | 4624 | 4,62% |
6 | 1000000 | 22272 | 2,23% |
7 | 10000000 | 107648 | 1,08% |
8 | 100000000 | 519552 | 0,52% |
9 | 1000000000 | 2509056 | 0,25% |
10 | 10000000000 | 12113920 | 0,12% |
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% 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:
- rozmiar przestrzeni haseł do przeszukania (ilość możliwych haseł),
- czas potrzebny na sprawdzenie jednego hasła (wyliczenie hasha i sprawdzenie go z posiadaną wartością),
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.
Ja wspomniane kropki bym potraktował jak znaki.
Przyjmijmy, że 'klawiatura' jest 3x3 (9 znaków), a hasło jest czterowierzchołkowe. Po drugiej stronie ustawmy klawiaturę numeryczną 1-9 (9 znaków). Różnica w tym podejściu od zwykłego pinu jest taka, że nie można ponownie wprowadzić ten sam znak.
Rozmiar przestrzeni dla 4 znakowego hasła
wzorek(wariacja bez powtórzeń): 9*8*7*6 = 3 024
pin (wariacja z powtórzeniami): 9*9*9*9 = 6 561
Prawdą jest to, że metoda 'wzorkowa' nie jest żadnym zabezpieczeniem.
btw, pisałem o czymś podobnym na blogu:
http://donpiekarz.pepiniera.net/blog/2012/07/02/safelock-v01/
Moim zdaniem można w miarę prosto oszacować to tak:
dla gridu 3x3 mamy
4 pola * 3 możliwości ruchu
4 pola * 5 możliwości ruchu
1 pole * 8 możliwości ruchu
czyli dla n=2 mamy
4*3 + 4*5 + 1*8 = 40 unikalnych ścieżek.
zamieniając to na procenty mamy
4/9 * 3 + 4/9 * 5 + 1/9 * 8 = 4.44(4)
i potem
n1 = 9
n2 = n1 * 4.44 = 39.96 (=~ 40, różnica wynika z niedokładności zaokrąglenia 4.44(4) do 4.44)
nX = n1 * 4.44^(X-1)
czyli
n3 = 177
n4 = 787
Co ważne - im większy grid tym bardziej odchodzimy od tego co byśmy uzyskali wybierając dowolne pola (pin). Dla gridu 5x5 współczynnik wychodzi ok. 5.76 - możemy to interpretować jako hasło tworzone z 6 różnych znaków (zamiast 25 różnych znaków dla swobodnie wybieranego pinu)
normalne hasło (80 symboli) = 6.32 bita na znak
PIN (cyfry) = 3.32 bita na znak
Łączenie kropek = 2.52 bita na znak
Czyli 8 znakowe hasło (50 bitów) przekłada się na rysunek łączący 20 kropek na gridzie 5x5.
W skrócie - Twoje obliczenie 9*8... byłoby prawdziwe wtedy, gdy kolejna kropka mogłaby być wybrana w sposób dowolny, a jedynym ograniczeniem byłoby to, że nie może być wykorzystana poprzednia kropka. To nie odpowiada warunkom opisanego przeze mnie zadania. Z kolei ja chciałem opisać logowanie przez kropki w Androidzie i jednak mój opis nie do końca się zgadzał z tym, jak ten mechanizm rzeczywiście działa.
Co do założeń to interesował mnie model zgodny z logowaniem w Alior Sync'u gdzie hest grid 5x5, jak najbardziej możliwe są powtórzenia (choć nie jest to intuicyjne, bo powtórzenia nie są oznaczone wizualnie), nie moża przechodzić przez ściany ani na inne punkty niż sąsiadujące.
Akurat dla n=2 się to zgadza, bo dla n=1 każde pole na siatce jest jednakowo prawdopodobne. Dla n=3 już się rozjedzie, bo dla n=2 są pola bardziej/mniej obłożone i ten współczynnik już nie jest do końca prawidłowy.
Dla 5x5 eksperymentalnie współczynnik dąży do 6.46
Jest to więcej, ale nadal malutko (2.7 bita na znak a nie 2.5).
Tam powinno być:
wzorek: 8*8*8*8 = 4 096
Ponieważ z każdego punktu możemy pójść do jednego z pozostałych punktów (8).