Co jsou duhové stoly a jak se používají?

Duhové tabulky jsou obvykle zaměňovány s další, jednodušší technika, která využívá výpočetní čas torage tradeoff in password recover: hash tables.

Hašovací tabulky jsou vytvořeny hašováním každého slova ve slovníku hesel. Páry hash hesla jsou uloženy v tabulce seřazené podle hodnoty hash. Chcete-li použít hashovací tabulku, jednoduše vezměte hash a proveďte binární vyhledávání v tabulce, abyste našli původní heslo, pokud je k dispozici.

Duhové tabulky jsou složitější. Konstrukce duhové tabulky vyžaduje dvě věci : funkce hash a funkce redukce. Funkce hash pro danou sadu tabulek duhy se musí shodovat s hashovaným heslem, které chcete obnovit. Funkce redukce musí transformovat hash na něco použitelného jako heslo. Jednoduchá funkce redukce je Base64 zakódujte hash a poté jej zkrátte na určitý počet znaků.

Duhové tabulky jsou vytvořeny z „řetězců“ o určité délce: například 100 000. Chcete-li sestrojit řetězec, vyberte náhodnou počáteční hodnotu. Pak aplikujte funkce hash a redukce na toto semeno a jeho výstup a pokračujte v iteraci 100 000krát. Uloží se pouze semeno a konečná hodnota. Tento postup opakujte, abyste vytvořili tolik řetězců, kolik chcete.

Obnovení heslo pomocí tabulek duhy, hash hesla prochází výše uvedený proces pro stejnou délku: v tomto případě 100 000, ale každý článek v řetězci je zachován. Každý článek v řetězci je porovnán s konečnou hodnotou každého řetězce. Pokud existuje shoda, může být řetězec rekonstruován, přičemž je zachován jak výstup každé hashovací funkce, tak výstup každé redukční funkce. Tento rekonstruovaný řetězec bude obsahovat hash příslušného hesla i heslo, které jej vytvořilo.

Silnou stránkou hash tabulky je, že obnovení hesla je rychlé (binární vyhledávání) a budování osoby hash tabulka si může vybrat, co do ní jde, například 10 000 nejlepších hesel. Slabinou ve srovnání s tabulkami Rainbow Tables je to, že hash tabulky musí ukládat každý pár hash-heslo.

Duhové tabulky mají tu výhodu, že osoba, která tyto tabulky sestavuje, si může vybrat, kolik úložiště je vyžadováno výběrem počtu odkazů v každý řetěz. Čím více odkazů mezi počátkem a konečnou hodnotou, tím více hesel je zachyceno. Jednou slabinou je, že osoba, která buduje řetězce, nevybírá hesla, která zachytí, takže tabulky Rainbow nelze optimalizovat pro běžná hesla. Obnova hesla také zahrnuje výpočet dlouhých řetězců hashů, což z obnovy dělá nákladnou operaci. Čím delší jsou řetězce, tím více hesel je v nich zachyceno, ale je potřeba více času na nalezení hesla uvnitř.

Hash tabulky jsou dobré pro běžná hesla, Rainbow Tables jsou dobré pro náročná hesla. Nejlepším přístupem by bylo obnovit co nejvíce hesel pomocí hašovacích tabulek a / nebo konvenčního prolomení pomocí slovníku nejlepších N hesel. Pro ty, kteří zůstanou, použijte tabulky Duha.

Komentáře

