Narozeninový útok je název používaný v kryptoanalýze pro metodu prolamování šifer nebo hledání kolizí hashovací funkce na základě narozeninového paradoxu . Podstatou metody je výrazně snížit počet argumentů předávaných hašovací funkci, což je nutné pro detekci kolize, protože pokud hašovací funkce generuje n -bitovou hodnotu, pak počet náhodných argumentů hašovací funkce, pro které při alespoň jedna hašovací kolize bude detekována s vysokou pravděpodobností funkce (to znamená, že existuje alespoň jeden pár stejných hašovacích kódů získaných na různých argumentech) není 2 n , ale pouze asi 2 n /2 .
Zvažte příklad: Budou mít dva lidé ve skupině 23 stejné narozeniny? Jeden rok, kromě přestupných let, má 365 dní, takže existuje 365 různých narozenin, což je mnohem větší počet než 23.
Pokud bychom vybrali konkrétní den, pak pravděpodobnost, že se v daný den narodil alespoň jeden člověk, by byla asi 6,1 %. Pravděpodobnost, že alespoň jeden člověk má stejné narozeniny jako kterýkoli jiný, je však podle vzorce [1] asi 50 % . Pro n = 70 je pravděpodobnost takové shody 99,9 %.
Pro danou hashovací funkci je cílem útoku najít kolizi druhého druhu . K tomu se počítají hodnoty pro náhodně vybrané bloky vstupních dat, dokud nejsou nalezeny dva bloky, které mají stejný hash.
Nechť je hashovací funkce . Narozeninový útok je úspěšný, pokud existuje takový pár
Pokud tedy funkce dává některý z různých výstupů se stejnou pravděpodobností a je dostatečně velká, pak matematické očekávání počtu párů různých argumentů , pro které je . Odhad počtu hašovacích operací pro nalezení kolize ideální kryptografické hašovací funkce s výstupní velikostí bitů se často zapisuje jako a nikoli [2] .
Nechť je pravděpodobnost, že alespoň dva lidé ve skupině lidí ( ) mají stejné narozeniny.
=Z prvních dvou členů expanze do Taylorovy řady funkce pro ,
Pojďme najít takové číslo
Tudíž,
[1] .Pokud je například použit 64bitový hash, existuje přibližně 1,8 × 10 19 různých výstupů. Pokud jsou všechny stejně pravděpodobné (nejlepší případ), pak by ke srážce za použití hrubé síly trvalo „jen“ asi 5 miliard pokusů ( 5,38×109 ) . Další příklady:
bitů | Možné výstupy (N) | Požadovaná pravděpodobnost náhodné kolize (P) | |||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
10 −18 | 10 −15 | 10 −12 | 10 −9 | 10 −6 | 0,1 % | jeden % | 25 % | padesáti % | 75 % | ||
16 | 2 16 (~6,5 x 10 3 ) | <2 | <2 | <2 | <2 | <2 | jedenáct | 36 | 190 | 300 | 430 |
32 | 2 32 (~4,3 × 10 9 ) | <2 | <2 | <2 | 3 | 93 | 2900 | 9300 | 50 000 | 77 000 | 110 000 |
64 | 2 64 (~1,8 × 10 19 ) | 6 | 190 | 6100 | 190 000 | 6 100 000 | 1,9× 108 | 6,1× 108 | 3,3 × 109 | 5,1 x 109 | 7,2 × 109 |
128 | 2128 (~ 3,4 × 1038 ) | 2,6 × 10 10 | 8,2 × 10 11 | 2,6 × 10 13 | 8,2 × 10 14 | 2,6 × 10 16 | 8,3 × 10 17 | 2,6 × 10 18 | 1,4 × 10 19 | 2,2 × 10 19 | 3,1 × 10 19 |
256 | 2256 ( ~ 1,2 × 10 77 ) | 4,8 × 10 29 | 1,5 × 10 31 | 4,8 × 10 32 | 1,5×10 34 | 4,8 × 10 35 | 1,5 × 10 37 | 4,8 × 10 37 | 2,6 × 10 38 | 4,0 × 10 38 | 5,7 × 10 38 |
384 | 2384 (~3,9 × 10115 ) | 8,9 × 10 48 | 2,8 × 10 50 | 8,9 × 1051 | 2,8 × 1053 | 8,9 × 1054 | 2,8 × 1056 | 8,9 × 1056 | 4,8 × 1057 | 7,4× 1057 | 1,0 × 10 58 |
512 | 2512 (~1,3 × 10154 ) | 1,6 × 10 68 | 5,2 × 10 69 | 1,6 × 10 71 | 5,2 × 1072 | 1,6× 1074 | 5,2 × 1075 | 1,6 × 10 76 | 8,8 × 1076 | 1,4 × 10 77 | 1,9 × 10 77 |
Je snadné vidět, že pokud jsou výstupy funkce nerovnoměrně rozloženy, lze kolize nalézt ještě rychleji. Koncept „rovnováhy“ hashovací funkce kvantifikuje odolnost funkce vůči „narozeninovému“ útoku (s použitím nejednotné distribuce klíčů). Určení rovnováhy hašovací funkce však vyžaduje výpočet všech možných vstupů, a proto není proveditelné pro oblíbené hašovací funkce, jako jsou rodiny MD a SHA.
K tomuto útoku může být náchylný například elektronický digitální podpis . Řekněme, že 2 lidé – A a B – chtějí podepsat smlouvu, ale A chce podstrčit B falešnou verzi smlouvy. Poté A sepíše pravou smlouvu a falešnou smlouvu. Dále tím, že provede platné změny, které nemění význam textu (uspořádání čárek, pomlček, odrážek), A dosáhne toho, že obě smlouvy mají stejný hash. Poté A pošle B pravou smlouvu, B ji podepíše a jeho podpis také ukazuje, že podepsal i falešnou smlouvu, protože obě smlouvy mají stejný hash. Abyste se vyhnuli tomuto druhu zranitelnosti, stačí zvětšit délku hash, takže bude výpočetně obtížné najít 2 smlouvy se stejnými hashemi. Zejména je zapotřebí dvojnásobná délka hash, aby byla zajištěna výpočetní složitost srovnatelná s prohledáváním hrubou silou. Jinými slovy, pokud útočník dokáže vypočítat hašovací hodnoty pomocí hrubé síly , začne nacházet hašovací kolize pro všechny haše kratší než trochu. (viz en:Narozeninový útok )
Aby se tomuto útoku zabránilo, lze výstupní délku hašovací funkce použité pro schéma podpisu zvolit dostatečně velkou, aby byl útok „narozeniny“ výpočetně neproveditelný, tj. přibližně dvakrát více bitů, než je potřeba k zabránění konvenčnímu útoku „hrubou silou“ . (úplný výčet) .
DNS je distribuovaný počítačový systém pro získávání informací o . Nejčastěji se používá k získání IP adresy z názvu hostitele (počítače nebo zařízení).
Termín „rekurze“ v DNS označuje chování DNS serveru, kdy server jménem klienta provádí kompletní vyhledávání potřebných informací v celém DNS systému, v případě potřeby s odkazem na jiné DNS servery. V případě „rekurzivního“ dotazu DNS server dotazuje servery (v sestupném pořadí podle úrovně zóny v názvu), dokud nenajde odpověď nebo nezjistí, že doména neexistuje (v praxi vyhledávání začíná od DNS servery nejblíže požadovanému, pokud jsou informace o nich uloženy v mezipaměti a jsou aktuální, server se nemusí dotazovat na jiné DNS servery).
V roce 2002 Wagner ze Sacramenta zveřejnil doporučení ukazující jeden problém s implementací protokolu DNS společností BIND. Zjistil, že BIND posílal několik simultánních rekurzivních požadavků na stejnou IP adresu.
Útočník odešle dotaz na server DNS oběti. Vybere název domény, který DNS server A nemůže najít ve své mezipaměti, a je nucen předat další DNS server B. Každá výměna oprávnění mezi A a B je ověřena pomocí náhodného TID. Než server DNS A může přijímat pakety odpovědí ze serveru DNS B, útočník odešle N falešných paketů odpovědí na server DNS A. Pokud má jeden z těchto falešných paketů stejné TID jako TID serveru DNS A, server tyto falešné pakety přijme. A jako platné pakety. Skutečná odpověď ze serveru DNS B nebude zpracována serverem DNS A. Útočník tedy může „otrávit“ mezipaměť serveru DNS A, aby namapovala napadenou doménu na adresu IP poskytnutou útočníkem.
Při běžném útoku pošle útočník N falešných odpovědí na jeden požadavek, pravděpodobnost úspěchu je (TID - 16bitové číslo).
Narozeninový útok usnadňuje prolomení protokolu BIND. Útočník odešle velké množství N dotazů na DNS server oběti, všechny se stejným názvem domény. Na N žádostí posíláme N falešných odpovědí . Pravděpodobnost, že útok bude úspěšný, je tedy [4]
Dobrým pravidlem , které lze použít pro rychlé duševní posouzení , je vztah
což lze také napsat jako
nebo
Tato aproximace funguje dobře pro pravděpodobnosti menší nebo rovné 0,5.
Toto aproximační schéma se obzvláště snadno používá při práci s indikátory. Odhadněme například, kolik dokumentů lze zpracovat 32bitovou hašovací funkcí ( ), aby pravděpodobnost kolize nebyla větší než jedna ku milionu ( ). Odhad co největšího počtu dokumentů pro takové stavy je
která se blíží správné odpovědi 93.
Předpokládejme, že k útoku na 64bitovou blokovou šifru potřebuje útočník získat dva páry otevřeného textu/šifrovaného textu, které se liší pouze v nejméně významném bitu. Interpretace tohoto problému z hlediska narozeninového paradoxu vede k závěru, že prostor pouze známých otevřených textů bude s vysokou pravděpodobností obsahovat požadovaný pár [5] .
Jako další příklad zvažte cyklus 64bitové Feistelovy šifry . Předpokládejme, že šifra používá náhodnou funkci F (32 až 32 bitů). Útočník může chtít vědět, kolik otevřených textů potřebuje získat, aby dostal kolizi funkce F . Podle narozeninového paradoxu k tomu musíte protřídit asi otevřené texty [5] .
Jedním z důsledků narozeninového paradoxu je, že pro n - bitovou blokovou šifru lze očekávat opakované výskyty bloku šifrovaného textu s pravděpodobností asi 0,63 za předpokladu, že pouze náhodné otevřené texty jsou zašifrovány na stejném klíči (bez ohledu na velikost klíče). Pokud se v režimu ECB shodují dva bloky šifrovaného textu, musí se shodovat i odpovídající otevřené texty. To znamená, že při známém útoku na šifrovaný text lze z bloků šifrovaného textu odhalit informace o otevřených textech.