Stół tęczowy - Rainbow table

Tęczowe tablice to precomputed stół do buforowania wyjścia kryptograficznych funkcji skrótu , zwykle do pękania hashe haseł. Tabele są zwykle używane do odzyskiwania funkcji wyprowadzania klucza (lub numerów kart kredytowych itp.) o określonej długości składającej się z ograniczonego zestawu znaków. Jest to praktyczny przykład kompromisu czasoprzestrzennego , wykorzystujący mniej czasu przetwarzania przez komputer i więcej pamięci niż atak brute-force, który oblicza hash przy każdej próbie, ale więcej czasu przetwarzania i mniej pamięci niż prosta funkcja wyprowadzania klucza z jednym wpisem za hasz. Użycie kluczowej pochodnej, która wykorzystuje sól, sprawia, że ​​ten atak jest niewykonalny.

Tęczowe tablice zostały wymyślone przez Philippe'a Oechslina jako zastosowanie wcześniejszego, prostszego algorytmu Martina Hellmana .

Tło

W przypadku uwierzytelniania użytkowników hasła są przechowywane w postaci zwykłego tekstu lub skrótów . Ponieważ hasła przechowywane w postaci zwykłego tekstu można łatwo wykraść w przypadku naruszenia dostępu do bazy danych, bazy danych zwykle przechowują skróty. W ten sposób nikt – w tym system uwierzytelniania – nie może nauczyć się hasła tylko na podstawie wartości przechowywanej w bazie danych.

Gdy użytkownik wprowadza hasło w celu uwierzytelnienia, obliczany jest dla niego skrót, a następnie porównywany z przechowywanym skrótem dla tego użytkownika. Uwierzytelnianie się powiedzie, jeśli dwa skróty są zgodne. (Z drugiej strony próba użycia zaszyfrowanej wartości jako hasła do zalogowania się nie powiedzie, ponieważ system uwierzytelniania zahaszuje ją po raz drugi).

Aby nauczyć się hasła z hasza, należy znaleźć ciąg, który po wprowadzeniu do funkcji haszującej tworzy ten sam hasz. To to samo, co odwracanie funkcji skrótu.

Chociaż ataki brute-force (np. ataki słownikowe ) mogą być używane do próby odwrócenia funkcji skrótu, mogą stać się niewykonalne, gdy zestaw możliwych haseł jest wystarczająco duży. Alternatywą dla brute-force jest użycie wstępnie obliczonych tabel łańcuchów mieszających . Stoły Rainbow to szczególny rodzaj takiego stołu, który pokonuje pewne trudności techniczne .

Etymologia

Termin „Tęczowe Tablice” został po raz pierwszy użyty w pierwszym artykule dr Oechslina. Termin ten odnosi się do sposobu, w jaki różne funkcje redukujące są używane w celu zwiększenia wskaźnika powodzenia ataku. Oryginalna metoda Hellmana wykorzystuje wiele małych tabelek z różnymi funkcjami redukcji. Tabele Rainbow są znacznie większe i wykorzystują inną funkcję redukcji w każdej kolumnie. Kiedy kolory są używane do reprezentowania funkcji redukcji, w tabeli tęczy pojawia się tęcza. Rycina 2 artykułu dr. Oechslina zawiera czarno-białą grafikę, która ilustruje, w jaki sposób te sekcje są ze sobą powiązane. Podczas swojej prezentacji na konferencji Crypto 2003, dr Oechslin dodał kolor do grafiki, aby skojarzenie tęczy było bardziej wyraźne. Udoskonalona grafika, która została zaprezentowana na konferencji, jest pokazana po prawej stronie.

Wstępnie obliczone łańcuchy skrótów

