Rainbow tables tajemství zbavené

Zdroj: SOOM.cz [ISSN 1804-7270]
Autor: .cCuMiNn.
Datum: 1.2.2015
Hodnocení/Hlasovalo: 1.47/96

S duhovými tabulkami nebo-li Rainbow tables se dnes již střetáváme naprosto běžně. Každý tak dokáže říci, k čemu tyto tabulky slouží a jak je lze použít. Málokdo už ovšem ví, jak jsou tyto tabulky ve skutečnosti generovány, jak jsou uloženy, a jak jsou nakonec aplikovány při louskání hashů. Nebude jistě od věci si tuto teorii blíže představit.

Zažité vnímání Rainbow tables je takové, že jde o tabulku s vygenerovanými páry heslo / hash pro všechny možné kombinace z požadované množiny znaků se zadanou délkou hesel. Kolik by v takové tabulce muselo být řádků, zjistíme snadno ze vzorce množina^délka_hesla. Pro čtyřznaková hesla tvořená pouze znaky malé abecedy a..z by řádků bylo 26^3 = 17.576. Počet kombinací označujeme výrazem keyspace.

Malý úryvek z takové tabulky by mohl vypadat například takto:

V případě požadavku na prolomení hashe aca19aa546644a82dd3f5fb3d3f7a17f bychom se jednoduše zeptali této tabulky a téměř okamžitě bychom dostali odpovídající heslo aaba. Zní to logicky, ale pojďme si nyní vzít příklad devítimístných hesel tvořených z písmen malé i velké abecedy a čísel. Jak velký by byl její keyspace, a kolik řádků by tedy měla výsledná tabulka? Přichází čas na trochu počítání. Možných variací máme 62^9 = 13.537.086.546.263.552, což je i odpovídající počet řádků výsledné tabulky. Pokud bychom takovou tabulku chtěli uložit do textového souboru, potřebovali bychom pro každý řádek 7 bytů na uložení hesla a budeme-li se bavit o hashovací funkci MD5 pak i dalších 32 bytů pro uložení hashe (ve skutečnosti je MD5 tvořena pouze 16ti byty, ale pro zjednodušení, zůstaneme u ukládání v txt podobě). Po aplikování jednoduché matematiky nám vychází velikost výsledné tabulky 13.537.086.546.263.552 * (7+32) = 527.946.375.304.278.528 bytů, tedy 480.164 TB. Rainbow tabulku, která obsahuje všechna mixalpha-numeric hesla do délky 9ti znaků si ale můžeme stáhnout ze stránek https://www.freerainbowtables.com/tables2/ o velikosti pouhého jednoho terabytu. Námi vypočtené hodnoty tedy vychází cca 500.000x větší, než jaká je velikost tabulky, kterou si můžeme stáhnout. Jak je to možné, a jak to s těmi Rainbow tables tedy ve skutečnosti je?

Rainbow tabulky nemají a přesto mají pouze dva sloupce

Příklad tabulky, který jsme si uvedli výše, obsahoval pouze dva sloupce obsahující kombinaci hesel a odpovídajících hashů. Toto by sice mohla být také Rainbow tabulka, ale dala by se použít pouze na velice krátká hesla. Tabulku o dvou sloupcích pro devítimístná hesla bychom totiž asi těžko někam uložili, viz. náš předchozí výpočet. Pro lepší pochopení následujícího textu budeme pro začátek vše hodně zjednodušovat. Začneme například tím, že budeme předpokládat Rainbow table čtyřznakových hesel tvořených pouze z písmen velké abecedy, kde i hashe budou pouze čtyřznakové ze stejné množiny znaků. Taková tabulka by vypadala takto:

Z této tabulky vyplývá, že hashe se musí dříve nebo později objevit nejen v pravém sloupci, ale i ve sloupci levém, který obsahuje všechny variace čtyřznakových řetězců. Proto se dá říci, že takto vypadající hash může být nejenom hashem, ale může být současně i heslem.

Pojďme si tedy vytvořit tabulku o více sloupcích, kde každý další sloupec je vytvořen zahashováním hesla z předchozího sloupce:

Vysvětlení: Zahashováním hesla AAAA nám vznikne hash VODA, který použijeme jako heslo a znovu jej zahashujeme. Zahashováním hesla VODA nám vznikne hash NERV, který opět použijeme jako heslo a po zahashování dostáváme hash PUSA. Stejně budeme pokračovat až na konec řádku, a celý postup budeme opakovat i pro všechny řádky tabulky.

Co jsme tím získali? Zatím to vypadá, že nic, ale ve skutečnosti nám bude stačit, když si ponecháme pouze první a poslední sloupec a všechny vnitřní sloupce (kterých může být i desetitisíce) vyhodíme. Dovůdem, proč můžeme vnitřní sloupce vyhodit, je skutečnost, že jsme schopni si tyto sloupce kdykoliv dopočítat. Po tomto vypuštění získáme tabulku, která bude vypadat takto:

Vyhledáváme v rainbow tables

Nyní si představte, že se vám do ruky dostal hash KROV a vy se budete snažit najít v tabulce odpovídající heslo. K dispozici máme následující Rainbow tabulku, o které víme, že z ní byly vypuštěny 4 sloupce.

Postup při vyhledávání bude následující:

Redukční funkce