• Panebože, přiznávám, že jsem šokován – diskutuji a vysvětluji tabulky Rainbow všechny po celou dobu se zdá, že jsem byl jedním z “ běžně zmatených „! Úplně bych dal +1 000krát, opravdu jsem se zde naučil něco nového (a myslel jsem si, že znám odpověď). Jsem rád, že jsem tu otázku nakonec položil … Děkuji!
• Ačkoli abych byl konkrétní (nyní, když jsi mi otevřel oči, udělal jsem další průzkum :)), Rainbow Tables se odlišují od Hellman Hash Chains pomocí několik různých redukčních funkcí. Složitější … ale opravdu docela krásný nápad (Ah! Je proto proč jsou ‚ nazývány “ Rainbow “ tabulky?)
• Souhlasím, je to velmi dobré vysvětlení. Ve své odpovědi jsem to jednoduše vysvětlil a také jsem to opravdu vysvětlil špatně tím, že jsem byl jednoduchý.Krása stolů Rainbow spočívá v tom, že neukládají každou hash hodnotu ‚. Chystám se upravit svůj hlas, ale také hlasovat, protože je to určitě lepší vysvětlení.
• Hmm … Ačkoli čím víc o tom přemýšlím, v reálných systémech nejsou duhové tabulky zdaleka tak užitečné jako hash tabulky. Jak jste uvedli, pro běžná hesla jsou hash tabulky mnohem lepší (protože jsou o řád rychlejší a požadavky na velikost slovníku hesel jsou samozřejmě mnohem menší než celý možný rozsah hesel). A kdo ‚ si děláme srandu? Většina hesel spadá do této kategorie, je velmi vzácné (a bude to nějakou dobu) volat RT.
• Bohužel jste mě zde ztratili: “ Chcete-li obnovit heslo pomocí tabulek duhy, heslo prochází výše uvedeným procesem stejné délky. “ Jak může heslo projít procesem, když ‚ není ani známo? Měli jste na mysli hash hesla? Také ‚ je toto: “ Každý odkaz v řetězci je porovnán s konečnou hodnotou každého řetězce. “ Nevidím situaci, kdy by se článek v řetězci shodoval s konečnou hodnotou v řetězci, protože hodnota odkazu by byla neustále hašována a snižována.

Existuje mnoho dobrých vysvětlení, jaké jsou duhové tabulky, toto Jak fungují duhové tabulky je obzvláště dobrý. Velmi dobré vysvětlení má také článek Wikipedie . Pro ještě podrobnější čtení je konečným příspěvkem na toto téma Vytvoření rychlejšího kryptoanalytického kompromisu časové paměti .

Jednoduchým vysvětlením duhových tabulek je, že využívají techniku kompromisu časové paměti. To znamená, že místo braní cílové hodnoty hash a slovníku slov pak hashování každého slova a průběžné porovnávání (přístup hrubou silou pomocí něčeho jako John ), místo toho předem zahašujete všechny hodnoty ve slovníku (v závislosti na velikosti slovníku to může trvat velmi dlouho). Ale jakmile je hotovo, můžete porovnat tolik hashů, kolik chcete, s předem hašovanými hodnotami v duhových tabulkách, což je podstatně rychlejší než výpočet hashů znovu.

Vysvětlení, které jsem zde psal dříve v snaha být krátká byla zavádějící, protože nevysvětlovala použití redukcí, které duhové stoly využívají. Pro lepší vysvětlení, dokud tento bit nepřepíšu, viz @Crunge answer .

Duhové tabulky můžete buď sami vygenerovat pomocí aplikace jako RainbowCrack nebo si je můžete stáhnout ze zdrojů jako The Shmoo Group , Free Rainbow Tables , projekt Ophcrack a mnoho dalších míst podle toho, pro jaký typ hash potřebujete tabulky.

Z důvodu ochrany před útokem založeným na Rainbow Table je nejúčinnější metodou boje zajistit, aby každý hash v systému byl solen . Díky tomu jsou předem vygenerované duhové tabulky k ničemu a znamenalo by to, že by útočník musel vygenerovat vlastní sadu tabulek, které by použil proti cíleným hashům, což by bylo možné, pouze kdyby znal sůl.

Komentáře

• Dále (zvažte úpravy v), pokud pro každé heslo použijete jinou sůl, zaznamenáváte ji nezašifrovanou do databáze, pak napadený by musel pro každý hash vygenerovat vlastní sadu tabulek, která by porazila předmět cvičení – celý bod duhové tabulky je hrubou silou celý prostor hesel a poté získat všechna hesla pro jednu hrubou sílu úsilí; pokud ‚ získáváte pouze jedno heslo na každý duhový stůl, můžete také přímo hrubou silou hash.

