Co to są tęczowe stoły i do czego są używane?

Tęczowe tabele są często mylone z inna, prostsza technika, która wykorzystuje czas obliczeniowy przechowywanie kompromisów w odzyskiwaniu haseł: tablice haszujące.

Tabele haszujące są konstruowane przez haszowanie każdego słowa w słowniku haseł. Pary hash-hash są przechowywane w tabeli posortowane według wartości hash. Aby użyć tablicy haszującej, po prostu weź skrót i przeprowadź wyszukiwanie binarne w tabeli, aby znaleźć oryginalne hasło, jeśli jest obecne.

Tęczowe tabele są bardziej złożone. Zbudowanie tęczowej tabeli wymaga dwóch rzeczy : funkcja haszująca i funkcja redukcji. Funkcja haszująca dla danego zestawu Rainbow Tables musi pasować do zaszyfrowanego hasła, które chcesz odzyskać. Funkcja redukcji musi przekształcić hash w coś, co można wykorzystać jako hasło. Prostą funkcją redukcji jest Base64 zakodować hash, a następnie skrócić go do określonej liczby znaków.

Tęczowe tabele są zbudowane z „łańcuchów” o określonej długości: na przykład 100 000. Aby skonstruować łańcuch, wybierz losową wartość początkową. Następnie zastosuj funkcje haszujące i redukujące do tego ziarna oraz jego wyniku i kontynuuj iterację 100 000 razy. Przechowywane są tylko ziarno i wartość końcowa. Powtórz ten proces, aby utworzyć dowolną liczbę łańcuchów.

Aby odzyskać hasło za pomocą Rainbow Tables, hash hasła przechodzi powyższy proces dla tej samej długości: w tym przypadku 100 000, ale każde ogniwo w łańcuchu zostaje zachowane. Każde ogniwo w łańcuchu jest porównywane z końcową wartością każdego łańcucha. Jeśli jest dopasowanie, łańcuch można zrekonstruować, zachowując zarówno dane wyjściowe każdej funkcji mieszającej, jak i dane wyjściowe każdej funkcji redukcji. Ten zrekonstruowany łańcuch będzie zawierał hash danego hasła, a także hasło, które je wygenerowało.

Mocną stroną tabeli skrótów jest to, że odzyskiwanie hasła jest błyskawiczne (wyszukiwanie binarne), a osoba budująca tabela skrótów może wybrać, co do niej trafi, na przykład 10 000 najpopularniejszych haseł. Wadą w porównaniu z Rainbow Tables jest to, że tablice skrótów muszą przechowywać każdą pojedynczą parę hash-password.

Rainbow Tables mają tę zaletę, że osoba tworząca te tabele może wybrać, ile pamięci jest wymagane, wybierając liczbę linków w każdy łańcuch. Im więcej powiązań między zarodkiem a wartością końcową, tym więcej haseł jest przechwytywanych. Jedną ze słabości jest to, że osoba budująca łańcuchy nie wybiera haseł, które przechwytuje, więc Rainbow Tables nie można zoptymalizować pod kątem typowych haseł. Ponadto odzyskiwanie hasła obejmuje przetwarzanie długich łańcuchów skrótów, co sprawia, że odzyskiwanie jest kosztowną operacją. Im dłuższe łańcuchy, tym więcej haseł jest w nich przechwytywanych, ale potrzeba więcej czasu, aby znaleźć hasło w środku.

Tabele haszujące są dobre dla typowych haseł, Rainbow Tables są dobre dla trudnych haseł. Najlepszym podejściem byłoby odzyskanie jak największej liczby haseł przy użyciu tabel skrótów i / lub konwencjonalnego łamania przy użyciu słownika N najważniejszych haseł. Dla tych, którzy pozostali, użyj Rainbow Tables.

Komentarze

