Paweł Goleń, blog

Na początek przypomnienie na czym polega specyfika blind sql injection. Polega ona na tym, że atakujący o zawartości bazy danych wnioskuje na postawie informacji pośredniej, konkretnie na podstawie warunku prawda/fałsz. Można to porównać do zabawy w odgadywanie o czym myśli druga osoba poprzez zadawanie pytań, na które można uzyskać wyłącznie odpowiedź tak lub nie.

W przypadku odczytywania danych z bazy danych (dla uproszczenia - danych tekstowych) można przyjąć kilka podejść. Po pierwsze można próbować uzyskać potwierdzenie, czy jakaś wartość w bazie się znajduje, czy nie. Jest to klasyczny przykład brute force, kompletnie nieprzydatny w praktyce. Można jednak zauważyć, że każdy tekst składa się tak naprawdę z liter umieszczonych na określonej pozycji. Jeśli chcemy odczytać wartość przyklad, wówczas szukamy litery na pierwszej pozycji, drugiej, trzeciej.. Można to robić wprost przez sekwencyjne porównywanie czy litera na pierwszej pozycji to a, b, c, d, .... p. Jest to jednak rozwiązanie mało wydajne. Oczywiście, można próbować je optymalizować w określony sposób. Na przykład zakładając, że tekst jest w danym języku, można sortować próbowane znaki na podstawie występujących znaków. Można również próbować wykorzystywać łańcuchy Markowa by określić, że skoro na poprzednim znaku wystąpiła określona wartość, to kolejną wartością będzie najprawdopodobniej (...). Nie tędy jednak droga. Zamiast tego można użyć wyszukiwania binarnego (bisekcji).

Wszystkie znaki można przedstawić za pomocą ich kodów ASCII, co w praktyce sprowadza problem do znalezienia właściwej liczby (tej, o której "ktoś myśli") w pewnym zakresie wartości. Zadanie to rozwiązuje się w ten sposób, że wybiera się wartość ze środka przedziału i sprawdza, czy wartość ta jest większa, niż ta, której się szuka. W zależności od odpowiedzi ustala się nowe granice przedziału. Na przykład dla wartości od 0 do 9 i liczby 3 pierwszą sprawdzoną wartością jest 4 (bo (0+9)/2 po zaokrągleniu daje 4). Szukana liczba 3 jest mniejsza od 4, tak więc nowy przedział to 0 do 4. Tu wartością znowu staje się 2, liczba 3 jest większa od 2, więc przedział został zawężony do przedziału od 2 do 4. Koncepcja jest chyba oczywista, zawsze można przeczytać dodatkowo: Metoda równego podziału, wyszukiwanie binarne.

Wykorzystanie LIKE w zasadzie nie jest niczym innym, niż modyfikacją wyszukiwania brute force. Dla przyklad można zrobić iść sekwencyjnie: %a%. Wiemy, że wartość ta występuje w tekście, ale nie wiadomo ile razy, na jakiej pozycji. Znaki "obok" trzeb sprawdzać znów poprzez wyszukiwanie liniowe. Przy każdej próbie zmniejszamy zakres tego, co mamy do przeszukania tylko o tę jedną, sprawdzoną wartość. W przypadku bisekcji zakres ten zmniejszamy o połowę (tego, co dostaliśmy na wejściu). Czyli (w przypadku 26 znaków) przy przeszukiwaniu brute force dla znalezienia jednej litery w najgorszym przypadku musimy wykonać aż 26 operacji, podczas gdy w przypadku bisekcji znacznie mniej (prawdopodobnie 4, ale jest późno, mogę nie uwzględniać przypadków granicznych). Różnica wydajności jest chyba oczywista.

EDIT: Szybkie sprawdzenie bisekcji dla wartości z zakresu 0 do 256 pokazuje, do określenia szukanej wartości potrzebne jest od 1 do 9 kroków, co przekłada się na od 2 do 18 zapytań SQL. Po prostu przy bisekcji ważne są trzy stany: większy, mniejszy, równy. Można to ustalić przy pomocy maksymalnie dwóch zapytań SQL (czy coś jest większe, lub czy coś jest mniejsze). Teoretycznie można próbować w każdym kroku wykonywać tylko jedno porównanie i sprawdzać inne warunki stopu, ale nie koniecznie jest to rozwiązanie bardziej wydajne.