it-swarm-eu.dev

jak dlouho trvá vytvoření tabulek Rainbow?

Četl jsem o tabulkách Rainbow, protože si myslím, že jsou docela zajímavé, protože jsou ve skutečnosti docela jednoduchý koncept.

Každopádně jsem přemýšlel, byl někdo skutečně zapojen do jeho výroby? Jak je to možné? Nechápu, jak je možné vygenerovat každou kombinaci každé postavy.

Vyloučíme-li speciální znaky, je jich tolik.

ABCDEFGHIJKLMNOPQRSTUVWXYZ abcdefghijklmnopqrstuvwxyz 1234567890

Zní to, jako by bylo 26 + 26 + 10 = 62 znaků

To znamená, že heslo délky 8 má 62 ^ 8 kombinací.

což se rovná 218340105584896

To samo zní, jako by trvalo generování. A co když zvýšíme počet znaků na 12 a přidáme speciální znaky (řekněme, že je jich dalších 10 jen tak, že se podíváme na znaky, které získáte stiskem shift - number)?

Dostali bychom 72 ^ 12 = 19408409961765342806016

to je číslo, které je dost velké na to, aby trvalo roky.

27
stickman

Tabulka Rainbow je „jen“ kompaktní reprezentace tabulky předem vypočítaných hashových hodnot. Během konstrukce stolu Rainbow se vyzkouší a hashuje mnoho možných vstupů. Každý vstup, který se objevil během konstrukce tabulky, bude s touto tabulkou úspěšně napaden a žádný jiný. Hodnocení hash soustředí většinu nákladů na budování stolu.