Załóżmy, że mamy funkcję skrótu hasła H i skończony zbiór haseł P. Celem jest wstępne obliczenie struktury danych, która przy dowolnym wyniku h funkcji skrótu może albo zlokalizować element p w P tak, że H( p ) = h , lub ustalić, że nie ma takiego p w P. Najprostszym sposobem na to jest obliczenie H( p ) dla wszystkich p w P , ale następnie przechowywanie tablicy wymaga Θ (|P| n ) bitów przestrzeni, gdzie | P| jest rozmiarem zbioru P, a n jest rozmiarem wyjścia H, co jest zaporowe dla dużych |P|. Łańcuchy haszujące są techniką zmniejszania tego zapotrzebowania na miejsce. Chodzi o to, aby zdefiniować funkcję redukcji R, który zawiera wartości hash z powrotem do wartości w P. Uwaga jednak, że funkcja redukcji nie jest w rzeczywistości odwrotnością funkcji skrótu, ale raczej inna funkcja z zamienione domeny i codomain z funkcja skrótu. Zamieniając funkcję skrótu z funkcją redukcji, tworzą się łańcuchy naprzemiennych haseł i wartości skrótów. Na przykład, gdyby P było zbiorem sześcioznakowych haseł alfabetycznych, składających się z małych liter, a wartości skrótu miały długość 32 bity, łańcuch mógłby wyglądać tak:

${\ Displaystyle {\ kolor {czerwony} {\ mathtt {aaaaaa}}} \ {\ xrightarrow [{\; H \;}] {}} \ {\ mathtt {281DAF40}} \ {\ xrightarrow [{ \;R\;}]{}}\,{\mathtt {sgfnyd}}\,{\xrightarrow[{\;H\;}]{}}\,{\mathtt {920ECF10}}\,{\xrightarrow [{\;R\;}]{}}\,{\kolor {fioletowy}{\mathtt {kiebgt}}}}$

Jedynym wymaganiem funkcji redukcji jest możliwość zwrócenia wartości „zwykłego tekstu” w określonym rozmiarze.

Aby wygenerować tabelę, wybieramy losowy zestaw początkowych haseł z P, obliczamy łańcuchy o określonej długości k dla każdego z nich i przechowujemy tylko pierwsze i ostatnie hasło w każdym łańcuchu. Pierwsze hasło nazywa się punktem początkowym, a ostatnie punktem końcowym . W powyższym przykładowym łańcuchu „aaaaaa” będzie punktem początkowym, a „kiebgt” będzie punktem końcowym, a żadne inne hasła (ani wartości skrótu) nie zostaną zapisane.

Teraz, mając wartość skrótu h , którą chcemy odwrócić (znajdź odpowiednie hasło), oblicz łańcuch zaczynający się od h , stosując R, następnie H, potem R i tak dalej. Jeśli w dowolnym momencie zaobserwujemy wartość pasującą do jednego z punktów końcowych w tabeli, otrzymujemy odpowiedni punkt początkowy i używamy go do odtworzenia łańcucha. Jest duża szansa, że ​​ten łańcuch będzie zawierał wartość h , a jeśli tak, to bezpośrednio poprzedzająca wartość w łańcuchu to hasło p , którego szukamy.

Na przykład, jeśli otrzymamy hash 920ECF10 , obliczymy jego łańcuch, najpierw stosując R:

${\ Displaystyle {\ mathtt {920ECF10}} \, {\ xrightarrow [{\; R \;}] {}} \, {\ kolor {fioletowy} {\ mathtt {kiebgt}}}}$

Ponieważ " kiebgt " jest jednym z punktów końcowych w naszej tabeli, bierzemy odpowiednie hasło początkowe " aaaaaa " i śledzimy jego łańcuch aż do osiągnięcia 920ECF10 :

${\ Displaystyle {\ kolor {czerwony} {\ mathtt {aaaaaa}}} \ {\ xrightarrow [{\; H \;}] {}} \ {\ mathtt {281DAF40}} \ {\ xrightarrow [{ \;R\;}]{}}\,{\mathtt {sgfnyd}}\,{\xrightarrow[{\;H\;}]{}}\,{\mathtt {920ECF10}}}$

Hasło to „ sgfnyd ” (lub inne hasło o tej samej wartości skrótu).

Zauważ jednak, że ten łańcuch nie zawsze zawiera wartość hash h ; może się zdarzyć, że łańcuch zaczynający się od h połączy się z łańcuchem mającym inny punkt początkowy. Na przykład możemy otrzymać wartość skrótu FB107E70, a gdy śledzimy jego łańcuch, otrzymujemy kiebgt:

