Łamanie haseł przy pomocy rainbow table

Projektując bazę danych dla aplikacji w końcu przychodzi ten moment kiedy trzeba określić co zawierać będzie tabela użytkowników. Zazwyczaj jest to login, adres email, imię, nazwisko oraz hasz (skrót) hasła użytkownika. Nic w tym dziwnego, bo trzymanie haseł jawnie lub przy użyciu szyfrowania nie jest rozsądne, a co za tym idzie nie powinno być praktykowane. Z drugiej strony, biorąc próbę statystyczną 100 programistów, około 90 na pytanie „dlaczego trzymasz w swojej bazie skrót hasła użytkownika”, odpowiedziałby „bo hasza nie da się odhaszować”. I teoretycznie jest to prawda jednak stwierdzenie, że jest to rozwiązanie w 100% bezpieczne już prawdziwe nie jest.

Na początek zadajmy sobie pytanie, czym jest funkcja skrótu? Według Wikipedii jest to:

 

Funkcja przyporządkowująca dowolnie dużej liczbie krótką, zawsze posiadającą stały rozmiar, niespecyficzną, quasi-losową wartość, tzw. skrót nieodwracalny.

 

Oprócz tego taka funkcja powinna spełniać następujące kryteria (również według Wiki):

  • Odporność na kolizję – brak praktycznej możliwości wygenerowanie dwóch dowolnych wiadomości o takim samym skrócie
  • Odporność na kolizje konkretnych wiadomości — brak praktycznej możliwości wygenerowania wiadomości o takim samym skrócie jak wskazana wiadomość
  • Jednokierunkowość — brak możliwości wnioskowania o wiadomości wejściowej na podstawie wartości skrótu. Zmiana dowolnego pojedynczego bitu wiadomości powinna zmieniać średnio połowę bitów skrótu w sposób, który nie jest istotnie podatny na kryptoanalizę różnicową.

 

Z tego wynika, że nasz statystyczny programista ma racje i faktycznie jedynym sposobem na złamanie hashu jest wybranie dowolnego hasła, obliczenie jego skrótu i porównanie z zadanym. Jeżeli skróty są identyczne oznacza to, że zgadliśmy, w przeciwnym przypadku szukamy od początku. Jest to tzw. atak brute-force. Problem w tym, że łamanie hasła tą metodą jest dość… nieefektywne. Załóżmy, że przeciętne hasło użytkownika ma 8 znaków i składa się jedynie z małych znaków alfanumerycznych (bez polskich znaków). Wobec tego możliwych kombinacji jest:

(26 + 10) ^8 = 2821109907456

Przyjmując, że obliczenie jednego skrótu zajmie nam 0.1 sek, złamanie hasła (w pesymistycznym przypadku) zajmie nam jedyne kilka lat:

(2821109907456 * 0.1)/(3600 * 24 * 365) = 8945.68

Trochę dużo, prawda?

Druga metoda zakłada zapisywanie kolejno: hasła i jego, skrótu, budując tym samym słownik. W przypadku chęci „odhaszowania” skrótu, sprawdza się czy istnieje taki w bazie. Jeżeli tak, zwrócone zostaje hasło zapisane w wierszu. Jeżeli skrót nie występuje, no cóż… operacja się nie udała. Metoda ta może się wydawać głupia, jednak czasem jest ona wystarczająca do złamania hasła. Wystarczy by użytkownik był posiadaczem „oryginalnego” hasła jak test123, admin, albo qwerty. Takie hasła raczej na pewno znajdą się w słowniku, a ich odnalezienie będzie możliwe w relatywnie krótkim czasie. Problem tego podejścia to ogrom danych jakie trzeba przetrzymywać i przeglądać. Patrząc na liczbę kombinacji 8 znakowego hasła, widać że mija się to z celem.

Przejdźmy teraz do tytułowych tęczowych tablic. Idea jest genialna w swojej prostocie i łączy w pewnym stopniu dwa poprzednie rozwiązania. Żeby przedstawić zasadę ich tworzenia posłużę się przykładem. Załóżmy, że chcielibyśmy stworzyć tęczową tablicę dla 4 znakowych haseł, które dla uproszczenia posiadają jedynie cyfry 0-9 oraz znaki a-f.

Pierwszym krokiem będzie zadanie dowolnego 4 znakowego hasła wejściowego. Niech będzie to: abcd. Następnie obliczmy skrót hasła przy pomocy funkcji skrótu ( w tym przypadku będzie to MD5). Otrzymany skrót to:

e2fc714c4727ee9395f324cd2e7f331f

Następnie stwórzmy funkcję redukcyjną, która z otrzymanego skrótu wygeneruje nam dowolne 4 znakowe hasło spełniające założenia. Operacje, które wykonamy w ramach funkcji zależą tylko i wyłącznie od nas. Ważne jest jedynie to, aby móc powtórzyć ten proces w przyszłości. Dla naszego przykładu funkcja będzie zwracać ostatnie 16 najmniej znaczących bitów, które zamieni w stringa. Będzie to więc ciąg 331f. Następnie powtórzmy proces n-razy, za każdym razem haszując ciąg otrzymany z funkcji redukcyjnej. Dla uproszczenia przykładu przyjmijmy 3 iteracje. Wobec tego kolejno otrzymanym skrótem będzie:

