Ataki wykorzystujące tęczowe tablice stały się w ciągu ostatnich lat jedną z najpopularniejszych metod odwracania skrótów kryptograficznych. Artykuł przedstawia ciekawą alternatywę, polegającą na kompresji tablic obliczeń wstępnych. Rozwiązanie to ma, pod kilkoma względami, lepsze właściwości niż tęczowe tablice.

Źródło: hakin9.org
Autor: Wojciech Terlikowski

Funkcja skrótu (hash function) w kryptografii to funkcja, która pozwala na przekształcenie bloku danych, tzw. wiadomości, w jej skrót kryptograficzny. Skrót zwany podpisem, odciskiem palca (fingerprint) lub sumą kontrolną (checksum) jest obliczany w taki sposób, że niemożliwe jest jego odwrócenie. Wiadomości nazywane będą niekiedy hasłami, ponieważ wiele systemów informatycznych przechowuje hasła właśnie w postaci odcisków palca. Choć nie są znane analityczne metody ataku na współczesne funkcje skrótu to zawsze pozostaje możliwość ataku brutalnego, wyczerpującego (exhaustion search, brute force attack). Polega on na generowaniu odcisków palca kolejno dla wszystkich możliwych wiadomości i porównywaniu ich z wartością poszukiwaną. Taki atak, jak nie trudno się domyślić, jest bardzo kosztowny obliczeniowo i faktycznie może być wyczerpujący. Już dla wiadomości składającej się z 7 znaków alfanumerycznych będzie potrzebował (26+26+10)7=3.521.614.6 06.208 – ponad 3,5 miliarda obliczeń funkcji skrótu i porównań. Jest to koszt jaki należałoby ponieść, by złamać siedmioliterowe hasło zabezpieczone przez funkcję skrótu. Dla współczesnych komputerów oznacza to setki tysięcy godzin obliczeń. Jest to zdecydowanie zbyt dużo czasu by stosować tę metodę powszechnie. Dlatego zostało opracowane wiele modyfikacji ataku wyczerpującego.
Niektóre z nich, na przykład ataki słownikowe, próbują ograniczyć zbiór wiadomości. Inne pozwalają na wielokrotne wykorzystanie raz obliczonych wartości funkcji skrótu. Do tych drugich zaliczyć można zarówno metodę tęczowych tablic, jak i kompresji tablic obliczeń wstępnych.

Właściwości funkcji skrótu

Funkcja skrótu, aby mogła znaleźć zastosowanie w kryptografii, a tym samym była odporna na ataki analityczne, musi posiadać następujące cechy:

• jednokierunkowość – zapewnia, że przekształcenie odwrotne do funkcji nie istnieje. Jeśli h =H (m) to nie istnieje funkcja F taka, że F (h)=m,
• • odporność na kolizje – dla dowolnejwiadomości m1 bardzo trudno jest znaleźć wiadomość m2 taka, że H(m1)=H(m2),
• • odległości z przestrzeni wiadomości nie są zachowane w przestrzeni skrótów – czyli modyfikacja wiadomości nawet o jeden bit powoduje znaczącą zmianę w wartości skrótu. Ponadto długość skrótu jest stała bez względu na długość wiadomości.

Współcześnie stosuje się wiele algorytmów obliczania odcisków palca. Do najczyściej używanych należą MD-5, SHA-1 i SHA256.

Należy pamiętać, że nie można mówić o niezawodnej funkcji skrótu. Algorytm MD-5, wprowadzony jako bezpieczny następca MD-4 w 1991 roku. Obecnie nie jest już zalecany do stosowania, gdyż uznano go za zbyt podatny na atak wykorzystujący paradoks dnia urodzin (birthday attack). Moc obliczeniowa komputerów i rozmiary dostępnej pamięci rosną z roku na rok. Sprawia to, że kolejne funkcje skrótu, podobnie jak i algorytmy szyfrowania, są zastępowane, nowszymi, trudniejszymi do złamania.

Tęczowe tablice

