rtables.pdf

ATAK

SEBASTIAN CZARNOTA

Tęczowe tablice

– przyśpiesz

atak brute-force

Stopień trudności

Tęczowe tablice pozwalają przyspieszyć ataki brute-force,

eliminując potrzebę wykonywania w każdym kolejnym ataku tych

samych obliczeń poprzez zapamiętani części kluczowych danych.

Tablice znalezione w Internecie bywają jednak niekompletne lub

płatne, dlatego zobaczmy jak zrobić je samemu!

haseł w postaci jawnej nie jest

bezpieczne. Przyklejanie haseł do

monitora, czy wkładanie pod klawiaturę jest

zmorą osób odpowiedzialnych w firmach za

bezpieczeństwo. Takie eksponowanie haseł jest

wręcz proszeniem się o kłopoty.

W systemach komputerowych jest

podobnie. Przechowywanie haseł w postaci

jawnej jest niebezpieczne, zwłaszcza gdy

hasła te przechowuje system operacyjny, który

zajmuje się przydzielaniem praw użytkownikom.

Najprostszym sposobem rozwiązania tego

problemu wydaje się zaszyfrowanie hasła

za pomocą szyfru symetrycznego. Jednak

pojawia się problem: kryptosystem symetryczny

do szyfrowania wymaga... hasła, które

również trzeba byłoby w sposób bezpieczny

przechować w systemie operacyjnym. Nie

rozwiązuje to jak widać problemu, ale go

pogłębia.

(zwany również wiadomością) i jest on

deterministyczny, tj. jeden ciąg wejściowy

zawsze da taki sam ciąg wynikowy;

• ciąg wynikowy (skrót) wydaje się być

ciągiem losowym – zależność między

ciągiem wejściowym (wiadomością)

i skrótem jest tak skomplikowana, że

nie jesteśmy w stanie odtworzyć ciągu

wejściowego na podstawie ciągu

wynikowego – mówi się, że taka funkcja jest

jednokierunkowa;

• skrót ma ustaloną długość w bitach (MD5

– 128 bitów, SHA-0 – 160 bitów, SHA-1

– warianty 224, 256, 384, 512 bitowe)

(Rysunek 1).

Warto w tym miejscu wtrącić dygresję na temat

nazwy funkcja skrótu (ang. message digest ),

ponieważ, jeśli skracamy na przykład hasło

tajne_haslo to jego skrót MD5 wynosi 1b955

38f3035f4cba2189716fd96173c , a więc jest

dłuższy. Nazwa ma swoje uzasadnienie w tym,

że funkcje skrótu projektowane były dla tworzenia

krótkiego odpowiednika dużego dokumentu.

Skrót przydatny jest w procesie cyfrowego

podpisywania dokumentu, ponieważ działanie

algorytmów podpisywania jest bardzo powolne,

a czas rośnie wraz ze zwiększeniem objętości

dokumentu, dlatego podpisuje się jedynie

skrót tego dokumentu. Do przechowywania

haseł wykorzystano istniejące już rozwiązanie

zwane funkcją skrótu, a nazwa już pozostała.

Z ARTYKUŁU

DOWIESZ SIĘ

do czego służą funkcje skrótu,

jak wykorzystać tęczowe

tablice,

jak zaprojektować skuteczną

tęczową tablicę.

Funkcje skrótu

Dlatego postanowiono podejść do problemu

w inny sposób. Użyto funkcji skrótu. Funkcja

skrótu (funkcja haszująca, ang. hash function )

przyjmuje jako parametr dowolny ciąg binarny,

a jako wynik swojego działania zwraca inny

ciąg binarny o następujących cechach:

CO POWINIENEŚ

WIEDZIEĆ

mieć ogólne pojęcie o

przechowywaniu i przesyłaniu

haseł.

• ciąg wynikowy (nazywany skrótem)

jest zależny od ciągu wejściowego

14 HAKIN9

12/2009

K ażdy doskonale wie, że przechowywanie

TĘCZOWE TABLICE

Czasem stosuje się określenie funkcja

haszujące. Osoby zajmujące się tym

zagadnieniem nie potrafią dojść do

porozumienia, która nazwa jest poprawna,

