Strona główna

Tęczowe tablice (ang. rainbow tables) - jest to baza skrótów wykorzystywana w łamaniu haseł szyfrowanych jednokierunkową funkcją skrótu. Pozwala na zaoszczędzenie mocy obliczeniowej koniecznej do złamania hasła metodą brute force. Metoda ta została wymyślona przez Philippe'a Oechslina z Politechniki w Lozannie.

 

 

W sieci można znaleźć wiele informacji na temat tego, czym są i jak działają tęczowe tablice. Jednak większość z nich opisuje cały ten proces tak skomplikowanym językiem, że dla laika wydaję się on dość niezrozumiałym. W tym artykule zostanie omówionych kilka istotnych szczegółów, które przybliżą istotę działania rainbow tables i ułatwią ich zrozumienie.

Na początku warto wspomnieć o funkcji hashującej. Kompresuje ona bity hasła do wartości o określonej długości (ang. hash value). Czyni to w sposób, który sprawia niezwykle trudnym pojawienie się wiadomości, która dałaby w rezultacie tę samą hash-wartość. Z hasła zapisanego jawnym tekstem tworzy hash w taki sposób, aby nie można było powiedzieć, z jakiego hasła powstał.


Do znalezienia hasła dla danego hasha można wykorzystać dwie proste metody: 

• Z przestrzeni znaków dla wszystkich możliwości haseł można tworzyć odpowiadające im hashe. Podczas generowanie każdego kolejnego hasha możn sprawdzać czy szukany hash odpowiada hashowi, który właśnie został wygenerowany. Jeśli hashe są takie same, należy zatrzymać generowanie i sprawdzać czy hasło pasuje, jeśli nie - kontynuować generowanie dalej.
   
• Z przestrzeni znaków dla wszystkich możliwości haseł można tworzyć odpowiadające im hashe, w sposób uporządkowany zapisywać je do tabeli, a po wygenerowaniu kompletnej tablicy wyszukiwać w niej interesujący nas hash. Dzięki zapisaniu tablic na dysku twardym można je w przyszłości wykorzystywać do szukania hashy, bez konieczności ponownego ich generowania.

Obie metody mają jednak duże wady. Każdorazowe generowanie hashy zabiera bardzo dużo czasu, a przetrzymywanie każdego hasha zajmuje ogromne przestrzenie dyskowe. Tęczowe tablice są swoistym kompromisem pomiędzy wcześniejszym generowanie tablic, a niskim użyciem pamięci masowej.

Nazwa Rainbow Tables wzięła się od kolumn z użytymi różnymi funkcjami redukującymi. Jeśli każda użyta funkcja redukująca miałaby w tabeli inny kolor, a na górze tabeli znajdowałoby się hasło w postaci plaintekstu i hashe w środku tablicy, to tablica wyglądała by jak tęcza.

Kluczem do zrozumienia tęczowych tablic jest zrozumienie, czym tak naprawdę jest funkcja redukująca. Funkcja hashująca przyporządkowuje dla danego hasła jego odpowiednik hash, zaś funkcja redukująca dla danego hasha przyporządkowuje hasło. Funkcja z hasha tworzy hasło, ale oczywiście nie jest to hasło, z którego dany hash powstał, jest on tak naprawdę dowolnym ciągiem znaków ,który powstał w wyniku konkretnego działania.

Na przykład jeśli przestrzeń znaków hasła to [0123456789], a hasło nie jest dłuższe niż sześć znaków i jest zaszyfrowane przy pomocy algorytmu md5 (sześcio-znakowe hasło numeryczne) to dla hasła "493823" hash będzie miał wartość "222f00dc4b7f9131c89cff641d1a8c50". W takim przypadku funkcja redukująca może ograniczyć się do pobrania sześciu pierwszych cyfr z hasha 222f00dc4b7f9131c89cff641d1a8c50, co daje nowe hasło o w postaci 222004. I oto z hasha otrzymuje się kolejne hasło, które posłuży do wygenerowania kolejnego hasha itd.

 

  

Hashowanie jak i redukcja są funkcjami jednokierunkowymi. Łańcuchy znaków tworzące tęczowe tablice są łańcuchami jednokierunkowych funkcji redukujących zaczynających się od konkretnego hasła i kończących się na konkretnym hashu. Łańcuch zaczyna się od hasła w plaintekscie, które później poddawane jest funkcji hashującej, której to wynik z kolei poddawany jest funkcji redukującej, a następnie znowu funkcji hashującej i redukującej itd. Łańcuch zawiera tylko początkowy plaintekst i końcowy hash. Dlatego też miliony hashy mogą być zastąpione jedynie rekordem posiadających jedno początkowe hasło i jeden końcowy hash.


Po wygenerowaniu wielu ciągów tablica ma postać podobną do tej:

Łańcuchy znaków są już wygenerowane, przyszedł więc czas, aby ich użyć. Mamy hash hasła, nie znamy jego plaintekstowej formy i chcemy sprawdzić czy znajduje się on w którymś z wygenerowanych łańcuchów.


Algorytm wyszukiwania wygląda następująco: 

 

Przy generowaniu rainbow tables można napotkać na kilka problemów. Po pierwsze, nigdy ma pewności, że wygenerowana tablica ma już wszystkie pożądane hashe. Oczywiście nie można być pewnym, iż wszystkie hasła w pożądanej przestrzeni znaków zostaną zahashowane, ale szanse rosną przy odpowiedniej ilości łańcuchów.

Kolejnym niepożądanym zjawiskiem jest zjawisko kolizji. Polega ono na wystąpieniu sytuacji, kiedy to z wielu różnych haseł otrzymuje się taki sam hash. Mogą też wystąpić zapętlenia w przypadku, gdy hash został zredukowany do hasła, które już wystąpiło w danym łańcuchu wcześniej. Został on jednak znacznie zminimalizowany dzięki temu, iż na całej drodze w łańcuchu za każdym razem użyta jest inna funkcja redukująca.

Tęczowe tablice pozwalają na złamanie większości popularnych funkcji skrótu, w tym MD5, SHA-1, NTLM czy Cisco Pix.

Obrona

Dobrym sposobem na zabezpieczenie sie przed tym sposobem ataku jest stosowanie tzw. soli (ang. salt), czyli losowo generowanej wartości dodawanej jako argument funkcji skrótu i zapisywanej obok wartości skrótu. Sprawia to, że dla każdej soli funkcja skrótu jest inna. Żeby złamać taki skrót osoba próbująca złamać musiałaby posiadać tęczową tablicę dla każdej możliwej soli, co jest niepraktyczne.

Większość dystrybucji GNU/Linuksa i systemów BSD wykorzystuje sól do zapisywania haseł użytkowników, funkcjonalność ta jest oferowana przez pakiet shadow. Z kolei większość aplikacji internetowych w PHP wykorzystuje do kodowania haseł użytkowników zwykłe MD5, co ułatwia złamanie hasła.

Opracowanie na podstawie http://kestas.kuliukas.com/RainbowTables/

Do góry