Účel a relevance

Duhové tabulky pomáhají rozluštit obtížná hesla, tj. ta, která nelze najít ani ve velkém slovníku. Hesla byla historicky ukládána jako prostý hash v databázích, a právě na to jsou duhové tabulky účinné: vytvořte jednu duhovou tabulku (pomalu) a spusťte proti ní libovolný počet databází plných hashů (rychle).

V dnešní době stále více systémů používá správné algoritmy pro ukládání hesel, jako jsou Bcrypt, Scrypt nebo Argon2. Viz: Jak bezpečně [ukládat] hesla? Tyto algoritmy jsou již není „zranitelný“ vůči duhovým stolům: protože každý hash je jedinečný, i když jsou hesla stejná, duhové tabulky již nefungují.

Proto jsou dnes duhové tabulky nepopulární.I když se něco moderního, jako je Argon2, nepoužívá, vývojáři dnes většinou vědí, že by měli použít alespoň sůl. To již stačí k tomu, aby byl duhový stůl k ničemu.

Jak fungují

Vytvoření tabulky

Představte si, že vytvoříme duhový stůl s pouhými dvěma řetězci, každý o délce 5. Duhový stůl je pro fiktivní hashovací funkci MD48, která má výstup 48 bitů (pouze 12 hexadecimálních znaků). Při vytváření řetězce to vidíme takto:

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 

Začínáme s 0, protože se jedná o první řetězec (pro začátek potřebujeme jen nějakou hodnotu). Když to s MD48 hashujeme, promění se to v cfcd208495d5. Nyní použijeme funkci „zmenšit“, která tento hash v podstatě naformátuje zpět do heslo a nakonec skončíme písmenem „z“. Když to znovu zalomíme, dostaneme fbade9e36a3f, poté ho opět snížíme a dostaneme renjaj820 . Existuje několik dalších cyklů a konečným výsledkem je WLgOSj.

Totéž pro druhý řetězec. Začneme pouze jinou hodnotou a uděláme totéž. To končí 0uUoAD.

Náš kompletní duhový stůl je nyní tento:

WLgOSj => 0 0uUoAD => 1 

To je vše, co musíte uložit.

Hledání hash

Řekněme, že jsme našli hash online, 7668b2810262. Pojďme to prolomit pomocí naší tabulky!

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 

Abychom si s tím mohli pohrát sami, byly výše uvedené příklady vytvořeny pomocí tohoto skriptu Python: https://gist.github.com/lgommans/83cbb74a077742be3b31d33658f65adb

Vlastnosti škálování

Stručně:

• Rychlé vyhledávání znamená větší tabulky za předpokladu, že pokrytí zůstane stejné.
• Lepší pokrytí znamená buď pomalejší vyhledávání, nebo větší tabulky.
• Menší tabulky znamená buď pomalejší vyhledávání, nebo horší pokrytí.

Následující části předpokládají, že čas na hash + snížení je 1 µs, a nedokáže zohlednit kolize. Toto jsou všechna čísla, která slouží jako příklady, nikoli jako přesné hodnoty.

Doba vyhledávání

Pokud operace hash + redukce trvá mikrosekundu, pak by vygenerování tabulky s milionem řetězců a 10 000 redukcemi na řetězec trvalo asi 3 hodiny:
chain_length × chain_count / reductions_per_second / seconds_per_hour
= 10 000 × 1 000 000 / 1 000 000 / 3600 = 2,8 hodiny.

Vyhledávání v této tabulce trvá v průměru 10 milisekund. Je to proto, že obvykle budeme muset projít chain_length/2 redukcemi, než zjistíme, který řetězec obsahuje hash. Například možná budeme muset udělat 3000 redukcí na hash, než najdeme hodnotu, která je v tabulce. Dále musíme tento řetězec znovu provést od začátku, dokud nenajdeme odpovídající hodnotu. Pokud bychom jen museli udělat 3000, abychom to našli v naší tabulce, musíme udělat 7000 redukcí od začátku, abychom se dostali do správného bodu v řetězci. V zásadě děláme tolik operací při vyhledávání, jako při generování jednoho řetězce. Proto je doba vyhledávání 10 000krát za mikrosekundu, což je deset milisekund (nebo centisekundu, pokud chcete).