o czym można przeczytać w Wikipedii, w

dyskusji do tematu Funkcje skrótu . Polskie

normy definiują jednak pojęcie funkcji

skrótu , dlatego będę się tym terminem

posługiwał w dalszej części artykułu.

Cechą funkcji skrótu jest

występowanie kolizji – czyli sytuacji, gdy

skróty dwóch różnych wiadomości są

identyczne. Cecha ta jest bezpośrednim

następstwem ustalenia długości skrótu

– ponieważ skoro można skracać

(poddawać działaniu funkcji skrótu)

wiadomość o dowolnym rozmiarze, do

ciągu o z góry określonej długości, to

muszą istnieć co najmniej dwie takie

wiadomości, które dają identyczny skrót

(działa tutaj twierdzenie zwane Zasadą

szufladkową Dirichleta ) (Rysunek 2).

W kryptologii występowanie kolizji

jest cechą niepożądaną, ponieważ

statystycznie znalezienie dowolnej

wiadomości, która daje określony

skrót jest bardziej prawdopodobne, niż

znalezienie dokładnie tej wiadomości,

której użyto do wygenerowania skrótu

(dzieje się tak dlatego, gdyż istnieje więcej

niż jeden ciąg, dający ten sam skrót).

Oznacza to, że aby zalogować się do

systemu, który przechowuje wyłącznie

skróty haseł użytkowników, można użyć

nie tylko hasła, które użytkownik sobie

wybrał, ale również wszystkich innych

haseł, których skrót jest identyczny. Atak

kryptoanalityczny wykorzystujący tą cechę

funkcji skrótu nazywa się poszukiwaniem

przeciwobrazu (ang. preimage attack ).

Kolizje w funkcjach skrótu

będą zawsze występowały.

Prostym sposobem na obniżenie

prawdopodobieństwa ich wystąpienia

jest wydłużenie skrótu. Zwiększa to

ilość różnych skrótów, zmniejszając

szansę na wystąpienie kolizji. Aktualnie

następuje zmiana standardowej

długości skrótu i zastępowanie starych,

niebezpiecznych funkcji skrótu nowymi.

Właśnie trwa konkurs na nowy standard

funkcji skrótu SHA-3 organizowany

przez amerykańską agencję federalną

NIST (ang. National Institute of

Standards and Technology ).

Wykorzystanie funkcji skrótu

Spójrzmy teraz jak funkcje skrótu

rozwiązują problem przechowywania

hasła. Gdy użytkownik loguje się do

systemu jest proszony o podanie

swojego hasła. System operacyjny

interpretuje hasło użytkownika jako ciąg

binarny i poddaje go działaniu funkcji

skrótu (np. MD5). Teraz to ten skrót

jest porównywany z przechowywanym

skrótem hasła w systemie. Jeśli oba

skróty są takie same, następuje

zalogowanie do systemu, jeśli nie, system

odmówi użytkownikowi dostępu.

Znając już zjawisko kolizji, wiemy,

że poprawne zalogowanie do systemu

może wystąpić również wtedy, gdy

użytkownik poda dowolne inne hasło,

o takim samym skrócie. Wydaje się to

niebezpieczne, ale pamiętajmy, że funkcja

skrótu jest funkcją jednokierunkową i

znalezienie hasła na podstawie skrótu

jest obliczeniowo trudne. Trudne, ale nie

niemożliwe.

Zanim przejdziemy do omówienia

ataków na funkcje skrótu, zauważmy

jeszcze kilka interesujących faktów.

Obliczenie skrótu wiadomości powinno

być szybkie i wydajne, natomiast

proces odwrotny musi być trudny

obliczeniowo. Kryptologia określa procesy

trudne obliczeniowo jako takie, których

rozwiązanie, przy użyciu najlepszych

znanych algorytmów i najlepszych

komputerów na świecie, biorąc pod

uwagę wzrost ich wydajności w czasie,

zajmie tak niewyobrażalnie długi czas, że

atak jest niepraktyczny. Niczym dziwnym

jest, że złamanie pewnych algorytmów

kryptograficznych szacuje się na miliony lat.

Trzeba jednak pamiętać, że przy

obecnym postępie technicznym dostępna