6735c53d219057a800a1855241f0b818

(argumentem w kolejnej iteracji będzie teraz b818)

ostatni obliczony skrót to:

f4c4da40790b54656d96302ff7a7f2b4

Po zakończonym procesie dodajmy do naszej tęczowej tablicy wiersz zawierający hasło od którego rozpoczęliśmy haszowanie, ostatni otrzymany skrót oraz liczbę iteracji. W tym przypadku będzie to:

abcd | f4c4da40790b54656d96302ff7a7f2b4 | 3

Zauważcie, że tym ruchem zamknęliśmy wszystkie uzyskane hasła oraz ich skróty w jednym wierszu. Cały proces „seedowania” naszej tablicy rozpoczynamy ponownie generując 4 znakowe hasło itd. Ilość wierszy tablicy będzie wpływała bezpośrednio na powodzenie procesu łamania skrótów. Ok, tablica jest gotowa, więc czas dowiedzieć się jak jej użyć? Proces jest bardzo prosty. Chcemy złamać skrót:

6735c53d219057a800a1855241f0b818

Postępujemy następująco. Sprawdzamy czy skrót występuje w jakimkolwiek wierszu naszej tablicy. Jeżeli tak, bierzemy hasło którym seedowaliśmy dany wiersz po czym przechodzimy cały proces jego tworzenia od początku do momentu kiedy otrzymamy poszukiwany skrót (zapisując do zmiennej hasło, które aktualnie haszujemy). Jeżeli jednak żadnej wiersz nie zawiera pożądanego skrótu, używamy tej samej funkcji redukcyjnej, której używaliśmy do tworzenia wierszy, aby wygenerować ze skrótu nowe hasło, haszujemy je po czym ponownie sprawdzamy czy taki skrót zawiera się w naszej tablicy. W przypadku kiedy liczba iteracji przekroczy tą zapisaną w wierszu, wiemy że nie zawiera on naszego hasła. Zobaczmy jak to się ma do naszego przypadku, zakładając że nasza tęczowa tablica posiada jedynie jeden wiersz, który wyliczyliśmy wcześniej. Sprawdzamy czy skrót zawiera się jakimś wierszu. Nie. W związku z tym, używamy funkcji redukcyjnej, użytej przy wyliczaniu wiersza. Otrzymanym hasłem jest b818, a jego skrótem:

f4c4da40790b54656d96302ff7a7f2b4

Sprawdzamy czy ten skrót występuje w tablicy.Trafiliśmy! Teraz wystarczy wziąć z wiersza hasło (abcd) i przejść proces analogiczny do tworzenia wiersza do momentu otrzymania skrótu, który chcieliśmy złamać. W tym przypadku rezultat otrzymamy po 2 iteracji. Naszym hasłem było 331f !


Przykład mam nadzieję nie był nadto skomplikowany. Posiada on jednak jedną wadę. Nasza tęczowa tablica jest podatna na kolizje oraz zapętlenia, które mogą się przytrafić podczas haszowania coraz to kolejnych haseł. Dzieje się tak, ponieważ ciągle używaliśmy tej samej funkcji redukcyjnej, wobec czego wyniki dla tych samych skrótów zawsze będą identyczne. Problem ten możemy znacznie zredukować poprzez zastosowanie innej funkcji redukcyjnej dla każdego kroku generowania wiersza tablicy. Właśnie stąd wzięła się nazwa tęczowych tablic. Gdybyśmy każdej funkcji redukcyjnej przypisali inny kolor, otrzymalibyśmy tęczę.

Jak wygląda w takim razie proces łamania skrótu z wieloma funkcjami redukcyjnymi? Analogicznie do przedstawionego przykładu. Różnica polega tylko na doborze funkcji redukcyjnej.  Gdybyśmy użyli różnych funkcji (np. f1, f2, f3… fn), wówczas przy wyszukiwaniu skrótu w tablicy, w kolejnych iteracjach wykorzystalibyśmy najpierw fn potem fn-1 itd. W przypadku odnalezienia skrótu w dowolnym wierszu, hasło „wydobywamy” korzystając już kolejno z f1,f2 itd, aż się dokopiemy 🙂


 

Jak więc bronić się przed takim atakiem? Solić Panie ! Solić ! Dla tych, którzy nie wiedzą o co chodzi szybka lekcja:

Za naszą „sól” przyjmujemy generowany, losowy ciąg znaków. W zasadzie im dłuższy, tym lepszy. Następnie przed zahaszowaniem hasła użytkownika, doklejamy do niego sól. Ten oto powstały ciąg znaków dopiero haszujemy, a sól zapisujemy jawnie w kolumnie obok. Co nam to daje? W przypadku użycia tęczowych tablic teraz oprócz znalezienia ciągu, który pasuje do skrótu, musimy jeszcze wiedzieć co z tego jest solą, a co hasłem.

 

Myślę, że temat jest ciekawy i na pewno godny rozważenia w Waszych przyszłych projektach. Być może w niedalekiej przyszłości napiszę taką tęczową tablicę, a wszelkimi refleksjami podzielę się z Wami na blogu 🙂

You may also like...