Narozeninový útok

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 15. prosince 2015; kontroly vyžadují 67 úprav .

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 .

Pochopení problému

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 %. $1-(364/365)^{23}$ $1-365!/((365-n)!\cdot 365^{n})$

Matematika

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. $h$ $h$

Nechť je hashovací funkce . Narozeninový útok je úspěšný, pokud existuje takový pár $h$ $x_{1}\neq x_{2}$ $h(x_{1})=h(x_{2}).$

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] . $h(x)$ $N$ $N$ $x_{1}\neq x_{2},$ $h(x_{1})=h(x_{2}),$ $1{,}25{\sqrt {N))$ $n$ $2^{n/2},$ $2^{{n}}$

Nechť je pravděpodobnost, že alespoň dva lidé ve skupině lidí ( ) mají stejné narozeniny. $P(n)$ $n$ $n<N=365$

P(n)

1-1\cdot \left(1-{\frac {1}{N}}\right)\cdot \left(1-{\frac {2}{N}}\right)\cdot .. .\cdot \left(1-{\frac {n-1}{N}}\right)=1-\prod _{i=0}^{n-1}\ \left(1-{\frac { i}{N}}\vpravo).

Z prvních dvou členů expanze do Taylorovy řady funkce pro , $\displaystyle e^{x}=1+{\dfrac {x}{1!}}+{\dfrac {x^{2}}{2!}}+{\dfrac {x^{3} }{3!}}+\cdots ,$ $|x|\ll 1$ $e^{x}\cca 1+x.$ $\left(1-{\frac {i}{N))\right)$ ${e}^{-i/N},$

P(n)\cca 1-\prod _{i=0}^{n-1}\ {e}^{-i/N}=1-\exp \sum _{i=0}^ {n-1}(-i/N)=1-{e}^{-n(n-1)/2N}\cca 1-{e}^{-{\frac {n^{2}}{ 2N}}}.

Pojďme najít takové číslo $n$ $P(n)\geq {\frac {1}{2)).$

{\frac {1}{2}}\geq {e}^{-{\frac {n^{2}}{2N}}}.

Tudíž,

n\geq {\sqrt {2\ln 2\cdot N}}\cca 1,177{\sqrt {N}}\cca 23

[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)
bitů	Možné výstupy (N)	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

Tabulka ukazuje počet hashů potřebných k dosažení dané pravděpodobnosti úspěchu za předpokladu, že všechny hashe jsou stejně pravděpodobné. Pro srovnání,

n(P),

10 −18 až 10 −15 je neopravitelná bitová chybovost typického pevného disku [3] . Teoreticky by hashe MD5 nebo UUID 128 bitů měly zůstat v tomto rozsahu až do přibližně 820 miliard dokumentů, i když jejich možné výsledky jsou mnohem větší.

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.

Citlivost digitálního podpisu

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 ) $2^{n}$ $2n$

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) .

BIND narozeninový útok

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). ${\frac {N}{65535}}$

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]

P(n)=1-{e}^{-{\frac {n^{2}}{2N}}}.

Jednoduchá aproximace

Dobrým pravidlem , které lze použít pro rychlé duševní posouzení , je vztah

P(n)\cca {n^{2} \over 2N},

což lze také napsat jako

{\displaystyle N\cca {n^{2} \over 2P(n)))

nebo

n\cca {\sqrt {2N\times P(n))).

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 $N=2^{32}$ $P=10^{-6}\cca 2^{-20}$

n\cca {\sqrt {2\times 2^{32}\times 2^{-20}}}={\sqrt {2^{1+32-20}}}={\sqrt {2 ^{13}}}=2^{6{,}5}\cca 90{,}5,

která se blíží správné odpovědi 93.

Příklady

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] . $2^{32}$

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] . $2^{16}$

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. $2^{{n{/2}}$

Poznámky

↑ 1 2 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein Úvod do algoritmů, třetí vydání, str. 130-133
↑ Bukhantsov A. D., Druzhkova I. V. O modifikaci algoritmu MD5 // Belgorod State National Research University, 2016, str. 176.
↑ Gray, Jim & van Ingen, Catharine (25. ledna 2007), Empirical Measurements of Disk Failure Rate and Error Rate, arΧiv : cs/0701166 .
↑ Joe Stewart , DNS Cache Poisoning, str. 4-5.
↑ 1 2 Babenko L. K., Ischukova E. A. , Analýza symetrických kryptosystémů, str. 146.

Literatura

Mihir Bellare, Tadayoshi Kohno : Rovnováha hašovacích funkcí a její dopad na narozeninové útoky. EUROCRYPT 2004: str. 401-418
Don Coppersmith : Another Birthday Attack, Proceeding CRYPTO '85 Advances in Cryptology str. 14-17