moc obliczeniowa ciągle wzrasta. Jak

również stale ulepsza się i wynajduje

nowe algorytmy oraz następuje ciągły

rozwój matematyki wyższej, która ma

niebanalny wpływ na wydajność ataków

szyfry i funkcje skrótu. Dlatego tak ważne

jest ich ciągłe udoskonalanie: zarówno

mechanizmów, według których działają,

jak i długości skrótu. Jest to o tyle ważne,

że nawet najlepiej zaprojektowana funkcja

skrótu zostanie szybko złamana, gdy jej

skrót będzie zbyt krótki.

Klasyczne ataki

na skróty haseł

W dalszej części artykułu będziemy

rozpatrywać atak polegający na

odzyskaniu hasła, z jego skrótu. Skróty

haseł są używane w czasie logowania

się zdalnie, w przypadku obecności

specjalnego klienta. Użytkownik wtedy

podaje swoje hasło w aplikacji klienckiej,

która skraca to hasło i w takiej postaci

przesyła do serwera (to jest znaczne

uproszczenie, gdyż napastnik mógłby

zrezygnować z użycia programu klienta,

a tylko przechwycić i przesłać sam

skrót – w rzeczywistości stosuje się

bardziej zaawansowane protokoły, które

uniemożliwiają takie nadużycie).

Hasła systemów operacyjnych

również są przechowywane w postaci

��

Rysunek 1. Idea działania funkcji skrótu

12/2009

HAKIN9

ATAK

skrótów. Jednak zdobycie pliku, który

przechowuje skróty, często wiąże się

z wtargnięciem do systemu ofiary,

więc odzyskiwanie hasła już nie jest

potrzebne. Wyjątkiem jest sytuacja, gdy

administrator systemu popełni błąd

(lub zostanie do niego sprowokowany)

i uda się bez włamywania na konto

administratora uzyskać ten plik. Metody

dalej opisane mogę wtedy zostać

wykorzystane do eskalacji uprawnień

w systemie i to w bardzo bezpieczny

sposób, bo offline.

Dwa najprostsze pomysły ataku

na funkcje skrótu nasuwają się chyba

każdemu:

rzeczywistości ich pełne przeprowadzenie

wymaga potężnej mocy obliczeniowej w

pierwszym przypadku i niewyobrażalnej

przestrzeni dyskowej w drugim. Warto

w tym miejscu podać pewne liczby,

które uzmysłowią skalę problemu. 128-

bitowa funkcja skrótu (to znaczy taka,

której skrót ma 128-bitów, wiadomość

może być dowolnej długości) posiada

2^128 różnych skrótów, daje to 6*10^23

petabajtów danych potrzebnych na

przechowanie tych wszystkich skrótów.

Jest to mniej więcej tyle petabajtów

danych, ile wynosi szacowana liczba

gwiazd we wszechświecie. A to tylko

skróty! Drugie tyle zajmą hasła im

odpowiadające, a czas potrzebny, do

wygenerowania takiej tablicy będzie

liczony w milionach lat.

Należy przy okazji sprostować, że są

to wyliczenia teoretyczne, zakładające,

że funkcja skrótu jest wyidealizowana

w taki sposób, że nie da się jej budowy

wewnętrznej użyć do znalezienia hasła,

oraz że wykorzystuje wszystkie dostępne

skróty. Rzeczywistość jest zupełnie

inna. To właśnie analiza budowy funkcji

skrótu (i algorytmów kryptograficznych

w ogólności) daje najlepsze

kryptoanalityczne efekty. Jeszcze lepsze

efekty uzyskuje się, gdy znaleziony

zostanie błąd w implementacji algorytmu

w konkretnej realizacji programowej, ale

na to nie należy liczyć, gdyż błąd może

być naprawiony.

Kolejnym faktem jest, że nie musimy

budować tablicy, dla wszystkich

możliwych skrótów, ponieważ interesują

nas jedynie hasła. Ilość wszystkich haseł

do 10 znaków włącznie jest znacznie

mniejsza, niż liczba wszystkich skrótów,

dla funkcji 128-bitowej. Dokładne

wyliczenia zależą od przyjętego zestawu

znaków.

Tęczowe tablice

Tęczowe tablice to pomost między

