rtables.pdf

(963 KB) Pobierz
244944066 UNPDF
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
244944066.051.png 244944066.057.png 244944066.058.png 244944066.059.png 244944066.001.png
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
15
244944066.002.png 244944066.003.png 244944066.004.png 244944066.005.png 244944066.006.png 244944066.007.png 244944066.008.png
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
244944066.009.png 244944066.010.png 244944066.011.png 244944066.012.png 244944066.013.png 244944066.014.png
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
17
244944066.015.png 244944066.016.png
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
244944066.017.png 244944066.018.png 244944066.019.png 244944066.020.png 244944066.021.png 244944066.022.png 244944066.023.png 244944066.024.png 244944066.025.png 244944066.026.png 244944066.027.png 244944066.028.png 244944066.029.png 244944066.030.png 244944066.031.png 244944066.032.png 244944066.033.png 244944066.034.png 244944066.035.png 244944066.036.png 244944066.037.png 244944066.038.png 244944066.039.png 244944066.040.png 244944066.041.png 244944066.042.png 244944066.043.png 244944066.044.png 244944066.045.png 244944066.046.png 244944066.047.png 244944066.048.png 244944066.049.png 244944066.050.png 244944066.052.png 244944066.053.png 244944066.054.png 244944066.055.png 244944066.056.png
 
Zgłoś jeśli naruszono regulamin