Nyní si patrně říkáte, co to tu plácám za nesmysly. Vždyť je každému jasné, že hashe nejsou čtyřznakové, a že jsou tvořeny z úplně jiných znaků, než které jsme v naší tabulce používali. Máte samozřejmě pravdu, a abychom vše uvedli na pravou míru, budeme si muset říci něco o redukčních funkcích. Ty slouží právě k tomu, aby převedly skutečný hash na hash, který svou délkou a množinou použitých znaků odpovídá požadovanému tvaru hesel.

Při generování tabulky tedy ve skutečnosti budeme postupovat takto (stále zjednodušeno):

Tak už je vám jasné, jak se Rainbow tabulka generuje? Upozorňuji, že jsem pro lepší pochopení problematiky celý postup zjednodušil. Ve skutečnosti jsou redukční funkce mnohem složitější.

HF – hashovací funkce
RF – redukční funkce

Kde vzaly Rainbow tabulky svůj název

Podíváme-li se nyní znovu na tabulku, kterou jsem již jednou použil dříve, můžete si v ní všimnout kolize u hashů KOLO nebo SOOM.

Například hash SOOM vznikl jednou z hesla MOTO a podruhé z hesla NOHA. Na tom není nic neobvyklého a ve skutečnosti se v Rainbow tabulkách s podobnými kolizemi střetneme hodně často. Je zde ovšem jeden problém, který těmito kolizemi vzniká a to ten, že se po kolizi již opakuje veškerý obsah všech následných sloupců až do konce řádku. V uvedené tabulce tedy najdete 2x nejenom heslo SOOM, ale i DOLY, KAVA a RUZE. Když si uvědomíme, že sloupců může mít Rainbow tabulka i desetitisíce, pak bychom zbytečně prováděli desetitisíce výpočtů opakovaně, a tím bychom zbytečně plýtvali výpočetním výkonem. Ve skutečnosti je tedy v každém sloupci použita jiná redukční funkce, a tím pádem nám jednou z hesla SOOM vznikne DOLY, ale v jiném sloupci nám použití jiné redukční funkce vytvoří ze stejného hesla slovo SLZA.

V tabulce jsem se snažil různými barvami naznačit použití odlišných redukčních funkcí v jednotlivých sloupcích. Toto barevné rozlišení nám přitom vytvořilo i pěknou duhu, čímž jsme se dostali i k tomu, kde Rainbow tables získaly svůj název.

Dva extrémy

Pokud jste při čtení textu dávali dobrý pozor, možná vám došlo, že tabulka o pouhých dvou sloupcích ze samého začátku článku, byla extrémem Rainbow tabulky, která byla exterémně dlouhá, ale současně bylo i extrémně rychlé vyhledávání v ní. Během čtení vás ale mohl napadnou i opačný extrém - tedy Rainbow tabulka o miliardách sloupců, která by ve výsledku vypadala takto:

Tato tabulka zabere na disku pouze několik bytů, ale přesto obsahuje ve vypuštěných sloupcích všechna čtyřznaková hesla. Extrémní ovšem v tomto případě bude i čas, který budeme potřebovat pro nalezení odpovídajícího hesla. Nejprve totiž budeme muset například mnohamilionkrát zahashovat náš hash, který hledáme, abychom se dostali k hashi NUSE, a následně budeme muset mnohamilionkrát zahashovat heslo AAAA, abychom se dostali před námi hledaný hash a získali tak požadované heslo. Ve výsledku bude vyhledávání v této tabulce díky redukčním funkcím mnohem pomalejší, než kdybychom se snažili o prolomení stejného hashe brutte force metodou.

Máme zde tedy dva extrémy:

  • 1) Velice dlouhé tabulky o málo sloupcích, které ovšem zaberou hodně místa na disku, ale hledání v nich je velmi rychlé.
  • 2) Velice široké tabulky, které na disku zabírají minimální místo, ale vyhledávání je v nich časově nesmírně náročné.
  • Který z extrémů zvolit? Odpověď na tuto otázku je jednoduchá: Ani jeden z nich. Při tvorbě Rainbow tabulek budeme sahat ke kompromisu. Budeme se snažit vytvořit tak vysokou tabulku, aby se nám vešla na disk, a současně tak širokou, abychom v ní byli schopni v rozumném čase vyhledávat.

    Winrtgen

    Snad mě uživatelé systému Linux neukamenují, když v praktické části zmíním windowsovský nástroj Winrtgen, jenž je součástí instalace známého multifunkčního nástroje Cain & Abel. Tento nástroj vám pomůže nejen při vytváření vlastních Rainbow tabulek, ale hlavně si pomocí něj můžete snadno vyzkoušet hledání vhodného kompromisu mezi výškou a šířkou Rainbow tabulky.

    Pokud si budete s hledáním vhodného kompromisu chvíli hrát, zjistíte, že na vašem hardwaru budou reálně použitelné tabulky do maximální velikosti 9 až 10 znaků. Pro delší hesla nebudete mít s největší pravděpodobností dostatečně velké úložiště, nebo nebudete mít ve vašem životě dostatek času, abyste se hledaného hesla dočkali.

    Z uvedeného vyplývá, že Rainbows tables nejsou všemocné, a pokud uživatelé použijí dostatečně dlouhá a silná hesla, tak i takový zázrak, kterým jsou duhové tabulky, bude naprosto bezbranný.