przytoczonymi przeze mnie dwoma

metodami ataku. Łączy w sobie zaletę

przechowywania wyników, umożliwiającą

wygenerowanie tablicy raz i korzystanie

z niej w każdym następnym ataku oraz

zmniejsza objętość tablic. Następuje

bardziej racjonalne wykorzystanie mocy

obliczeniowej i pamięci.

Wyobraźmy sobie listę ciągów

binarnych. Pierwszym elementem tego

ciągu jest pewne hasło ze słownika

haseł. Drugim elementem jest skrót

tego hasła. Kolejnymi elementami

są: pewne hasło, wygenerowane na

podstawie poprzedzającego skrótu

i skrót tego hasła. Dalej podobnie,

hasło wygenerowane na podstawie

poprzedzającego skrótu i jego skrót,

itd. Należy sobie uzmysłowić, że hasła

generowane na podstawie skrótów, to

nie są hasła, które po skróceniu dają

ten skrót, są to po prostu jakieś hasła

zależne od skrótu (Rysunek 3).

Generowaniem hasła ze skrótu

zajmuje się tak zwana funkcja

redukująca. Może ona mieć dowolną

postać, ale warto, by zapewnić, aby

była w stanie wygenerować możliwie

najwięcej różnych haseł. Najprostszą

• sprawdzanie wszystkich możliwych

haseł – skracanie ich i testowanie,

czy dają pożądany skrót;

• zbudowanie ogromnej tablicy

wszystkich haseł i odpowiadających

im skrótów, posortowanie według

skrótów i wyszukiwanie w tablicy.

Są to metody pewne, czyli gdyby

udało się je przeprowadzić, istnieje

stuprocentowa szansa na poprawne

znalezienie hasła. Jednak w

��

Rysunek 2. Kolizja – dwie wiadomości mają jednakowy skrót

�

��

Rysunek 3. Łańcuch – podstawowa jednostka przechowywania danych w tęczowej tablicy. H – funkcja skrótu, R – funkcja

redukująca

16 HAKIN9 12/2009

TĘCZOWE TABLICE

funkcją redukującą może być funkcja,

która będzie binarną reprezentację

skrótu zamieniać na znaki traktując je

jak kod ASCII.

Zapisujemy sobie początkowe

hasło takiego łańcucha i ostatni skrót.

Pośrednie hasła i skróty nie będą

zapisywane, bo jak się za chwilę okaże,

nie są potrzebne. Przydatna będzie

jedynie informacja o liczbie par w całym

łańcuchu. Taka para: hasło i odległy skrót

jest bardzo interesująca.

Wyobraźmy sobie, że chcemy

znaleźć hasło odpowiadające skrótowi.

Najpierw musimy się upewnić, że

szukane hasło odpowiadające skrótowi

znajduje się w naszym łańcuchu.

Ponieważ nie zapisaliśmy żadnych

wartości pośrednich, będziemy opierać

się na zapamiętanym, odległym skrócie.

Postępujemy zgodnie z algorytmem jak

na Rysunku 4.

5. otrzymane hasło skracamy

otrzymując inny skrót, ten skrót

zapamiętujemy w zmiennej H,

6. przechodzimy do kroku 2,

7. gdy H jest równy końcowemu skrótowi

łańcucha – łańcuch posiada szukane

hasło,

8. gdy ilość skracań i redukcji

przekroczyła długość łańcucha

– łańcuch nie posiada hasła.

1. H – przyjmujemy za H szukany skrót,

2. sprawdzamy, czy H jest równy

końcowemu skrótowi łańcucha,

3. jeśli nie, sprawdzamy, czy ilość

skracań i redukcji jest większa niż

długość łańcucha,

4. jeśli nie, to poddajemy nasz skrót

H działaniu funkcji redukującej,

otrzymujemy w ten sposób hasło.

Jeśli w kroku drugim okaże się, że któreś

H jest równe końcowemu skrótowi, to

mamy pewność, że w ciągu znajduje się

hasło do naszego skrótu. Jeśli natomiast

wykonamy krok 3 więcej razy niż

wynosiła liczba par w całym łańcuchu, to

zaprzestajemy poszukiwań, bo łańcuch