Ogromny koszt ataku wyczerpującego sprawia, że jest on niemożliwy do przeprowadzenia nawet na mocnym komputerze. W takiej sytuacji z pomocą przyjść mogą obliczenia rozproszone. Jeśli wspomniane wcześniej setki tysięcy godzin obliczeń, podzieli się między miliony komputerów w Internecto czas odwracania pojedynczego odcisku palca może skrócić się do godzin, a nawet sekund. Obliczone w ten sposób skróty można zapisać i je, wykorzystać przy następnym ataku, ale przestrzeń dyskowa wymagana do takiej operacji (przy założeniu jak wcześniej 3,5 miliarda 7 literowych haseł i 128 bitowych skrótów) wynosi 627*(7+128/ 8)=80.997.135.942.784, czyli ponad 70 terabajtów danych. Przechowywanie tak wielkiej tablicy par wiadomość – skrót choć jest możliwe we współczesnych centrach obliczeniowych to wydaje się być niepraktyczne.
Metoda tęczowych tablic pozwala zaoszczędzić przestrzeń dyskową przy zachowaniu stosunkowo niedługiego czasu na odtworzenie pojedynczej wiadomości ze skrótu. W 2003 roku zaproponował ją Philippe Oechslin na międzynarodowej konferencji kryptograficznej CRYPTO w Santa Barbara. Metoda ta wykorzystuje, ponad dwadzieścia lat starszy, pomysł łańcuchów Martina Hellmana. Wprowadza on pojęcie tzw. funkcji redukcyjnych (reduction function). Są to transformacje, pozwalające przekształcić wartość funkcji skrótu w obiekt w przestrzeni wiadomości. Oczywiście nie jest to funkcja odwrotna do funkcji skrótu, bo taka nie istnieje, pozwala ona tylko zamienić skrót w wiadomość potencjalnie reprezentowaną przez inny skrót. Metoda tęczowych tablic składa się z dwóch faz.
Obliczenia wstępne:

• Dla wybranych losowo wiadomości obliczane są skróty, tak samo jak przy ataku wyczerpującym.
• Każdy ze skrótów za pomocą funkcji redukcyjnej przekształcany jest do przestrzeni wiadomości.
• Z otrzymanej w ten sposób wiadomości ponownie generowany jest skrót. Kroki te są powtarzane dopóki łańcuch nie osiągnie założonej długości.
• Z każdego z obliczonych łańcuchów zapamiętywany jest tylko początek i koniec – wiadomość i końcowy skrót.

Odwracanie skrótu:

• Obliczone wcześniej łańcuchy tęczowe tablice ładowane są do pamięci.
• Jeśli pośród zapamiętanych wartości nie ma poszukiwanego skrótu generowana jest z niego wiadomość za pomocą funkcji redukcyjnej, a następnie skrót wiadomości.
• Powyższy krok powtarza się, do momentu aż kolejny wygenerowany skrót nie pokryje się z jednym z zapamiętanych lub wyczerpana zostanie założona długość łańcuchów. Druga sytuacja oznacza chybienie w tęczową tablicę – brak wiadomości i koniec obliczeń.
• Jeśli udało się odnaleźć skrót, początkowa wiadomość z łańcucha, w którym się znajdował zostaje przekształcana kolejno za pomocą funkcji skrótu i redukcyjnej, aż uzyska się odwracany odcisk palca. Wiadomość, z której został wygenerowany, jest tą poszukiwaną