${\displaystyle {\mathtt {FB107E70}}\,{\xrightarrow[{\;R\;}]{}}\,{\mathtt {bvtdll}}\,{\xrightarrow[{\;H\;}] {}}\,{\mathtt {0EE80890}}\,{\xrightarrow[{\;R\;}]{}}\,{\color {Violet}{\mathtt {kiebgt}}}}$

Ale FB107E70 nie znajduje się w łańcuchu zaczynającym się od „aaaaaa”. Nazywa się to fałszywym alarmem . W takim przypadku ignorujemy dopasowanie i kontynuujemy wydłużanie łańcucha h w poszukiwaniu innego dopasowania. Jeśli łańcuch h zostanie przedłużony do długości k bez dobrych dopasowań, to hasło nigdy nie zostało utworzone w żadnym z łańcuchów.

Zawartość tabeli nie zależy od wartości skrótu, która ma zostać odwrócona. Jest tworzony raz, a następnie wielokrotnie używany do wyszukiwania w niezmienionej postaci. Zwiększenie długości łańcuszka zmniejsza rozmiar stołu. Zwiększa również czas wymagany do wykonania wyszukiwania i jest to kompromis pamięci czasu w tabeli tęczy. W prostym przypadku łańcuchów jednoelementowych wyszukiwanie jest bardzo szybkie, ale tabela jest bardzo duża. Gdy łańcuchy stają się dłuższe, wyszukiwanie spowalnia, ale zmniejsza się rozmiar tabeli.

Proste łańcuchy haszujące mają kilka wad. Najpoważniejsze, jeśli w dowolnym momencie zderzają się dwa łańcuchy (wytwarzają tę samą wartość), połączą się, a w konsekwencji tabela nie pokryje tylu haseł, mimo że zapłacił ten sam koszt obliczeniowy za wygenerowanie. Ponieważ poprzednie łańcuchy nie są przechowywane w całości, nie można tego skutecznie wykryć. Na przykład, jeśli trzecia wartość w łańcuchu 3 pasuje do drugiej wartości w łańcuchu 7, dwa łańcuchy obejmą prawie tę samą sekwencję wartości, ale ich końcowe wartości nie będą takie same. Funkcja mieszająca H prawdopodobnie nie spowoduje kolizji, ponieważ jest zwykle uważana za ważną cechę bezpieczeństwa, aby tego nie robić, ale funkcja redukcyjna R, ze względu na jej konieczność prawidłowego pokrycia prawdopodobnych tekstów jawnych, nie może być odporna na kolizje .

Inne trudności wynikają z ważności wyboru właściwej funkcji dla R. Wybór R jako tożsamości jest niewiele lepszy niż podejście brute force. Tylko wtedy, gdy atakujący ma dobre pojęcie o tym, jakie będą prawdopodobne teksty jawne, może wybrać funkcję R, która zapewni, że czas i przestrzeń zostaną wykorzystane tylko dla prawdopodobnych tekstów jawnych, a nie całej przestrzeni możliwych haseł. W efekcie R przenosi wyniki wcześniejszych obliczeń hash z powrotem do prawdopodobnych tekstów jawnych, ale ta zaleta ma tę wadę, że R prawdopodobnie nie wygeneruje każdego możliwego tekstu jawnego w klasie, którą atakujący chce sprawdzić, odmawiając atakującemu pewności, że żadne hasła nie pochodzą z jego wybraną klasę. Również może być trudne zaprojektowanie funkcji R tak, aby pasowała do oczekiwanego rozkładu tekstów jawnych.

Stoły tęczowe