hasła nie zawiera (Rysunek 5).

Gdy już wiemy, że łańcuch

zawiera hasło, przystępujemy do jego

odzyskiwania. W tym celu bierzemy z

pary zapamiętanej dla ciągu hasło i

poddajemy go cyklicznym skracaniom

i redukcjom. Kiedy natrafimy na

poszukiwany skrót, to poprzednie hasło

jest hasłem, które szukaliśmy!

Pewnie niezrozumiałe jest teraz,

dlaczego od razu nie można było

cyklicznie skracać i redukować. Już

śpieszę z wyjaśnieniem. Łańcuchów

jest wiele, nawet bardzo wiele. Im

więcej tym lepiej, gdyż mamy większe

prawdopodobieństwo, że szukane hasło

��

Rysunek 4. Schemat sprawdzania, czy łańcuch zawiera skrót. Należy pamiętać,

że redukowanie i skracanie wykonujemy tylko tyle razy, ile wynosi długość łańcucha

(zapamiętana w czasie tworzenia)

R E K L A M A

12/2009

HAKIN9

ATAK

jest w naszym zbiorze. Cała siła tęczowych

tablic zawiera się właśnie w ilości

łańcuchów i ich długości (Rysunek 6).

Długość łańcucha to nic innego jak

ilość cyklicznych skracań i redukcji od

pierwszego hasła do ostatniego skrótu.

Im dłuższe łańcuchy, tym mniej miejsca

zajmą tablice przy tej samej liczbie

haseł. Jednocześnie im dłuższe tablice,

tym więcej mocy obliczeniowej będzie

potrzebne do wyszukiwania w tablicy.

Należy więc znaleźć złoty środek.

hasło, które już w innym łańcuchu zostało

zawarte. Ponieważ funkcja redukująca

jest jednakowa, wszystkie następujące

później hasła i skróty powtórzyłyby się!

Byłoby to ogromne marnotrawstwo

miejsca na dysku i mnóstwo zbędnych

obliczeń. Gdyby kolizje występowały

często, sporo danych byłaby zdublowana

i tylko niepotrzebnie spowalniałaby użycie

tęczowych tablic (Rysunek 7).

To ciekawe, że kolizje, które są

zjawiskiem niepożądanym w funkcjach

skrótu, utrudniają ataki metodą tęczowych

tablic. Okazuje się, że funkcja skrótu

o licznych kolizjach sparaliżowałaby

działania tęczowej tablicy! Na domiar

złego, gdyby w tym samym ciągu

jakieś hasło wystąpiło dwa razy, to

otrzymalibyśmy zapętlenie – w równych

odstępach pojawiałyby się sekwencje

tych samych skrótów i haseł (Rysunek 8).

Czy więc jesteśmy skazani na tak

niedoskonałe narzędzie? Okazuje się,

że poradzono sobie w bardzo sprytny

sposób z tymi problemami, poprzez

wprowadzenie wielu różnych funkcji

redukujących. Różnych, czyli takich które

dla takiego samego skrótu zwracają różne

hasła. Przychodzi nam zapewne na myśl

kilka sposobów ulokowania tych różnych

funkcji redukujących. Trzy główne z nich to:

Kolizje i pętle

w tęczowych tablicach

Wydaje się, że nasze tęczowe tablice

są już gotowe do pracy. Zastanówmy

się jednak, co by się stało, gdybyśmy

obliczając pewien łańcuch natrafili na

• użycie za każdym razem innej funkcji

– bardzo nieefektywny sposób, gdyż

potrzeba przechowywania ogromnej

ilość funkcji redukujących przekracza

wielokrotnie rozmiar samej tęczowej

tablicy;

�

��

�

��

�

��

�

��

�

��

�

��

�

��

�

��

Rysunek 5. Przykład wyszukiwania hasła w jednym łańcuchu. W tablicy wykonujemy te porównania z wieloma skrótami kończącymi

łańcuchy

�

��

�

��

�

��

�

��

�

��

�

��

�

��

�

��

�

��

Rysunek 6. Tęczowa tablica – w poziomie widzimy łańcuchy, a w pionie kolejno od lewej każda para stanowi warstwę

18 HAKIN9 12/2009

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: