Tęczowe Tablice (Rainbow Tables) – wstęp, algorytm, tutorial

Mamy poniżej kilka przykładowych haseł oraz ich hashów MD5:

MD5( „1729” ) = 25e2a30f44898b9f3e978b1786dcd85c
MD5( „2523” ) = a6d259bfbfa2062843ef543e21d7ec8e
MD5( „6259” ) = 99503bdd3c5a4c4671ada72d6fd81433
MD5( „9950” ) = 09a630e07af043e4cae879dd60db1cac
MD5( „0963” ) = d1cbdbc9cacee6c8b133c7a92a83bcca


A. Łamanie haseł metodą Brute Force

Jeżeli czas potrzebny do obliczenia jednego hashu będzie stosunkowo duży (np. 1 sek.), to nie będzie się opłacać stosowanie metody Brute Force.

W przypadku powyższego, przykładowego czasu (1 sek.), sprawdzenie metodą Brute Force powyższych 5-ciu haseł wyniosłoby: 5 sek.

Przy dużej ilości haseł, rozwiązanie takie jest nieefektywne dla maszyn klienckich. W przypadku powyższego czasu (1 sek), sprawdzenie metodą Brute Force wszystkich haseł składających się z 4 znaków wyniosłoby:

Liczba znaków alfanumerycznych: 95
Liczba wariacji z powtórzeniami: 95*95*95*95 = 84022750

Czas = 84022750 * 1s = ~3 lata


B. Łamanie haseł metodą Słownikową

Jeżeli czas potrzebny do wyszukania w bazie danych jednego hashu i odpowiadającego mu hasła jest znacznie krótszy od wyliczenia go (np. 0.01 sek.), to bardziej będzie opłacać się dokonać ataku Słownikowego.

Należy jednak pamiętać, że przy ataku słownikowym, konieczne jest, aby twórca słownika wcześniej dokonał stosownych obliczeń hashów – być może w krótszym czasie niż zrobiła by to zwykła maszyna kliencka.

W przypadku powyższego czasu (0.01 sek.), sprawdzenie metodą Słownikową powyższych 5 haseł wyniosłoby: 0.05 sek.

Przy dużej ilości haseł, rozwiązanie takie jest o wiele bardziej efektywne niż metoda Brute Force. W przypadku powyższego czasu (0.01 sek.), sprawdzenie metodą Słownikową wszystkich haseł składających się z 4 znaków wyniosłoby:

Liczba znaków alfanumerycznych: 95
Liczba wariacji z powtórzeniami: 95*95*95*95 = 84022750

Czas = 84022750 * 0,01s = ~233h.

Przy dużej ilości haseł, większym problemem niż czas, staje się rozmiar słownika. Dla przykładu dla wszystkich haseł alfanumerycznych składających się z 4 znaków rozmiar słownika wynosiłby:

Liczba znaków alfanumerycznych: 95
Liczba wariacji z powtórzeniami: 95*95*95*95 = 84022750

Razmiar haseł = 84022750 * 1B = 84022750 B = ~80 MB
Razmiar hashów = 84022750 * 16B = 1344364000 B = ~1282 MB
RAZEM: ok. 1,2 GB


C. Łamanie haseł przy pomocy Rainbow Tables

Tęczowe Tablice wykorzystują pewien sprytny zabieg, który łączy w sobie obie powyższe metody łamania haseł, biorąc z nich co najlepsze. Opiszę to w kilku prostych krokach.


1. Zdefiniujmy funkcję redukującą (reduction function)

Funkcja redukująca to arbitralnie dobrana funkcja (dostosowana do naszych indywidualnych potrzeb), która na wejściu dostaje hash (np. MD5), a na wyjściu generuje zupełnie nowe hasło. Funkcja ta nie ma na celu obliczenie z hasha hasła, z którego owy hash został wygenerowany – gdyż to jest niemożliwe. Funkcja ma na celu w dowolny sposób na podstawie wejściowego hasha, stworzyć zupełnie nowe hasło.

Dla nas, zupełnie wystarczająca będzie przykładowa funkcja redukująca, która tworzy nowe hasło poprzez wzięcie 4-ech pierwszych cyfr z hasha. Funkcja taka ma oczywiste ograniczenia – będzie mogła być zastosowana tylko do łamania haseł, które:

  • składają się z 4 znaków
  • znaki hasła to tylko cyfry
  • będzie błąd, gdy hash nie będzie miał przynajmniej 4 cyfr


2. Wyliczenie wartości dla Tęczowej Tablicy

Bierzemy jakieś przykładowe hasło, dla którego pasować będzie nasza funkcja redukująca.
„1729″
Teraz liczymy hash z tego przykładowego hasła.
MD5( „1729″ ) = 25e2a30f44898b9f3e978b1786dcd85c
Do tak otrzymanego hasha, stosujemy naszą funkcję redukującą.
RED( „25e2a30f44898b9f3e978b1786dcd85c” ) = 2523

Wynik działania funkcji redukującej, używamy jako kolejne hasło.

„2523″
MD5( „2523″ ) = a6d259bfbfa2062843ef543e21d7ec8e
RED( „a6d259bfbfa2062843ef543e21d7ec8e” ) = 6259

I tak dalej…

„6259″
MD5( „6259″ ) = 99503bdd3c5a4c4671ada72d6fd81433
RED( „99503bdd3c5a4c4671ada72d6fd81433″ ) = 9950

„9950″
MD5( „9950″ ) = 09a630e07af043e4cae879dd60db1cac
RED( „09a630e07af043e4cae879dd60db1cac” ) = 0963

„0963″
MD5( „0963″ ) = d1cbdbc9cacee6c8b133c7a92a83bcca


3. Kompresja Tęczowej Tablicy

Teraz dzieje się cała magia Tęczowych Tablic. Weźmy pierwsze hasło, od którego zaczęliśmy liczenie wartości.

„1729″

Weźmy teraz ostatni wyliczony hash.

„d1cbdbc9cacee6c8b133c7a92a83bcca”

Zapiszmy ilość iteracji, które doprowadziły, od tego hasła, do tego hashu.

5

Powyższy zestaw danych stanowi pojedynczy element naszej tworzonej Tęczowej Tablicy.

1729 ; d1cbdbc9cacee6c8b133c7a92a83bcca ; 5

Cała magia się kryje w tym, że w powyższych danych, zaszyte są wszystkie informacje uzyskane w toku powyższych obliczeń. Nie są one dostępne wprost, ale tam są.


3. Wyszukiwanie w Tęczowej Tablicy

Wyobraźmy sobie, że teraz mamy do złamania jakiś hash, np:

„99503bdd3c5a4c4671ada72d6fd81433″

Nie ma go w naszej jednoelementowej Tęczowej Tablicy. Ale zróbmy coś takiego.

RED( „99503bdd3c5a4c4671ada72d6fd81433″ ) = 9950
MD5( „9950″ ) = 09a630e07af043e4cae879dd60db1cac

Tego hasha, też nie ma w naszej Tęczowej Tablicy. Więc zróbmy to ponownie.

RED( „09a630e07af043e4cae879dd60db1cac” ) = 0963
MD5( „0963″ ) = d1cbdbc9cacee6c8b133c7a92a83bcca

Trafiliśmy. Ten hash, znajduje się w naszej jednoelementowej Tęczowej Tablicy. Odnaleźliśmy więc element Tęczowej Tablicy, w którym zaszyta jest informacja o naszym hashu.

Aby sprawdzić, z jakiego hasła został wygenerowany hash, od którego rozpoczęliśmy nasze poszukiwania, robimy następującą rzecz. Po pierwsze odczytujemy hasło, od zapisane w tym elemencie Tęczowej Tablicy.

„1729″

Teraz wykonujemy na nim tyle razy hashowanie i redukcji, aż dojdziemy do poszukiwanego hashu.

„1729″
MD5( „1729″ ) = 25e2a30f44898b9f3e978b1786dcd85c
RED( „25e2a30f44898b9f3e978b1786dcd85c” ) = 2523

„2523″
MD5( „2523″ ) = a6d259bfbfa2062843ef543e21d7ec8e
RED( „a6d259bfbfa2062843ef543e21d7ec8e” ) = 6259

„6259″
MD5( „6259″ ) = 99503bdd3c5a4c4671ada72d6fd81433

No i znaleźliśmy. Teraz możemy odczytać hasło, z jakiego został wygenerowany poszukiwany hash.

„6259″


4. Zysk czasowy i objętościowy dla Tęczowych Tablic

Aby stworzyć Tęczową Tablicę, musieliśmy normalnie wykonać wszystkie obliczenia hashów – zysku tu żadnego. Zysk jest widoczny dla klienta, który korzysta z wcześniej stworzonej Tęczowej Tablicy, którą pobrał np. z Internetu.

Po pierwsze, rozmiar słownika został zmniejszony tylukrotnie względem normalnego słownika, ile wynosi ilość iteracji wykonanych dla stworzenia jednego elementu tablicy.

Jeżeli chodzi o zysk czasowy, to być może nie jest on dobrze widoczny na naszym przykładzie, gdyż nasza Tęczowa Tablica składa się tylko z jednego elementu. W ogólnym przypadku, liczba koniecznych hashowań wynosi tyle ile suma poniższych:

  • liczba hashowań, aby odnaleźć hash znajdujący w naszej Tęczowej Tablicy
  • liczba hashowań, aby odnaleźć hasło, z którego utworzono już wcześniej zlokalizowany hash

Dodatkowo, należy zauważyć, że:

  • suma powyższych nigdy nie jest większa, niż liczba iteracji przypadająca na jeden element słownika
  • gdy nasza Tablica nie pozwala na odnalezienie poszukiwanego hasła, to dowiadujemy się tego po tylu hashowaniach, ile iteracji przypada na jeden element

Pozostaje jeszcze kwestia porównań. Ich sumaryczna ilość to suma poniższych:

  • aby zlokalizować element Tablicy, w którym zaszyty jest poszukiwany hash (maksymalnie musimy wykonać: liczba_iteracji_na_element * liczba_elementów
  • aby zlokalizować hasło, z którego stworzono zlokalizowany już hash (maksymalnie to: liczba_iteracji_na_element
  • z tym, że im więcej porównań wykonamy w pierwszym kroku, tym mniej musimy wykonać w drugim


5. Podsumowanie

  • Metoda Tęczowych Tablic, to połączenie metody Słownikowej i Brute Force
  • Zysk objętościowy słownika wynosi tyle, ile mamy iteracji na jeden element tablicy
  • Ilość koniecznych obliczeń hashów wynosi dokładnie tyle, ile mamy iteracji na jeden element tablicy
  • Zysk czasowy jest więc tym większy, ile szybciej następuje wyszukanie w bazie względem wyliczenia hasha
  • Zysk czasowy rośnie więc również gdy mamy więcej element w Tablicy – lepiej porównywać, niż hashować
  • Gdyby wyszukiwanie miało taki sam koszt jak wyliczenie, to zysku brak – a nawet strata czasowa