Metoda jest prosta i skutecznie pozwala osiągnąć założony cel. Osiągnięty jest kompromis między rozmiarem pamięci potrzebnym do przechowania obliczonych skrótów, czasem potrzebnym do odwrócenia odcisku. Czas ataku zależy od liczby i długości łańcuchów oraz zastosowanych funkcji redukcyjnych. Podczas testu przeprowadzonego przez autora metody odwrócenie skrótu trwa około 20 000 razy krócej niż w ataku brutalnym, zaś ilość pamięci i przestrzeni dyskowej jest niewielka – 6 600 razy mniejsza w porównaniu z pełną tablicą skrótów. Przy generowaniu tęczowych tablic pojawia się problem, utrudniający odwracanie odcisków palca. Chodzi o kolizję, czyli sytuację gdy różne wiadomości dają taki sam skrót lub różne skróty redukują się do takiej samej wiadomości. Może to spowodować sytuację, w której kilka łańcuchów będzie się częściowo pokrywać. Takie zduplikowane ciągi stają się bezużyteczne z punktu widzenia odwracania skrótów. Kiedy kolizja wystąpi w tym samym łańcuchu następuje zapętlenie. W takim wypadku tylko niewielki podciąg łańcucha jest użyteczny, a pozostałe elementy stanowią powtórzenia. Metoda tęczowych tablic rozwiązuje takie problemy przez zastosowanie różnych funkcji redukcyjnych na każdym kroku obliczania łańcucha. Na Rysunku 1 zostało to przedstawione jako R1, R2, … . Dzięki takiemu rozwiązaniu ryzyko kolizji zostało znacząco zmniejszone. Nawet jeśli w kilku łańcuchach pojawi się ten sam skrót, to w wyniku zastosowania różnych funkcji redukcyjnych nie doprowadzi on do duplikacji ciągów. Niebezpieczne są tylko kolizje występujące w kilku łańcuchach na tej samej pozycji.
Atak wykorzystujący tęczowe tablice wymaga pełnego obliczenia jednego łańcucha. Jest to kilkaset tysięcy lub kilka milionów obliczeń funkcji skrótu i funkcji redukcyjnej. Wielkość ta zależy od założonej długości łańcucha. Im jest on dłuższy tym więcej czasu potrzeba na odwrócenie odcisku palca, ale mniej pamięci na przechowywanie i używanie tablic. Warto przy tym zauważyć, że podczas ataku konieczne jest porównanie odwracanego skrótu z zapisanymi wartościami aby wybrać odpowiedni łańcuch. Posortowanie tablicy według wartości odcisków palców pozwala znacząco skrócić czas tej operacji, tym niemniej stanowi to dodatkowy narzut. Same obliczenia wstępne ze względu na konieczność obliczania funkcji redukcyjnych są znacznie dłuższe od ataku wyczerpującego. Dlatego też obliczanie własnych tęczowych tablic dla odwrócenia pojedynczych skrótów jest nieopłacalne. Programy stosujące tę metodę takie jak Ophrack czy RainbowCrack wykorzystują gotowe, obliczone wcześniej wartości pobrane z Internetu lub zakupione na płytach DVD.

Tabela 1. Kodowanie ośmiobitowych wiadomości w sposób wykorzystywany w algorytmie kompresji tablic obliczeń wstępnych

Rysunek 1. Zasada działania tęczowych tablic. Różne funkcje redukcyjne zostały zaznaczone różnymi kolorami. Utworzonej w ten sposób tęczy metoda zawdzięcza swoją nazwę

Tabela 2. Porównanie obu opisywanych metod ataku pochądze z materiałów Michała Trojnary

Rysunek 2. Program Opcrack uruchomiony z płyty LiveCD łamie hasła systemu Windows

Kompresja tablic obliczeń wstępnych

W roku 2007 Michał Trojnara doktorant na Wydziale Elektroniki i Technik Informacyjnych Politechniki Warszawskiej zaproponował, alternatywną wobec tęczowych tablic, metodę ataku na skróty kryptograficzne. Dzięki podzieleniu wyników obliczeń wstępnych na nieduże pliki i ich kompresji pozwala ona zaoszczędzić przestrzeń dyskową oraz ograniczyć czas konieczny do odwrócenia skrótu. Metoda podobnie jak w przypadku tęczowych tablic ma dwie fazy. Pierwsza z nich to obliczenia wstępne:

• Dla każdej z dopuszczalnych wiadomości obliczany jest skrót.
• Wiadomość w postaci skompresowanej jest zapisywana do pliku o nazwie zależnej od części skrótu np. jak pierwsze 4 znaki skrótu.
• Kompresja polega na zapisie wiadomości w sposób przyrostowy. Zachowywana jest tylko różnica pomiędzy aktualna a poprzednia wiadomością.