Tabele tęczowe skutecznie rozwiązują problem kolizji ze zwykłymi łańcuchami mieszającymi poprzez zastąpienie pojedynczej funkcji redukcyjnej R sekwencją powiązanych funkcji redukcyjnych R ₁ do R _k . W ten sposób, aby dwa łańcuchy zderzyły się i połączyły, muszą osiągnąć tę samą wartość w tej samej iteracji : w konsekwencji końcowe wartości w tych łańcuchach będą identyczne. Ostateczny przebieg przetwarzania końcowego może posortować łańcuchy w tabeli i usunąć wszystkie "duplikaty" łańcuchów, które mają te same wartości końcowe, co inne łańcuchy. Następnie generowane są nowe łańcuchy, aby wypełnić tabelę. Łańcuchy te nie są wolne od kolizji (mogą na krótko na siebie nachodzić), ale nie łączą się, co drastycznie zmniejsza ogólną liczbę kolizji.

Użycie sekwencji funkcji redukcyjnych zmienia sposób wyszukiwania: ponieważ interesująca wartość skrótu może być znaleziona w dowolnym miejscu w łańcuchu, konieczne jest wygenerowanie k różnych łańcuchów. Pierwszy łańcuch zakłada, że ​​wartość skrótu znajduje się na ostatniej pozycji skrótu i ​​po prostu stosuje R _k ; następny łańcuch zakłada, że ​​wartość skrótu znajduje się na przedostatniej pozycji i stosuje R _{k -1} , następnie H , potem R _k ; i tak dalej, aż do ostatniego łańcucha, który stosuje wszystkie funkcje redukujące naprzemiennie z H. Tworzy to nowy sposób generowania fałszywego alarmu: jeśli „odgadniemy” błędną pozycję wartości skrótu, możemy niepotrzebnie ocenić łańcuch.

Chociaż tabele tęczowe muszą podążać za większą liczbą łańcuchów, nadrabiają to, mając mniej tabel: proste tabele z łańcuchem mieszającym nie mogą wzrosnąć poza pewien rozmiar bez gwałtownego stania się nieefektywnym z powodu łączenia łańcuchów; aby sobie z tym poradzić, utrzymują wiele tabel, a każde wyszukiwanie musi przeszukiwać każdą tabelę. Tabele Rainbow mogą osiągnąć podobną wydajność z tabelami, które są k razy większe, co pozwala im na wykonanie współczynnika k mniejszej liczby wyszukiwań.

Przykład

1. Zaczynając od skrótu ("re3xes") na obrazku poniżej, oblicza się ostatnią redukcję użytą w tabeli i sprawdza, czy hasło pojawia się w ostatniej kolumnie tabeli (krok 1).
2. Jeśli test się nie powiedzie ( rambo nie pojawia się w tabeli), oblicza się łańcuch z dwiema ostatnimi redukcjami (te dwie redukcje są przedstawione w kroku 2)

   Uwaga: Jeśli ten nowy test ponownie się nie powiedzie, kontynuuje się 3 redukcje, 4 redukcje itd., aż do znalezienia hasła. Jeśli żaden łańcuch nie zawiera hasła, atak się nie powiódł.

3. Jeśli ten test jest pozytywny (krok 3, linux23 pojawia się na końcu łańcucha iw tabeli), hasło jest pobierane na początku łańcucha, w którym powstaje linux23 . Tutaj znajdujemy passwd na początku odpowiedniego łańcucha przechowywanego w tabeli.
4. W tym momencie (krok 4) generuje się łańcuch i porównuje w każdej iteracji hash z hashem docelowym. Test jest ważny i znajdujemy skróty re3x w łańcuchu. Obecne hasło ( kultura ) jest tym, które wyprodukowało cały łańcuch: atak się powiódł.

Tabele Rainbow wykorzystują udoskonalony algorytm z inną funkcją redukcji dla każdego „ogniwa” w łańcuchu, dzięki czemu w przypadku kolizji skrótów w dwóch lub więcej łańcuchach łańcuchy nie połączą się, o ile kolizja nie nastąpi w taka sama pozycja w każdym łańcuchu. Zwiększa to prawdopodobieństwo prawidłowego pęknięcia dla danego rozmiaru tabeli, kosztem kwadratury liczby kroków wymaganych na wyszukiwanie, ponieważ procedura wyszukiwania musi teraz również iterować przez indeks pierwszej funkcji redukcji użytej w łańcuchu.

