Wyniki kolejnego eksperymentu dotyczącego "przyspieszania" blind sql injection przez zmianę układu znaków, na którym wyszukiwane jest rozwiązanie, czyli kontynuacja wpisów Blind SQL Injection z wykorzystaniem regexpów oraz Szybszy(?) blind sql injection. Tym razem postanowiłem sprawdzić jak układ (kolejność) znaków wpływa na szybkość znajdowania rozwiązania przy "klasycznej" strategii podziału.
Szybszy(?) blind sql injection II: inny układ znaków
Jeśli wrócić do poprzedniego przykładu, można zauważyć, że część znaków jest znajdowana szybciej, niż pozostałe. Różnica jest niewielka, zwykle jest to 5 prób, dla niektórych znaków (właściwie pozycji) tych prób jest tylko cztery. Dla przypomnienia:
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
Skąd ta różnica? Na początku mamy 26 znaków, po pierwszym podziale jest są dwie części po 13 znaków każda. Po kolejnym podziale mamy dwie części o rozmiarze 6 i 7 znaków, (...) Możemy dojść do przypadku, gdy mamy dwa przedziały po dwa znaki każdy, lub dwa przedziały jeden o długości dwóch znaków i jeden zawierający jeden znak. W obu przypadkach mamy 4 możliwe znaki, ale ilość pytań, które pozwoli ustalić o jaki znak chodzi może być różny. W drugim przypadku może wystarczyć jedno pytanie, podczas gdy w pierwszym wymagane są dwa zapytania. Przykładowo szukając litery a i zaczynając od przedziału abcd:
ab cd a b a
I analogiczny przykład dla drugiego przypadku:
a bcd a
W tym drugim przypadku możemy zapytać o a i otrzymać odpowiedź TAK, albo zapytać o przedział bcd i otrzymać odpowiedź NIE, co również pozwala znaleźć literę a, bo pozostały przedział zawiera tylko jeden element, więc nie ma co dzielić. Takich wniosków nie można wyciągnąć, gdy oba przedziały zawierają po dwa elementy i wymagane są dwa pytania. Pierwszy po to, by wybrać właściwy przedział o długości dwóch znaków i drugie, by wybrać właściwą literę (i w ramach dziwacznych skojarzeń: TSA - Trzy zapałki).
Pomysł na przyspieszenie działania "klasycznego" blind sql injection opiera się więc na takim ułożeniu najczęściej występujących znaków, by były znajdowane (naj)szybciej. Przy większej ilości danych statystyka da o sobie znać i ilość wykonanych zapytań będzie nieco mniejsza.
Mój sposób na znalezienie lepszego niż standardowy układu znaków był prosty. Dla każdego ze znaków z rozważanego zakresu posortowanego według częstości występowania szukałem takiej pozycji, w której zostanie znaleziony najszybciej. Następnie dla kolejnego, kolejnego, kolejnego, (...). W efekcie otrzymałem między innymi takie przypadki:
aqfexmoczsjvbydpnkwiuhtlrg nkvobxyspcjudigfazlermwqth nqfabdoxwtkvcymlipsehurzjg nrgitvofbclmpazdexkyujwqsh
Wszystkie są jednakowo dobre, w teorii powinno wystarczyć około 4.51 zapytania na znak. Jest to lepiej niż przy podejściu "klasycznym", choć gorzej niż w przypadku wykorzystującym podział oparty na prawdopodobieństwie wystąpienia znaku.
Powtarzając test na wyrazach zgromadzonych w słowniku otrzymałem wynik potwierdzający te wyliczenia. Do odgadnięcia 1 277 717 słów składających się z 14 265 480 liter potrzebnych było 64 167 302 zapytań, co daje 4.498 zapytania na literę. I analogicznie dla słów angielskich: 306 211 słów składających się z 2 839 373 liter wymagało 12 898 292 pytań, co daje 4.5426 zapytania na literę.
Skoro miałem już funkcję, która generuje "szybkie" tablice, wiele zmian nie było potrzebnych, by zamiast tego generowała tablice "wolne". Kilka przykładowych tablic:
fobvrkhayustcxjeqimgnzwdlp qravltfducijnhzygmwxbekpos vraqltfducijnhzygmwxbekpos qidxuofnelrkchztvpbgymswaj vkjhtmqrspubdxyofelgzacinw
Oczekiwana ilość zapytań na literę w tym przypadku to 4.969 (eksperymentalnie dla słów angielskich daje to 4.9264 pytań na znak).
Warto jeszcze zwrócić uwagę na jeszcze jedno zagadnienie. Jako wprowadzenie zestawienie podobne do podanego w poprzednim odcinku:
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 4 5 5 5 4 5 5 5 4 5 5 5 5 4 4 5 5 5 5 5 5 5 5 5 4 5
Jest to (ponownie) ilość pytań potrzebnych do odgadnięcia określonego znaku, odpowiednio dla:
- klasycznego przypadku ze standardowym układem znaków,
- przypadku z kolejnością znaków opartą na prawdopodobieństwie wystąpienia znaków,
- klasycznego przypadku z "optymalizowanym" układem znaków,
Z algorytmami jest tak, że mają swoje lepsze i gorsze przypadki. Warto zauważyć, że w pierwszym i trzecim przypadku najgorszy przypadek to 5 pytań na znak. W przypadku drugim może to być nawet 7 pytań na znak, wszystko zależy od znaku (słowa) do odgadnięcia.
Szczerze mówiąc nie wiem, czy będzie kolejny odcinek. W szczególności nie wiem, czy zbiorę się w sobie, by sprawdzić przypadek z prawdopodobieństwem warunkowym (to, o czym wspominałem w pierwszym wpisie i o co pytał Gynvael). Powód jest prozaiczny - mój kod służący do eksperymentowania jest paskudny i w związku z tym osiągnął taki stopień makaronowatości, w którym sam nie pamiętam co która linia robi ;P. Osiągnięcie takiego stanu w Pythonie jest co prawda trudniejsze niż w Perlu, ale konsekwentne stosowanie jednoliterowych nazw zmiennych, nazw funkcji typu test1, test2, (...), testN oraz całkowity brak komentarzy, to pewna droga do sukcesu!
Jest też drugi powód, który trochę powstrzymuje moje zapędy do kolejnego eksperymentu. Dobrze to oddaje ten komentarz. Po prostu dane, które rzeczywiście trzeba wyciągnąć z bazy najprawdopodobniej nie będą chciały pasować do stworzonego w symulacji modelu. Co więcej prawdopodobnie zestaw wykorzystanych znaków będzie taki, że podejście oparte na prawdopodobieństwach będzie spisywało się gorzej, niż podejście "klasyczne". Tak jest zresztą przy tekście angielskim:
- 4.7068 pytań na znak dla wersji klasycznej,
- 4.6421 pytań na znak dla wersji opartej na prawdopodobieństwach,
- 4.5426 pytań na znak dla wersji ze "zoptymalizowanym" układem znaków,
Choć znaki były układane w oparciu o język polski, okazuje się, że i w przypadku języka angielskiego, przynajmniej tych testowych danych, taka tablica sprawdza się całkiem nieźle. Lepiej niż wersja "bazowa", a i teoretyczny "najgorszy przypadek" wcale nie jest taki zły :)
Ale są też ciekawe pomysły w komentarzach, kto wie, może coś będę kombinował w tym kierunku jednak?
Może zbadać prawdopodobieństwo wystąpienia litery na danej pozycji?
Albo prawd. wystąpienia litery w słowach 5, 6, ..., n literowych.
Może jakoś spróbować połączyć obie metody (klasyczną z 'ulepszoną')? Np pierwszy podział robiąc klasycznie, ponieważ zawsze ucinamy dokładnie połowę, a ulepszona nie zawsze utnie pół
Może eliminować zbiory liter o najmniejszym prawdopodobieństwie na początku? (to może być głupie
A może jeszcze inaczej: dowiedzieć się ile liter 'a' (najbardziej prawdopodobnych liter) jest w słowie, następnie spróbować zgadnąć ich pozycję, a potem ich sąsiadów (np samogłoski rzadko stoją koło siebie).
Może próbować odgadnąć całe sylaby?
To takich parę pomysłów po przeczytaniu tego posta :]
Wydaje mi się, że w części swoich sugestii pomijasz fakt, że rozmawiamy o zgadywaniu WSZELKICH informacji na podstawie odpowiedzi TAK/NIE.
W ten sposób musisz uzyskać informacje na temat tego, jak długie jest słowo, co kosztuje kilka(naście) zapytań. Podobnie rezultat zapytania "ile jest liter a" również ma wartość liczbową, którą musisz ustalić zadając odpowiednie pytania. Potem szukasz możliwych układów (to są chyba kombinacje bez powtórzeń), potem powtarzasz zabawę... Wszystko pięknie, tylko:
- musi to być szybsze, niż metoda "klasyczna",
- nie powinno wymagać strasznych ilości testów w "najgorszym przypadku",
Wiedza o ilości liter w słowie może decydować o wyborze strategii. Może statystki dla słów o określonej długości wyglądają trochę inaczej?
Jeśli zakładasz najgorsze przypadki to wypadało by uruchomić skrypt dla losowego ciągu znaków, oczywiście alfa-num Trzeba poczynić pewne założenia, których dotyczą dane badania. Żeby nie przesadzić z tymi 'najgorszymi przypadkami'. I czy to jest sztuka dla sztuki (losowe polskie słowa), czy coś użytecznego (chyba najczęściej tabele maja angielskie nazwy, próbować podejść do problemu ze słownikiem najczęściej nazywanych tabel/wzorców nazw/innych cech charakterystycznych).
Lekko to podchodzi pod sztuczną inteligencje, może spróbować zbudować bazę wiedzy, i do wymyślania metod posłużyć się prologiem? To jest jak gra, trzeba znaleźć najlepszą strategie :]
Pozdrawiam
Tak naprawdę nie musisz uruchamiać testowego skryptu, by móc z dużą dokładnością oszacować ilość potrzebnych zapytań do odgadnięcia słowa o określonej długości. Do tego wystarczy posiadanie informacji jak wiele prób jest potrzebnych do odgadnięcia określonego znaku. Następnie do tego dodaje się (w sensie - mnoży) prawdopodobieństwo wystąpienia określonego znaku i już z grubsza wiadomo jak to będzie wyglądać. Wdzięcznym tematem będą tu na przykład hashe haseł, bo prawdopodobieństwo wystąpienia poszczególnych znaków jest takie samo.
Najgorszy przypadek w tym kontekście też łatwo oszacować, wystarczy uwzględnić ten znak, który "kosztuje" najwięcej pytań i przemnożyć go przez ilość znaków do odgadnięcia. Oczywiście taki przypadek prawdopodobnie się nie zdarzy, ale mimo wszystko fajnie wiedzieć, że program nie pójdzie w maliny, tylko dlatego, że ktoś złośliwie wybrał sobie login złożony z 32 znaków z
Tak, to jest jak gra i trzeba znaleźć najlepszą strategię. A właściwie nie najlepszą, tylko taką, która będzie się sprawdzała najlepiej przez większość czasu.
Z prologiem mam umiarkowanie pozytywne doświadczenia, więc nie chcę się jakoś specjalnie wymądrzać, ale wydaje mi się, że lepszą strategią mogą być jednak symulacje.
a - 35%
b - 25%
c - 15%
d - 10%
e - 10%
f - 5%
zamiast dzielić abc def w pierwszym pytaniu, dzielisz ab (60%; po pierwszym znaku, którego dodanie przekroczy/zrówna się z 50%) cdef (40%). Jeśli będzie ab, to w następnym pytaniu dzielisz na a (mającym 35/60 czyli 58%) i b. Jeśli masz pecha i jest cdef,to dzielisz cd (25/40 czyli 62%) i ef (38%). Potem c i d lub e i f. W najgorszym wypadku masz 3 zapytania (z 40% szans, statystycznie), w najlepszym 2 (60% szans), czyli średnio 2,4 pytania, zamiast 3 przy klasycznym podejściu z podziałem binarnym. Wpływ podziału 3 elementów i odpowiedzi negatywnej, która wskazuje pomijam, bo też będzie miał miejsce.
Czy to jest to, o co Ci chodziło, czy coś mi umknęło?
Za to jeszcze jedna uwaga na podstawie http://en.wikipedia.org/wiki/Letter_frequency - jak sugerował BP w pierwszym komentarzu, samo prawdopodobieństwo nie jest aż tak istotne, ważna jest też pozycja. Co z tego, że e ma prawie 13% (angielski), skoro dla pozycji pierwszej ma marne 2%? Ewentualnie, zamiast tego (i chyba lepiej nawet) prawdopodobieństwa określać na podstawie poprzedniego znaku (łańcuchy Markowa).
Pomysł zarzuciłem, ale może do niego wrócę tak dla sprawdzenia czy będzie wyraźnie lepiej.
Z natury jestem leniwy, gdyby nie naciski w komentarzach, to bym ten trzeci wpis odłożył na świętego nigdy