• O mój Boże, przyznaję, że jestem zszokowany – omawiam i wyjaśniam tabele Rainbow wszystkie i przez cały ten czas wydaje się, że byłem jednym z ” często mylonych „! Zrobiłbym całkowicie +1000 razy, naprawdę nauczyłem się tutaj czegoś nowego (i myślałem, że znałem odpowiedź). Cieszę się, że mimo wszystko zadałem to pytanie … Dziękuję!
• Chociaż mówiąc konkretnie (teraz, gdy otworzyłeś oczy, przeprowadziłem więcej badań :)), Rainbow Tables różnią się od Hellman Hash Chains za pomocą kilka różnych funkcji redukcji. Rzeczywiście bardziej skomplikowany … ale naprawdę całkiem piękny pomysł (Ach! To dlatego , dlaczego ' nazywają się ” Rainbow ” tabele?)
• Zgadzam się, że to bardzo dobre wyjaśnienie. W mojej odpowiedzi wyjaśniłem to prosto, a także naprawdę wyjaśniłem to źle, będąc zbyt prostym.Piękno tabel Rainbow polega na tym, że nie ' nie przechowują wszystkich wartości skrótu. Mam zamiar edytować moje, ale także głosować, ponieważ jest to zdecydowanie lepsze wyjaśnienie.
• Hmm … Chociaż im więcej o tym myślę, w prawdziwych systemach Rainbow Tables nie są tak przydatne jak tablice skrótów. Jak już wspomniałeś, w przypadku popularnych haseł tabele skrótów są znacznie lepsze (ponieważ są o rząd wielkości szybsze, a wymagania dotyczące rozmiaru słownika haseł są oczywiście znacznie mniejsze niż cały możliwy zakres haseł). A kogo ' żartujemy? Większość haseł należy do tej kategorii, bardzo rzadko (i będzie przez jakiś czas) trzeba dzwonić w trybie RT.
• Niestety, zgubiłeś mnie tutaj: ” Aby odzyskać hasło za pomocą Rainbow Tables, hasło podlega powyższemu procesowi przez tę samą długość. ” W jaki sposób hasło może przejść proces, gdy ' nawet nie wiadomo? Czy chodziło Ci o skrót hasła? Ponadto ' to: ” Każde ogniwo w łańcuchu jest porównywane z końcową wartością każdego łańcucha. ” Nie widzę sytuacji, w której łącze w łańcuchu pasowałoby do końcowej wartości w łańcuchu, ponieważ wartość linku byłaby stale mieszana i zmniejszana.

Istnieje wiele dobrych wyjaśnień tego, czym są tęczowe tabele, ten Jak działają Rainbow Tables jest szczególnie dobra. Również artykuł w Wikipedii również ma bardzo dobre wyjaśnienie. Aby uzyskać nieco dokładniejsze informacje, ostateczny artykuł na ten temat to Szybsza kryptoanalityczna wymiana czasu i pamięci .

Prostym wyjaśnieniem Rainbow Tables jest to, że wykorzystują technikę wymiany pamięci czasu. Znaczenie zamiast brać docelową wartość skrótu i słownik słów, a następnie haszować każde słowo i robić porównania w locie (podejście brutalnej siły z użyciem czegoś takiego jak Jan ), zamiast tego należy z góry zaszyfrować wszystkie wartości w słowniku (może to zająć bardzo dużo czasu w zależności od rozmiaru słownika). Ale kiedy już to zrobisz, możesz porównać dowolną liczbę haszów z wartościami wstępnie zahaszowanymi w tabelach tęczy, jest to znacznie szybsze niż ponowne obliczanie skrótów.

Wyjaśnienie, które napisałem tutaj wcześniej w próba bycia krótką była myląca, ponieważ nie wyjaśniała zastosowania redukcji, z których korzystają tęczowe tablice. Aby uzyskać lepsze wyjaśnienie, dopóki nie przepiszę tego fragmentu, zobacz @Crunge answer .

Możesz samodzielnie wygenerować tęczowe tablice za pomocą aplikacji takiej jak RainbowCrack lub możesz je pobrać ze źródeł takich jak The Shmoo Group , Free Rainbow Tables , projekt Ophcrack i wiele innych miejsc, w zależności od tego, do jakiego typu skrótów potrzebujesz tabel.

Aby chronić się przed atakiem opartym na Rainbow Table, najskuteczniejszą metodą walki z nim jest upewnienie się, że każdy hash w systemie jest solony . To sprawia, że wstępnie wygenerowane tabele tęczowe są bezużyteczne i oznaczałoby, że atakujący musiałby wygenerować niestandardowy zestaw tabel do użycia przeciwko docelowym skrótom, co byłoby możliwe tylko wtedy, gdyby znał sól.

Komentarze

• Ponadto (rozważ edycję tego w), jeśli używasz innej soli dla każdego hasła, zapisując je w postaci niezaszyfrowanej w bazie danych, zaatakowany musiałby wygenerować niestandardowy zestaw tabel dla każdego skrótu, który pokonałby obiekt ćwiczenia – celem tęczowej tabeli jest brutalne wymuszenie całej przestrzeni na hasła, a następnie uzyskanie wszystkich haseł dla jednej brutalnej siły wysiłek; jeśli ' otrzymujesz tylko jedno hasło na tęczową tabelę, równie dobrze możesz bezpośrednio brutalnie wymusić skrót.

Cel i znaczenie

Tęczowe tabele pomagają złamać trudne hasła, tj. takie, których nie można znaleźć nawet w dużym słowniku. Hasła były historycznie przechowywane jako zwykłe skróty w bazach danych i właśnie w tym celu „tablice tęczowe są skuteczne: utwórz pojedynczą tęczową tabelę (wolno) i uruchom dowolną liczbę baz danych pełnych skrótów (szybko).

Obecnie coraz więcej systemów korzysta z odpowiednich algorytmów przechowywania haseł, takich jak Bcrypt, Scrypt lub Argon2. Zobacz: Jak bezpiecznie [przechowywać] hasła? Te algorytmy to nie jest już „podatny” na tęczowe tablice: ponieważ każdy hash jest unikalny, nawet jeśli hasła są równe, tęczowe tablice już nie działają.

Dlatego tęczowe tablice nie są dziś popularne.Nawet jeśli nie używa się czegoś nowoczesnego, takiego jak Argon2, programiści zwykle wiedzą, że powinni przynajmniej użyć soli. To już wystarczy, aby tęczowy stół stał się bezużyteczny.

Jak działają

Tworzenie tabeli

Wyobraź sobie, że tworzymy tęczową tablicę z zaledwie dwoma łańcuchami, każdy o długości 5. Tablica tęczy jest przeznaczona dla fikcyjnej funkcji skrótu MD48, która daje 48 bitów (tylko 12 znaków szesnastkowych). Podczas budowania łańcucha widzimy to:

Chain 0: 0=cfcd208495d5 => z=fbade9e36a3f => renjaj820=7668b2810262 => aL=8289e8a805d7 => ieioB=2958b80e4a3a => WLgOSj Chain 1: 1=c4ca4238a0b9 => ykI4oLkj=140eda4296ac => Dtp=1b59a00b7dbe => W=61e9c06ea9a8 => 6cBuqaha=d4d2e5280034 => 0uUoAD 

Zaczynamy od 0, ponieważ jest to pierwszy łańcuch (potrzebujemy tylko jakiejś wartości na początek). Kiedy haszujemy to za pomocą MD48, zamienia się to w cfcd208495d5. Teraz stosujemy funkcję „redukuj”, która zasadniczo formatuje ten skrót z powrotem do hasło i otrzymujemy „z”. Kiedy ponownie to haszujemy, otrzymujemy fbade9e36a3f, a następnie ponownie je zmniejszamy i otrzymujemy renjaj820 . Jest jeszcze kilka cykli, a końcowy wynik to WLgOSj.

To samo dotyczy drugiego łańcucha. Po prostu zaczynamy od innej wartości i robimy to samo. To kończy się na 0uUoAD.

Nasza pełna tęcza tabela wygląda teraz tak:

WLgOSj => 0 0uUoAD => 1 

To wszystko, co musisz przechowywać.

Wyszukiwanie skrótu

Powiedzmy, że znaleźliśmy hash online, 7668b2810262. Załatwmy go przy użyciu naszej tabeli!

Looking for hash "7668b2810262", reduced to "aL". hashed=>reduced "aL" to ieioB hashed=>reduced "ieioB" to WLgOSj Found a match, "WLgOSj" is in our rainbow table: WLgOSj => 0 The chain starts with "0". Let"s walk that chain and look for the hash. hashed "0" to cfcd208495d5 hashed "z" to fbade9e36a3f hashed "renjaj820" to 7668b2810262 That hash matches! Found the password: renjaj820 

Aby się tym bawić, powyższe przykłady zostały utworzone przy użyciu tego skryptu Pythona: https://gist.github.com/lgommans/83cbb74a077742be3b31d33658f65adb

Właściwości skalowania

W skrócie:

• Szybkie wyszukiwanie oznacza większe tabele, przy założeniu, że pokrycie pozostaje takie samo.
• Lepsze pokrycie oznacza wolniejsze wyszukiwania lub większe tabele.
• Mniejsze tabele oznaczają wolniejsze wyszukiwania lub gorsze pokrycie.

W poniższych sekcjach przyjęto, że czas na redukcję skrótu i skrótu wynosi 1 µs i nie uwzględnia kolizji. To są wszystkie liczby, które mają służyć jako przykłady, a nie dokładne wartości.

Czas wyszukiwania

Jeśli operacja haszowania + redukcji zajmie mikrosekundę, wygenerowanie tabeli z milionem łańcuchów i 10 000 redukcji na łańcuch zajmie około 3 godzin:
chain_length × chain_count / reductions_per_second / seconds_per_hour
= 10 000 × 1 000 000 / 1 000 000 / 3600 = 2,8 godziny.

Wyszukiwanie w tej tabeli zajmuje średnio 10 milisekund. Dzieje się tak, ponieważ zazwyczaj będziemy musieli przejść przez chain_length/2 redukcje, zanim znajdziemy łańcuch zawierający hash. Na przykład może być konieczne wykonanie 3000 redukcji na hashu, zanim znajdziemy wartość w tabeli. Następnie musimy powtórzyć ten łańcuch od początku, aż znajdziemy pasującą wartość. Gdybyśmy tylko musieli zrobić 3000, aby znaleźć to w naszej tabeli, to musimy zrobić 7000 redukcji od początku, aby dostać się do właściwego punktu w łańcuchu. Zasadniczo wykonujemy tyle operacji, patrząc w górę, co podczas generowania pojedynczego łańcucha. Dlatego czas wyszukiwania wynosi 10 000 mikrosekund, czyli dziesięć milisekund (lub centisekundę, jeśli wolisz).

Wymagania dotyczące pamięci

Jeśli chcesz utworzyć pełną, szybką tabelę wyszukiwania dla funkcji skrótu, nawet MD5, „nadal potrzebujesz stu miliardów miliardów terabajtów pamięci. To” nie są zbyt pomocne. Ale co, jeśli chcemy objąć tylko hasła małymi literami do 10 znaków?

Jeśli chcemy spędzić co najwyżej 30 sekund na szukaniu hasha i zakładając, że potrzebujemy 1 mikrosekundę (milionową sekundy) na hash + skróć cykl, wtedy możemy mieć długość łańcucha: 1 million × 30 = 30 milionów. Istnieje 26 ¹⁰ (lub 10 ¹⁴ ) haseł małymi literami po 10 znaków, a każdy łańcuch obejmuje 30 milionów wartości. To daje nam 4 miliony łańcuchów. Wiemy, że każdy łańcuch ma zapisaną tylko wartość początkową i końcową, a każda z nich ma 10 znaków. Tak więc 2 × 10 × 4 million = 76 MiB danych.

Generowanie tabeli przez iterację wszystkich 10-znakowych haseł zajmuje dużo czasu: 30 sekund na łańcuch, razy 4 miliony łańcuchów to około 91 lat. Takim stołem zainteresowałoby się jednak wiele osób, więc łączenie 1092 procesorów (= 91 × 12) zajmuje tylko 1 miesiąc. To pokazuje, jak mała może być taka tabela w porównaniu z obszarem haseł, który obejmuje: wyszukiwanie zajmuje tylko 30 sekund i musisz przechowywać tylko 76MiB danych.

Wniosek

Tęczowe tabele mogą być uważane za kompromis czasowo-pamięciowy : przechowuje się tylko niewielką część tabeli i odzyskuje ją poprzez dodatkowe obliczenia w czasie wyszukiwania. Jest to jeden z powodów, dla których sole, a raczej dobry algorytm przechowywania haseł, taki jak Scrypt lub Argon2, są ważne, aby zapewnić bezpieczeństwo haseł.Tęczowa tabela może odzyskać zasolone hasło tylko wtedy, gdy tabela zawiera wpis dostatecznie duży, aby pomieścić zarówno sól, jak i hasło, co byłoby wyjątkowo nieefektywne i przeczyło całemu celowi.

Zauważ, że podobnie jest z szyfrowaniem: kiedy ludzie szyfrują pliki hasłem, można zbudować tęczową tabelę, aby złamać pliki. Powiedzmy, że oprogramowanie używa AES, a pierwszy blok pliku powinien odszyfrować, aby „poprawić hasło” za pomocą hasła dostarczonego przez użytkownika, a następnie tablica tęczowa użyje AES zamiast funkcji skrótu.

Za każdym razem, gdy masz do czynienia z hasłem (sekretem o nieznanej sile, a zwłaszcza jeśli użytkownik może go ponownie użyć), zawsze przepuszczaj je przez odpowiedni (powolny) algorytm przechowywania haseł, aby uczynić go wolnym i niepowtarzalnym do złamania. >

Komentarze

• Dobre wyjaśnienie. Jeśli dobrze to zrozumiałem, siła tabel tęczowych polega na dobrej funkcji redukcyjnej, prawda? Jak wymyślić dobry? I jak uniknąć kolizji dla wszystkich kandydatów we wszystkich łańcuchach?
• @ Kyu96 Dobre pytania! Nie ' nie znam odpowiedzi, ale byłbym zainteresowany, gdybyś ją znalazł. Ta strona dotyczy tylko ogólnego pytania, czym jest tęczowa tabela, a nie szczegółów, takich jak projektowanie algorytmu. Powinieneś otworzyć nowe pytanie , ale ta witryna dotyczy ” ochrony zasobów przed zagrożeniami cyfrowymi ” (iirc ). Myślę, że byłoby to na temat naszej siostrzanej witryny, crypto.stackexchange.com , czyli około ” matematyka i właściwości systemów kryptograficznych, ich analiza (” kryptoanaliza „) i tematy pomocnicze, które zazwyczaj składają się na kryptologię, takie jak liczby generacji. ”