Tabele Rainbow są specyficzne dla funkcji skrótu, dla której zostały utworzone, np. tabele MD5 mogą łamać tylko skróty MD5. Teoria tej techniki została wymyślona przez Philippe'a Oechslina jako szybka forma kompromisu czas/pamięć , którą zaimplementował w programie do łamania haseł systemu Windows Ophcrack . Później opracowano potężniejszy program RainbowCrack , który może generować i używać tęczowych tablic dla różnych zestawów znaków i algorytmów mieszających, w tym hash LM , MD5 i SHA-1 .

W prostym przypadku, gdy funkcja redukcji i funkcja skrótu nie kolidują ze sobą, biorąc pod uwagę kompletną tablicę tęczy (taką, która gwarantuje znalezienie odpowiedniego hasła przy dowolnym hashu) rozmiar ustawionego hasła | P |, czas T , który był potrzebny do obliczenia tabeli, długość tabeli L i średni czas t potrzebny do znalezienia hasła pasującego do danego skrótu są bezpośrednio powiązane:

${\ Displaystyle T = | P |}$

${\ Displaystyle t = {\ Frac {| P |} {2L}}}$

W ten sposób 8-znakowe małe litery w haśle alfanumerycznym (| P | ≃ 3×10 ¹² ) byłyby łatwe do opanowania na komputerze osobistym, podczas gdy 16-znakowe małe litery w hasłach alfanumerycznych (| P | ≃ 10 ²⁵ ) byłyby całkowicie niewykonalne.

Obrona przed tęczowymi tablicami

Tęczowa tablica jest nieskuteczna w przypadku haszy jednokierunkowych zawierających duże sole . Rozważmy na przykład skrót hasła, który jest generowany przy użyciu następującej funkcji (gdzie „ + ” jest operatorem konkatenacji ):

saltedhash(password) = hash(password + salt)

Lub

saltedhash(password) = hash(hash(password) + salt)

Wartość soli nie jest tajna i może być generowana losowo i przechowywana z hashem hasła. Duża wartość soli zapobiega atakom polegającym na wykonywaniu obliczeń wstępnych, w tym tablicach tęczowych, zapewniając unikatowe zaszyfrowanie hasła każdego użytkownika. Oznacza to, że dwóch użytkowników z tym samym hasłem będzie miało różne skróty haseł (zakładając, że używane są różne sole). Aby odnieść sukces, atakujący musi wstępnie obliczyć tabele dla każdej możliwej wartości soli. Sól musi być wystarczająco duża, w przeciwnym razie atakujący może stworzyć tabelę dla każdej wartości soli. W przypadku starszych haseł Unix, które używały 12-bitowej soli, wymagałoby to 4096 tabel, co oznacza znaczny wzrost kosztów dla atakującego, ale nie jest to niepraktyczne w przypadku terabajtowych dysków twardych. Metody SHA2-crypt i bcrypt — używane w systemach Linux , BSD Unix i Solaris — mają 128-bitowe sole. Te większe wartości soli powodują, że ataki oparte na obliczeniach wstępnych na te systemy są niewykonalne dla prawie każdej długości hasła. Nawet gdyby atakujący mógł wygenerować milion tabel na sekundę, nadal potrzebowałby miliardów lat, aby wygenerować tabele dla wszystkich możliwych soli.

Inną techniką, która pomaga zapobiegać atakom związanym z obliczeniami wstępnymi, jest rozciąganie klucza . Gdy używane jest rozciąganie, sól, hasło i niektóre pośrednie wartości skrótu są wielokrotnie przepuszczane przez podstawową funkcję skrótu, aby wydłużyć czas obliczeń wymagany do zaszyfrowania każdego hasła. Na przykład MD5-Crypt używa pętli 1000 iteracji, która wielokrotnie przekazuje sól, hasło i bieżącą pośrednią wartość skrótu z powrotem do podstawowej funkcji skrótu MD5. Skrót hasła użytkownika jest połączeniem wartości soli (która nie jest tajna) i końcowego skrótu. Dodatkowy czas nie jest zauważalny dla użytkowników, ponieważ przy każdym logowaniu muszą czekać tylko ułamek sekundy. Z drugiej strony rozciąganie zmniejsza skuteczność ataków brute-force proporcjonalnie do liczby iteracji, ponieważ zmniejsza liczba prób, które atakujący może wykonać w danym przedziale czasowym. Ta zasada jest stosowana w MD5-Crypt i bcrypt. To również znacznie wydłuża czas potrzebny do zbudowania wstępnie obliczonej tabeli, ale w przypadku braku soli wystarczy to zrobić tylko raz.