Etap odwracania wymaga wybrania pliku, odpowiadającego atakowanemu skrótowi, a następnie obliczenia odcisku palca kolejno dla każdego hasła zapisanego w pliku. Jest to jak atak wyczerpujący, zwany również atakiem pełnego przeglądu przeprowadzony dla ograniczonego, niewielkiego podzbioru wiadomości.
Idea algorytmu opiera się na kilku ciekawych spostrzeżeniach. Przede wszystkim kompresja zbioru haseł jest bardziej efektywna, ponieważ ma on znacznie mniejszą entropię, niż odpowiadający mu zbiór skrótów czy par skrót-hasło. Sekwencyjne generowanie wiadomości i zapisywanie ich w plikach również wpłynie na polepszenie stopnia kompresji. Poza tym daje to oszczędność nakładu obliczeniowego względem metod, w których hasła są generowane w sposób pseudolosowy. W ramach metody wykorzystana jest też właściwość funkcji skrótu zapewniająca, że odległości z przestrzeni wiadomości nie są zachowane w przestrzeni skrótów. Dodatkowo wartości skrótów są równomiernie rozłożone w całej dziedzinie. Dzięki temu rozkład haseł miedzy plikami jest również w przybliżeniu równomierny, co sprawia, że utworzone pliki są podobnej wielkości. Poza tym wartość oczekiwana odległości między kolejnymi hasłami w pojedynczym zbiorze nie zależy od długości wiadomości, ale od liczby zbiorów. Przykład kodowania dla ośmiobitowych wiadomości przedstawia Tabela 1. Zalecana liczba plików w metodzie kompresji tablic obliczeń wstępnych to 216 , co daje 2 – 3 bajty potrzebne do zapisania pojedynczej wiadomości. Liczba ta dobrze sprawdza się przy liczności zbioru haseł rzędu 235-240. Rozmiar jednego pliku wynosi wtedy 3*235 /216 =1.572.864, czyli 1,5 MB, co daje czas odwracania skrótu poniżej sekundy. Między innymi dzięki takim właściwościom metoda kompresji tablic obliczeń wstępnych może stanowić atrakcyjną alternatywę dla tęczowych tablic.

Porównanie metod

