Tak, jest to nawiązanie do wcześniejszego wpisu: Blind SQL Injection z wykorzystaniem regexpów. Postanowiłem sprawdzić, czy rzeczywiście uda się zmniejszyć ilość pytań, które trzeba zadać, by odgadnąć słowo. Rezultat: 66976481 63650628. Lepiej?
Szybszy(?) blind sql injection
Najpierw krótki opis. Uwzględniałem tylko znaki z zakresu: abcdefghijklmnopqrstuvwxyz. Jako źródło danych o częstotliwości występowania znaków wykorzystałem ten słownik języka polskiego. W teście uwzględniałem wyłącznie prawdopodobieństwo wystąpienia określonego znaku, bez "kontekstu", czyli nie uwzględniam prawdopodobieństwa wystąpienia znaku pod warunkiem, że wcześniej wystąpił określony znak. Być może w przyszłości :)
Na podstawie tych danych wejściowych utworzyłem listę znaków z podanego zakresu posortowaną po prawdopodobieństwie ich wystąpienia, informacja o prawdopodobieństwie wystąpienia określonego znaku również była zawarta w tej liście. Następnie zamiast dzielić określony zakres znaków na połowy, dzieliłem je na dwie części o (prawie) równych prawdopodobieństwach wystąpienia znaku w każdej z części. Jak wygląda efekt? Tak jak napisałem we wstępie. Dla danych testowych "odgarnięcie" wszystkich słów w testowym słowniku przy pomocy "klasycznej" bisekcji wymagało 66976481 pytań. W zmodyfikowanym podejściu tych pytań było 63650628. Różnica zauważalna, ale nie powalająca.
Dla przykładu zastanówmy się nad dwoma słowami: akwarystkach oraz akwarystkami. Rezultat testu wygląda następująco:
akwarystkach 57 58 akwarystkami 57 56
Pierwsza wartość liczbowa oznacza ilość prób, które trzeba było wykonać przy podejściu "klasycznym", druga wartość to podejście zmodyfikowane. Odgadnięcie jednego słowa jest wolniejsze, drugiego - szybsze. Sumarycznie - wymagane jest dokładnie tyle samo zapytań.
Dla porównania zobaczmy jak "dochodzi się" do odpowiedzi. W pierwszym przypadku (podejście klasyczne):
abcdefghijklmnopqrstuvwxyz abcdefghijklm abcdef abc a
Dla wyjaśnienia - podane zakresy znaków to zakres, który "wchodzi" do funkcji. Zakres ten jest dzielony na dwie części i następuje sprawdzenie, w której części znajduje się szukany znak. Czyli:
abcdefghijklmnopqrstuvwxyz
Został podzielony na dwie części:
abcdefghijklm nopqrstuvwxyz
Ponieważ znak a znajduje się w pierwszym zakresie, stanowi on wejście dla kolejnego wywołania funkcji, w którym ponownie jest dzielony i (...). I tak do skutku, gdy w przedziale zostaje tylko jeden znak będący tym poszukiwanym.
W podejściu "zmodyfikowanym" jest nieco inaczej:
aioenyzwrcmskptuldbjghfvxq aioenyz aio ai a
W powyższym przykładzie widać wyraźnie, że zakres możliwych znaków dzielony jest na dwie części, ale podział ten nie jest równy. W tym wypadku prawdopodobieństwo, że znak wystąpi w pierwszej części jest z grubsza takie samo, jak to, że wystąpi w drugiej. Dlaczego akurat takie podejście wybrałem? Bo chyba jest najbardziej efektywne. Przy symulacji różnych strategii podziału właśnie ta okazała się najefektywniejsza, a przynajmniej było to lokalne minimum.
Ilość pytań potrzebnych do znalezienia odpowiedzi w obu przypadkach jest taka sama, przy czym można zaobserwować, że drugie podejście szybciej zawęża przedział, w którym znajduje się poszukiwany znak. Przynajmniej w tym przypadku, bo szukana była litera a, czyli ta najbardziej prawdopodobna (przynajmniej według analizy danych, które wybrałem jako źródło danych do wykonania statystyki).
Jak wygląda to w przypadku litery q?
abcdefghijklmnopqrstuvwxyz nopqrstuvwxyz nopqrs qrs q aioenyzwrcmskptuldbjghfvxq wrcmskptuldbjghfvxq tuldbjghfvxq jghfvxq q
Jak widać w tym przypadku zakres jest zawężany wolniej, choć w efekcie odpowiedź jest znajdowana po tej samej ilości pytań.
Interesujące może być również to zestawienie:
a b c d e f g h i j k l m n o p q r s t u v w x y z 4 5 5 4 5 5 4 5 5 5 5 5 5 4 5 5 4 5 5 4 5 5 5 5 5 5 4 5 4 5 4 7 6 7 4 6 5 5 5 4 3 5 4 5 5 6 6 7 5 7 4 4
Pokazuje ono ilość pytań, które trzeba zadać w celu odgadnięcia konkretnej litery z alfabetu, wyniki dotyczą odpowiednio "klasycznej" i "zmodyfikowanej" metody. Jeśli zsumować te wyniki, to dla wersji klasycznej w sumie wymagane są 124 próby podczas gdy dla wersji zmodyfikowanej wymagane są 132 próby. Wersja klasyczna jest jednak wydajniejsza?
Nie do końca, co zresztą pokazał cytowany na początku wynik testu. Dla wydajności metody liczy się zarówno ilość prób potrzebnych na odgadnięcie określonego znaku, jak i prawdopodobieństwo wystąpienia określonego znaku. W efekcie fakt, że odgadnięcie znaków typu f, h, v czy x jest wyraźnie wolniejsze w przypadku metody zmodyfikowane może zostać zniesiony przez efekt szybszego znajdowania znaków e, i czy o, które występują w naszym języku z większym prawdopodobieństwem. Oczywiście wszystko się zmieni, jeśli z jakiegoś powodu prawdopodobieństwo występowania znaków będzie inne od oczekiwanego.
Na zakończenie jeszcze raz podsumowanie: do prawidłowego odgadnięcia 1 277 717 słów liczących w sumie 14 265 480 liter w przypadku podejścia klasycznego potrzebnych było 66 976 481 pytań (co daje 4.695 pytania na literę). Do tego samego zadania wersja zmodyfikowana wymagała 63 650 628 pytań (co daje 4.4618 pytania na literę). Dla porównania podam, że wartości oczekiwane wyliczone na podstawie ilości pytań wymaganych do odgadnięcia określonej litery i prawdopodobieństwa jej wystąpienia wynosiły odpowiednio 4.76084754802 oraz 4.45636670279, czyli są to wartości zbliżone do końcowych wyników eksperymentu. Przyznam się przy okazji, że przy liczeniu prawdopodobieństwa wystąpienia określonych znaków uwzględniłem nieco inny zbiór danych, niż ten, na którym ostatecznie wykonałem testy.
Dla porównania w przypadku pliku Wordlist.txt (standardowy plik dostarczany wraz z Cain&Abel) wyniki są następujące:
- 306 211 słów,
- 2 839 373 znaków,
- 13 364 610 pytań dla sposobu klasycznego (4.7068 pytań na znak),
- 13 180 865 pytań dla wersji zmodyfikowanej (4.6421 pytań na znak),
Angielski to jednak trochę inny język, niż polski. Czy warto się bawić w takie "akrobacje" by zmniejszyć ilość zapytań o kilka procent? Wnioski we własnym zakresie :)
...będzie jeszcze jeden post na ten temat, mam jeszcze jeden pomysł na eksperyment.
Planujesz powtórzyć ekspryment dla wersji z wykorzystaniem kontekstu (tj. prawdopodobieństwo wystąpienia znaku X po znaku Y)? Sądzę, że tutaj rezultat byłby lepszy.
Hmm nie jestem pewien czy słownik języka polskiego jest dobrym źródłem do stworzenia tablicy statystyk występowania danego znaku. Raczej słownik ograniczony do języka potocznego i w użytku codziennym byłby bardziej adekwatny imo (chodzi o pominięcie słów bardzo rzadko używanych/archaicznych/bardzo specialistycznych).
Ale z drugiej strony... pewnie wyniku i tak by to za bardzo nie zmieniło.
Jestem bardzo ciekaw kolejnego postu z tej serii ;>
Cheers!
Tak zupełnie z innej beczki - umiejętność (kiepskiego) programowania pozwala czasem na stworzenie symulacji ciekawych problemów z "prawdziwego życia", których wyniki pozwalają podjąć decyzję (czy lepszą - kwestia dyskusyjna) w naszym świecie specjalizującym się w robieniu wody z mózgu. Choćby takie "trywialne" zagadnienie jak wybór najlepszej oferty abonamentu z uwzględnieniem własnej specyfiki korzystania z telefonu
Np. możnaby spróbować zawężyć zbiór znaków, etc. Przykładowo, jeśli nie ma się pojęcia co może być w kolumnie to zazwyczaj trzeba szukać ASCII 32-126 włącznie. Więc wysyłając na początku kilka zapytań regexpowych dla całego ciągu typu [A-Za-z] a potem [a-z] pozwoliłoby znacznie zwężyć przedział w którym się szuka.
Nie wiem czy możnaby/wartoby schodzić poniżej [a-z] z zapytaniami natomiast.
Ofc, implicit cały czas chodzi o prawdopodobieństwa.
Natomiast zastanawiam się, czy jakimiś mega-sprytnymi regexpami nie można by ustalić plus-minus zbioru znaków jakie występują w całym ciągu. Any ideas? ;>
Cheers,
Jakimiś mega-sprytnymi chyba nie, ale można po prostu kolejno sprawdzić:
'^a+$'
'^[ab]+$'
'^[abc]+$'
'^[abcd]+$'
'^[abcde]+$'
...
'^[abcdefghijklmnopqrstuvwxyz0123456789]+$'
jak w końcu zwróci true, poznasz zbiór znaków
Być może sensowną strategią byłoby zapytanie o zbiory najbardziej prawdopodobnych znaków, kolejno o 13, 25, 50 i 75 znaków. W najgorszym przypadku ustalenie danych zajęłoby (wariant klasyczny) + 4 zapytania, natomiast w najlepszym jakieś 4. Wszędzie oczywiście jakieś ułamki, a przybliżenia biorę z głowy i mogę się mylić +/- 1.
Ale i tak wszystko się rozbija o to, co w tej bazie, tabeli, wierszu i kolumnie właściwie jest.
Wg mnie Twoje wyniki potwierdzają, że nie warto bawić się w prawdopodobieństwa.
W rzeczywistości wiele nazw będzie mieszanką pol/eng a do tego dojdą skróty, w których często brak popularnych samogłosek i jeśli już różnica jest minimalna to przy zwiększeniu pomyłki w określaniu prawdopodobieństwa występowania znaków będzie jeszcze gorzej.
Masz rację, wynik końcowy (ilość wymaganych zapytań) mocno zależy od tego, czy prawdopodobieństwo wystąpienia określonego znaku jest zgodne z "rzeczywistym" prawdopodobieństwem dla danych znajdujących się w atakowanej bazie. W niekorzystnych przypadkach wydajność takiego "zmodyfikowanego" podejścia może okazać się dużo niższa, niż podejścia "klasycznego".