Alternatywne podejście, zwane wzmacnianiem klucza , przedłuża klucz losową solą, ale następnie (w przeciwieństwie do rozciągania klucza) bezpiecznie usuwa sól. Zmusza to zarówno atakującego, jak i legalnych użytkowników do przeprowadzenia brutalnego wyszukiwania wartości soli. Chociaż artykuł, który wprowadził rozciąganie klawiszy, odwoływał się do tej wcześniejszej techniki i celowo wybrał inną nazwę, termin „wzmocnienie klawisza” jest obecnie często (prawdopodobnie błędnie) używany w odniesieniu do rozciągania klawisza.

Tęczowe tabele i inne ataki oparte na obliczeniach wstępnych nie działają w przypadku haseł, które zawierają symbole spoza założonego zakresu lub są dłuższe niż te, które zostały wstępnie obliczone przez atakującego. Można jednak generować tabele, które uwzględniają typowe sposoby, w jakie użytkownicy próbują wybierać bezpieczniejsze hasła, takie jak dodanie liczby lub znaku specjalnego. Ze względu na spore inwestycje w przetwarzanie obliczeniowe, tęczowe tablice o długości przekraczającej czternaście miejsc nie są jeszcze powszechne. Tak więc wybranie hasła dłuższego niż czternaście znaków może zmusić atakującego do skorzystania z metod brute-force.

Konkretne intensywne wysiłki skoncentrowane na hashu LM , starszym algorytmie haszującym używanym przez firmę Microsoft, są publicznie dostępne. Skrót LM jest szczególnie podatny na ataki, ponieważ hasła dłuższe niż 7 znaków są dzielone na dwie sekcje, z których każda jest haszowana osobno. Wybranie hasła składającego się z piętnastu znaków lub dłuższego gwarantuje, że hash LM nie zostanie wygenerowany.

Typowe zastosowania

Prawie wszystkie dystrybucje i odmiany Unixa , Linuksa i BSD używają skrótów z solami, chociaż wiele aplikacji używa tylko skrótu (zazwyczaj MD5 ) bez soli. Rodzina Microsoft Windows NT/2000 wykorzystuje metodę mieszania LAN Manager i NT LAN Manager (opartą na MD4 ) i jest również niesolona, ​​co czyni ją jedną z najczęściej generowanych tabel. Tęczowe tablice odnotowały zmniejszone użycie od 2020 roku, ponieważ solenie jest bardziej powszechne, a ataki brute force oparte na GPU stały się bardziej praktyczne. Jednak tabele Rainbow są dostępne dla ośmio- i dziewięcioznakowych haseł NTLM .

Zobacz też

• A5/1
• Brutalny atak
• DystrRTgen
• Algorytm kangura Pollarda

Uwagi

Bibliografia

• Oechslin, Filip (2003-08-17). „Dokonywanie szybszej wymiany kryptoanalitycznej pamięci czasu”. Dokonywanie szybszej wymiany kryptoanalitycznej pamięci czasu (PDF) . Postępy w kryptologii: Proceedings of CRYPTO 2003, 23. doroczna międzynarodowa konferencja kryptologiczna . Notatki z wykładów z informatyki. 2729 . Santa Barbara, Kalifornia , USA: Springer. s. 617-630. doi : 10.1007/978-3-540-45146-4_36 . Numer ISBN 978-3-540-40674-7.

Zewnętrzne linki

• Strona Ophcrack autorstwa Philippe'a Oechslina Oryginalne badania nad tablicą tęczową
• Kryptografia w Curlie