Tabela pochodzi z materiałów opublikowanych przez Michała Trojnarę i przedstawia porównanie kosztu i skuteczności metody tęczowych tablic oraz metody kompresji tablic obliczeń wstępnych. Wartości w niej zamieszczone dotyczą łamania skrótów LM-DES przy założeniu 237 możliwych haseł. Wydajność wynosiła 106 obliczeń wartości skrótu w ciągu sekundy. Wartości oznaczone gwiazdką (*) zostały wyznaczone empirycznie. Przy pomocy tej tabeli twórca metody chciał pokazać, że jego algorytm w założonych warunkach wykazuje nie gorsze właściwości od tęczowych tablic. Wykorzystanie pamięci, to rozmiar pamięci używanej przez każdą z metod. Tabela przedstawia tę pamięć, która w danej metodzie stanowi największy koszt. Dla tęczowych tablic jest to pamięć RAM, do której ładowane są skróty. W tym wypadku kilka gigabajtów dysku twardego stanowi zaniedbywanly koszt. Dla kompresji tablic obliczeń wstępnych dominującym wydatkiem jest pamięć masowa konieczna do przechowywania rezultatów obliczeń wstępnych. Przy założeniu sekwencyjnego odczytu danych z dysku lub nawet załadowania całego kilkumegabajtowego pliku do pamięci wydatek na dodatkowo wymagany RAM można pominąć. Porównywana wielkość drastycznie, bo prawie trzystukrotnie, różniła się dla obu metod. Różnica ta nie będzie już tak znacząca, gdy uwzględni się ceny nośników pamięci to wydatki na sprzęt okażą się porównywalne dla obu metod. Warto zaznaczyć, że porównywane wielkości są przykładem i to dość szczególnie dobranym. Modyfikacje algorytmu tęczowych tablic potrafią dzięki wstępnemu posortowaniu tabeli według wartości skrótów oraz czytaniu pliku za pomocą takich funkcji jak fseek w C, ograniczyć do minimum rozmiar koniecznej do wykorzystania pamięci operacyjnej. Ponadto metody bazujące na łańcuchach Hellmana, zwanych również TMTO (Time Memory Trade-off ), pozwalają na minimalizację czasu ataku kosztem wzrostu rozmiaru potrzebnej pamięci lub zmniejszeniu pamięci kosztem wydłużenia czasu. Ta cecha jest bodaj największą zaletą metody w porównaniu z kompresją tablic obliczeń wstępnych. Wydajność, czyli czas odwracania pojedynczego skrótu podany w tabeli dla tęczowych tablic, wyznaczona została empirycznie. Jej wartość teoretyczna jest trudna do wyznaczenia bez znajomości zastosowanych funkcji redukcyjnych. Jednak złamanie pojedynczego hasła wymaga obliczenia wartości funkcji skrótu i funkcji redukcyjnych dla całego łańcucha oraz porównania obliczonej wartości ze wszystkimi zapamiętanymi skrótami zanim zostanie wyznaczony odpowiedni łańcuch. To zdecydowanie większy koszt niż obliczenie odcisków palca haseł zapisanych w pliku, aż do znalezienia poszukiwanej wartości. Nawet, jeśli uwzględniony zostanie nakład związany z dekompresją, czyli jedną operacją dodawania na hasło. Również czas wymagany na załadowanie do pamięci będzie mniejszy, bo wymaga wczytania tylko jednego pliku wielkości kilku megabajtów zamiast gigabajta całych tęczowych tablic. Mimo, że skuteczność metody Oechslina jest znacznie wyższa niż prostych łańcuchów, to wciąż istnieje niezerowe prawdopodobieństwo, iż jakieś hasło nie zostanie pokryte przez żaden z ciągów. Algorytm tablic obliczeń wstępnych nie ma takiej wady i niezależnie od używanych funkcji skrótu zawsze pokrywa pełen zbiór wiadomości. Czas obliczeń wstępnych jest znacznie dłuższy dla algorytmu tęczowych tablic. Wynika to z faktu, że dla każdego kroku w łańcuchu konieczne jest nie tylko obliczenie skrótu, ale również wartości funkcji redukcyjnej. Dla metody kompresji tablic obliczeń wstępnych czas obliczeń początkowych jest porównywalny z czasem ataku wyczerpującego. Algorytm wymaga tylko dodatkowej operacji kompresji, czyli jednego odejmowania, dla każdego zapisywanego hasła. Znaczącym czynnikiem nieuwzględnionym w teoretycznych rozważaniach jest czas zapisu na dysk. Dla 384 GB będzie on o wiele dłuższy niż dla 1,4 GB. Spory wolumen koniecznych do zapisania danych jest chyba największą słabością nowej metody. Udostępnienie przez Internet lub na płytach DVD wyników obliczeń wstępnych wielkości kilkuset gigabajtów jest praktycznie niemożliwe. Dla pojedynczych gigabajtów, w przypadku tęczowych tablic, nie stanowi to dużego problemu. Wielkość danych ogranicza również możliwości zastosowania algorytmu. W przypadku komputerów domowych można ją stosować dla kluczy do długości ok. 40 bitów lub wiadomości alfanumerycznych nie dłuższych niż 7 znaków. Powyżej tych wielkości ceny dysków wymaganych do przechowania rezultatów są zbyt wysokie.

Rysunek 3. Generowanie tęczowych tablic za pomocą generatora rtgen z projektu RainbowCrack

Rysunek 4. Odwracanie skrótu MD-5 za pomocą testowego programu

Podsumowanie

