Autor: .cCuMiNn. | 1.2.2015 |
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?
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:
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í:
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):
| 2b | 6c | 79| 34 |2c | 50 | ac | 0f | c4 | 49 | 11 | ae | 2f | 70 | 19 | 09 |
| 2b | 6c | 79| 34 |
2b -> 43 6c -> 108 79 -> 121 34 -> 52
43 % 26 = 17 108 % 26 = 04 121 % 26 = 17 52 % 26 = 00
17 = R 04 = E 17 = R 00 = A
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ší.
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.
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:
Máme zde tedy dva extrémy:
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.
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ý.