V podstatě tedy náklady na sestavení tabulky Rainbow, která může invertovat [~ # ~] n [~ # ~] hesla, jsou zhruba rovnocenné nákladům o vyzkoušení těchto [~ # ~] n [~ # ~] hesel pomocí hashovací funkce - bod tabulky Rainbow je tím, že ji postavíte jednou a poté jej lze použít k rozbití několika hesel. (Abych byl přesný, v důsledku řetězových kolizí během konstrukce stolu jsou náklady ve skutečnosti blíže 1,7 * N , ale teď to ignorujeme. )

S SHA-1 jsem jednou zažil nějaké zkušenosti. Jednoduché hashování heslem pomocí SHA-1 má náklady na zpracování jediného „bloku“ (SHA-1, jako MD5, zpracovává data 64-bajtovými bloky), což vyžaduje asi 900 32bitových logických nebo aritmetických operací. Optimalizovaná implementace na procesoru Intel Core2 x86 to dokáže za zhruba 500 hodinových cyklů. Útoky hesly (ať už přímo nebo pro konstrukci tabulky Rainbow, na tom nezáleží) jsou však vysoce paralelní úlohou, takže lze použít instrukce SSE2, které nabízejí 128bitové registry, a kde může provádět jeden operační kód čtyři 32bitové operace současně. SSE2 má k dispozici méně druhů operací (zejména nenabízí rotace, pouze řazení), takže počet operací se zvyšuje na přibližně 1200; ale za určitých podmínek jednotka SSE2 provede několik opcod současně. Takže skončíme s 800 hodinovými cykly, pro čtyři instance SHA-1 paralelně. Sečteno a podtrženo: můj počítač je Intel Core2 Q6600 se čtyřmi jádry běžícími na 2,4 GHz. Každé jádro může spustit moji implementaci SSE2, což má za následek zhruba 48 milionů hesel za sekundu.

Mám také příliš malou grafickou kartu Nvidia a GPU může spouštět libovolný kód prostřednictvím CUDA . Toto je 9800 GTX +, se 128 jádry běžícími na 1,84 GHz. Každé jádro může provádět jednu 32bitovou operaci za cyklus (existuje vysoká latence, ale díky vysoké paralelizaci lze tuto propustnost pro jednu instrukci na cyklus zachovat). Jádra neví o rotacích, takže každý kód použije 1200 hodinových cyklů na hashované heslo. Celkový výkon je 160 milionů hashovacích hesel za sekundu.

Můj počítač a grafická karta jsou z počátku roku 2009 a nejsou špičkové. Dnes lze najít za několik stovek dolarů GPU, která bude hashovat hesla třikrát rychleji než moje 9800 GTX +. Předpokládejme tedy, že útočník se společným počítačem (který stojí méně než 1 000 $) dokáže hashovat půl miliardy hesel za sekundu.

Při této rychlosti jsou všechna hesla s 8 alfanumerickými znaky (velká a malá písmena a číslice) procházena přibližně 5 dní . S 1 000 $ PC. Pokud používáte MD5, věci jsou asi o 30% rychlejší (MD5 používá o něco méně operací než SHA-1). Dobrá schémata hašování hesel však nepoužívají jednoduché hašování hašování: používají iterované hašování s, řekněme, 2000 vnořených hašovacích vyvolávání: to násobí náklady na útočníka stejným faktorem 2000 (takže se „5 dní“ změní na asi 28 roky, doslova "věky", jak jste to řekli).

30
Thomas Pornin

Jak dlouho trvá vytvoření tabulky Rainbow pro velmi jednoduchý hash pomocí jediné iterace? Trvá to jednu hodinu! Nebo méně, pokud chcete.

I když výše uvedené odpovědi jsou zcela správné, existuje jeden důležitý vývoj, o kterém se nezmiňují. Amazon EC2 a další poskytovatelé serverů typu „cloud computing“

Dnes mohou všichni s kreditní kartou jít na aws.Amazon.com a zařazovat hrstka EC2 spotových instancí za méně než sto dolarů. Nebo pokud máte k dispozici dobrý kód CUDA, pronajměte si 50 dražších instancí Amazonu „Cluster GPU“ se dvěma grafickými procesory NVIDIA Tesla M2050.

(Trochu jako letecké společnosti, Amazon rozlišil ceny. Pokud potřebujete konkrétní server EC2 s garantovanou dostupností, ceny jsou vyšší. Například můžete získat instanci „Hi-CPU Large“ s 8 virtuálními jádry za 0,68 USD za hodinu . Pokud jste ochotni koupit ve stejné době jako povolení nadměrného zásobování v době mimo provoz, můžete si to koupit se slevou 40% - 50% .)

Vytváření duhových tabulek lze provádět paralelně s lineárním zvýšením výkonu, tj. Se 100 počítači, které pracují, je 100krát rychlejší než jediný počítač.

Amazon vám neúčtuje poplatky za instanci, účtuje se za hodinu instancí. Provoz 1000 serverů po dobu jednu hodinu stojí stejné jako jeden server za 1 000 hodin.

Paralelní povaha vytváření tabulek Rainbow, braná společně se službami, jako je Amazon EC2, znamená, že již neexistuje otázka „jak dlouho to trvá“. Existuje „kolik jste ochotni zaplatit, abyste to dostali rychle, versus platíte méně a dostáváte to za pár dní?“. Rozdíl v ceně a čase vychází hlavně z cenového rozlišení Amazonu mezi „běžnými“ případy EC2 oproti levnějšími „okamžitými případy“.

18
Jesper M

Pomocí jednoduchého testovacího běhu 26 ^ 5 jsem byl schopen vygenerovat ascii hex tabulku v Ruby, která generovala 228488 výstupů MD5 za sekundu. Všech 11881376 záznamů trvalo 52 sekund na mém 1,5letém Core i7. Pokud bych nevylepšil svůj program, očekával bych, že to bude trvat 26 týdnů, aby se vygeneroval váš seznam 62 ^ 8.

Pravděpodobně bych mohl vylepšit svůj program spuštěním osmi samostatných programů, z nichž jeden na hyperthread, k rozdělení problémového prostoru. Pokud by každý program uložil výstup na svůj vlastní disk, nekonkuroval by o IO= šířka pásma). Očekával bych čtyřnásobné až šesté zrychlení ve srovnání s mým hloupým jednozávitovým programem pro 4-6. Kdybych měl přepsat v C, mohl bych očekávat další faktor urychlení 1,5. (Možná více? Na jedné straně je to jednoduchý program, na druhé straně, pole C o délce 13 bajtů, upravené za běhu, pravděpodobně bude běžet v mnohem méně paměti a samozřejmě žádná kolekce odpadu ve srovnání s vytvářením a ničením řetězcových objektů Ruby).

Očekával bych odpolední práci a pár set dolarů nového vybavení by mi umožnilo dokončit 62 ^ 8 tabulek dva týdny na komoditním hardwaru.

A určitě nikdo nepoužívá jednorázový MD5 na hesla; jen mějte moje konečné výsledky, jakkoli je vaše jednosměrná hash mnohem dražší než MD5. :)

6
sarnold

Podívejte se na výpočty hašovací rychlosti bitcoinové sítě na Jak bezpečně hashovat hesla? - IT Security za to, co určují lidé s modernějšími GPU kartami, pokud jde o hrubé hašování. Komunita běží začátkem července 2011 rychlostí 11 Thash/s (11 * 10 ^ 12 hash/s) ....

1
nealmcb