Szybszy(?) blind sql injection II: inny układ znaków

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.

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:

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:

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?

Oryginał tego wpisu dostępny jest pod adresem Szybszy(?) blind sql injection II: inny układ znaków

Autor: Paweł Goleń