Čo sú rainbow tables a prečo sa dnes už takmer nepoužívajú
Rainbow table je predpočítaná štruktúra, ktorá umožňuje k danému hashu nájsť pôvodné heslo rýchlejšie, než keby ste všetky možnosti počítali odznova. Metódu opísal Philippe Oechslin v roku 2003 a nadviazal ňou na staršiu prácu Martina Hellmana o kompromise medzi časom a pamäťou.
Ako to funguje
Naivný prístup by znamenal uložiť si dvojicu heslo a jeho hash pre všetky možné heslá. To sa nedá, lebo taká tabuľka by mala nepredstaviteľnú veľkosť. Rainbow table preto neukladá všetky dvojice, ale len začiatok a koniec takzvaných reťazcov.
Reťazec vznikne tak, že sa z hesla vypočíta hash, z hashu sa redukčnou funkciou vyrobí ďalšie možné heslo, z neho zase hash, a tak dokola niekoľko tisíc krát. Uloží sa len prvé heslo a posledný výsledok. Pri hľadaní sa postup opakuje a hľadá sa zhoda s uloženými koncami. Keď sa nájde, celý reťazec sa prepočíta od začiatku a heslo z neho vypadne.
Slovo rainbow v názve pochádza z toho, že v každom kroku sa používa iná redukčná funkcia. Tým sa obmedzuje problém starších metód, kde sa reťazce často zlievali do seba a tabuľka strácala účinnosť.
Čo ich zabilo
Dve veci, a ani jedna z nich nie je zložitá.
Soľ. Ak si služba pri každom hesle vygeneruje náhodný reťazec, pripojí ho k heslu a až výsledok zahashuje, predpočítaná tabuľka stráca zmysel. Útočník by potreboval samostatnú tabuľku pre každú soľ, teda pre každého používateľa zvlášť. Náklad na prípravu tabuliek sa tým znásobí počtom účtov a celá výhoda predpočítania zmizne. Solenie je dnes súčasťou každej rozumnej knižnice na prácu s heslami a programátor ho spravidla ani nemusí riešiť sám.
Grafické karty. Rainbow tables riešili problém, že počítanie hashov je pomalé a pamäť je lacná. Od roku 2010 sa tento pomer obrátil. Moderná grafická karta spočíta pri rýchlych algoritmoch desiatky miliárd hashov za sekundu, takže útok hrubou silou alebo slovníkom je často rýchlejší než práca s terabajtovou tabuľkou na disku.
Kde sa ešte objavia
V praxi narazíte na predpočítané tabuľky najmä pri starých systémoch, ktoré heslá nesolili. Typickým príkladom sú staršie verzie Windows s hashom LM a NTLM bez soli, kde sa tabuľky používali na prelomenie hesla z odchytenej databázy. Pri systémoch, ktoré vznikli po roku 2010, ide skôr o historickú kuriozitu.
Čo si z toho odniesť
Ak prevádzkujete službu, ktorá ukladá heslá, nepočítajte hash sami. Použite hotovú funkciu navrhnutú presne na tento účel, ktorá soľ aj počet iterácií rieši za vás. Aktuálne odporúčanie smeruje k argon2id, prípadne k bcryptu alebo scryptu, ktoré sú v praxi rozšírenejšie a rovnako obstoja.
Ako používateľ z toho máte jedno praktické ponaučenie: o tom, ako je vaše heslo uložené, nerozhodujete vy. Rozhodujete o tom, či sa to isté heslo dá použiť aj inde. Viac v článku Ako dlho trvá prelomiť heslo.
Časté otázky
Fungujú rainbow tables ešte dnes?
Len proti systémom, ktoré heslá nesolia. Typickým príkladom sú staršie hashe LM a NTLM vo Windows. Pri službách, ktoré vznikli po roku 2010, ide o historickú kuriozitu.
Čo presne je soľ?
Náhodný reťazec, ktorý sa pripojí ku každému heslu pred výpočtom hashu. Útočník by potreboval samostatnú tabuľku pre každého používateľa, čím sa výhoda predpočítania stráca.
Aký algoritmus použiť na ukladanie hesiel?
Funkciu navrhnutú priamo na tento účel, ktorá soľ aj počet iterácií rieši za vás. OWASP odporúča argon2id, prípadne bcrypt alebo scrypt.