Požadavky na úložiště

Pokud chcete vytvořit úplnou a rychlou vyhledávací tabulku pro hashovací funkci, dokonce i pro MD5, stále potřebujete sto miliard miliard terabajtů úložiště. To “ není moc užitečné. Ale co když chceme pokrýt pouze malá hesla do 10 znaků?

Pokud chceme strávit maximálně 30 sekund hledáním hodnoty hash a za předpokladu, že potřebujeme 1 mikrosekundu (miliontinu sekundy) na hodnotu hash + snížit cyklus, pak můžeme mít délku řetězce: 1 million × 30 = 30 milionů. Existuje 26 ¹⁰ (nebo 10 ¹⁴ ) možných malých hesel o délce 10 znaků a na řetězec pokryjeme 30 milionů hodnot. Takže nám zbývají 4 miliony řetězů. Víme, že každý řetězec má uloženou pouze počáteční a koncovou hodnotu a že hodnoty mají každý 10 znaků. Takže 2 × 10 × 4 million = 76 MiB dat.

Generování tabulky iterací přes všechna 10místná hesla trvá dlouho: 30 sekund na řetězec, krát 4 miliony řetězců asi 91 let. Spousta lidí by o takovou tabulku měla zájem, takže shromáždění 1092 CPU (= 91 × 12) trvá jen 1 měsíc. To ukazuje, jak malou lze takovou tabulku srovnávat s prostorem hesel, které pokrývá: vyhledávání trvá jen 30 sekund a musíte uložit pouze 76 MB dat.

Závěr

Duhové tabulky mohou být považováno za kompromis časové paměti : jeden uloží pouze malou část tabulky a obnoví ji pomocí nějakého zvláštního výpočtu v době vyhledávání. To je jeden z důvodů, proč jsou soli, nebo spíše dobrý algoritmus pro ukládání hesel, jako je Scrypt nebo Argon2, důležité pro zachování hesla.Duhová tabulka může obnovit solené heslo, pouze pokud tabulka obsahuje záznam dostatečně velký na to, aby obsahoval jak sůl, tak i heslo, což by bylo extrémně neefektivní a marilo celý účel.

Pamatujte, že při šifrování platí podobná věc: když lidé šifrují soubory pomocí hesla, může být vytvořena duhová tabulka, která soubory rozluští. Řekněme, že software používá AES, a první blok souboru by měl dešifrovat na „heslo opravit“ pomocí hesla dodaného uživatelem, pak by duhová tabulka místo hašovací funkce používala AES.

Kdykoli zpracováváte heslo (tajemství neznámé síly, zejména pokud ho uživatel může znovu použít), vždy jej spusťte pomocí vhodného (pomalého) algoritmu pro ukládání hesel, aby bylo prolomení pomalé a jedinečné.

Komentáře

• Dobré vysvětlení. Pokud jsem to správně pochopil, síla duhových stolů spočívá v dobré redukční funkci, že? Jak přijdu s dobrým? A jak se mohu vyhnout kolizím u všech kandidátů napříč řetězci?
• @ Kyu96 Dobré otázky! Neznám ‚ odpověď, ale zajímalo by mě, jestli ji najdete. Tato stránka pojednává pouze o obecné otázce, co je duhová tabulka, nikoli o konkrétních aspektech, jako je návrh algoritmu. Měli byste otevřít novou otázku , ale tento web je o “ ochraně aktiv před digitálními hrozbami “ (iirc ). Myslím, že by to bylo téma pro náš sesterský web crypto.stackexchange.com , který je o “ matematika a vlastnosti kryptografických systémů, jejich analýza (“ kryptoanalýza „) a pomocná témata, která obecně tvoří kryptologii, například náhodné číslo generace. “