Kompresja tablic obliczeń wstępnych jest bardzo ciekawą alternatywą dla popularnego algorytmu tęczowych tablic. Jak dotąd nie zyskała zbyt dużej popularności i rozgłosu – jest znana raczej w kręgach akademickich. Nic nie wskazuje na to, aby nowa metoda miała wyprzeć tęczowe tablice, ale jej atrakcyjność będzie rosnąć wraz ze spadkiem cen nośników danych i wzrostem przepustowości łącz internetowych. Ponieważ jako wynik obliczeń wstępnych przechowane są tylko skompresowane wiadomości, rozmiar przestrzeni dyskowej wymaganej do ich zapisania nie zależy od zastosowanego odcisku palca. W związku z tym rosnąca złożoność i długość skrótów nie wpłynie na wolumen danych. Podobnie jak w przypadku tęczowych tablic zastosowanie tak zwanej soli, stanowi skuteczną ochronę przed atakiem, gdyż każdy dodatkowy bit wiadomości zwiększa wykładniczo liczbę potrzebnych do przechowania i porównania haseł. Zaletą algorytmu jest również jego prostota, dzięki czemu nakład obliczeniowy jest tylko minimalnie większy niż przy ataku wyczerpującym. Choć duży rozmiar tablic obliczeń wstępnych nie pozwala na udostępnienie ich przez Internet w całości, jednak sam algorytm dobrze nadaje się do rozproszonego (distributed) odwracania odcisków palców. Poszczególne, niewielkie pliki z wynikami obliczeń wstępnych mogą zostać umieszczone na różnych komputerach. Dekompozycja zadania odwracania listy skrótów będzie polegała na rozdzieleniu ich tak, aby każda maszyna łamała odciski palców pasujące do jej skompresowanej tabeli. Dzięki temu rozmiar plików ze skompresowanymi hasłami potrzebny do zapisania na każdym z komputerów jest minimalny, a jednocześnie dzięki równomiernemu rozkładowi wartości skrótów obciążenie maszyn również jest równomierne. Nowy algorytm kryje w sobie jeszcze wiele możliwości i choć mało prawdopodobne jest by w ciągu najbliższych lat zastąpił metodę tęczowych tablic, może się stać jej cennym uzupełnieniem.

Testowy program

Ponieważ autorowi tekstu nie są znane ogólnie dostępne programy, wykorzystujące algorytm kompresji tablic obliczeń wstępnych na płycie z pismem dostarczone zostały skrypty implementujące opisywaną metodę. Są to dwa programy napisane w języku skryptowym Python. Pierwszy z nich – prepare.py generuje pliki z tablicami obliczeń wstępnych. Dla zachowania większej przejrzystości kodu do kompresji zastosowany jest standardowy algorytm gzip.
Drugi – crack.py pozwala na złamanie hasła podanego w postaci skrótu MD-5. Oba programy po uruchomieniu z opcją -h wyświetlają pomoc i opcje uruchomienia. Skrypty stanowią jedynie przykład implementacji, nie należy ich traktować jako wydajnego narzędzia do łamania haseł.

W Sieci

• http://cygnus.tele.pw.edu.pl/~zkotulsk/seminarium/Trojnara-precomputations.pdf – prezentacja Michała Trojnary o kompresji tablic obliczeń wstępnych,
• http://kestas kuliukas com/RainbowTables/ – opis metody tęczowych tablic,
• http://www h online.com/security/features/Hellman and Rivest 746294 html – algorytm łańcuchów M. Hellmana,
• http://csrc nist gov/publications/fips/fips180-2/fips180-2 pdf – publikacja na temat bezpiecznych funkcji skrótu,
• http://www objectif securite ch/research/websec06.pdf Do you need to fear of the rainbow publikacja P. Oechslina na temat tęczowych tablic.

Wojciech Terlikowski
Autor jest z wykształcenia inżynierem elektroniki. Od ponad dwóch lat pracuje w jednej z największych polskich firm informatycznych, gdzie pełni rolę m.in. konsultanta do spraw bezpieczeństwa systemów informatycznych.
Kontakt z autorem: w.terlikowski@terlikowski.eu.org.