Bit-flipping attack

Narozeniny útok je typ kryptografického útoku , který využívá matematiku , které stojí za narozeninám problém v teorii pravděpodobnosti . Tento útok může být použita ke zneužívání komunikaci mezi dvěma nebo více stranami. Útok závisí na vyšší pravděpodobnost kolizí nalezených mezi náhodnými útoku pokusy a pevné stupeň permutací ( škatulek ), jak je popsáno v narozeninovém problému / paradox.

[ upravit překlad ]Pochopení problému

Hlavní článek: Narozeniny problém

Jako příklad, zvažovat scénář, ve kterém učitel s třídou 30 studentů žádá o každého člověka narozeniny, aby se zjistilo, zda nějaké dva studenti mají narozeniny ve stejný den (což odpovídá hash kolize , jak je popsáno níže, pro jednoduchost, ignorovat 29.února). Intuitivně, může tato šance zdát malý.Pokud učitel vybral specifický den (říci 16. září), pak je pravděpodobnost, že alespoň jeden ze studentů narodil na tomto konkrétním den je $1 - (364/365) ^ {30}$ asi 7,9%. Nicméně, je pravděpodobnost, že alespoň jeden ze studentů má stejné narozeniny jako jakékoliv jiné studenta je kolem 70% (podle následujícího vzorce $1-365! / ((365-n)! \ Cdot365 ^ n)$ pro n = 30 ^[ 1 ] ).

[ editovat ]Matematika

Vzhledem k tomu, funkce $F$ , cílem útoku je najít dva různé vstupy $x_ {1}, x_ {2}$ takové, že $f (x_ {1}) = f (x_ {2})$ . Taková dvojice $x_ {1}, x_ {2}$ se nazývá kolize .Použitá metoda pro nalezení kolize je jednoduše vyhodnotit funkci $F$ pro různé vstupní hodnoty, které mohou být vybrány náhodně nebo pseudorandomly dokud není téhož výsledku bylo nalezeno více než jednou. Vzhledem k narozeninám problému, může být tato metoda spíše efektivní. Konkrétně, je-lifunkce $f (x)$ vzdá některý z $H$ různých výstupů se stejnou pravděpodobností a $H$ je dostatečně velký, pak se očekávat, že pro získání pár různé argumenty $x_ {1}$ a $x_ {2}$ s $f (x_ {1}) = f (x_ {2})$ po vyhodnocení funkce asi $1.25 \ sqrt {H}$ různé argumenty v průměru.

Jsme toho názoru, následující experiment. Ze sady H hodnot zvolíme n hodnot rovnoměrně v náhodných tím umožňují opakování. Ať p ( n ; H ) je pravděpodobnost, že během tohoto experimentu je alespoň jedna hodnota vybrán více než jednou. Tato pravděpodobnost lze aproximovat jako

$p (n, H) \ cca 1 - e ^ {-n (n-1) / (2H)} \ cca 1-e ^ {-n ^ 2 / (2H)}, \,$

Nechť n ( p , H ) je nejmenší počet hodnot, které máme na výběr, takové, že pravděpodobnost nalezení kolize je nejméně s. . Převrácením tohoto výrazu nahoře, najdeme následující aproximace

$n (p, H) \ approx \ sqrt {2H \ ln \ frac {1} {1-p}},$

a přiřazení 0,5 pravděpodobnost kolize jsme přijet na

$n (0.5 H) \ approx 1,1774 \ sqrt H. \,$

Nechť Q ( H ), je očekávaný počet hodnot, které musíme zvolit před nalezení první kolize. Toto číslo lze aproximovat

$Q (H) \ approx \ sqrt {\ frac {\ pi} {2}} H.$

Jako příklad lze uvést, pokud 64-bitové hash se používá, je přibližně 1,8 x 10 ¹⁹různé výkony. Pokud jsou všechny stejně pravděpodobné (v nejlepším případě), pak by se "pouze" přibližně 5,1 × 10 ⁹ pokusy generovat kolize pomocí hrubé síly. Tato hodnota se nazývá narozeniny vázán ^[ 2 ] a pro n -bitových kódů by mohl být vypočteny jako 2 ^{n / 2} . ^[ 3 ] Další příklady jsou následující:

Bity	Možné výstupy (zaokrouhleno) (H)	Požadovaný pravděpodobnost náhodného nárazu (zaokrouhleno) (p)
Bity	Možné výstupy (zaokrouhleno) (H)	10 ^-18	10 ^-15	10 ^-12	10 ^-9	10 ^-6	0,1%	1%	25%	50%	75%
16	6,6 × 10 ⁴	2	2	2	2	2	11	36	1,9 × 10 ²	3,0 × 10 ²	4,3 × 10 ²
32	4,3 × 10 ⁹	2	2	2	2.9	93	2,9 × 10 ³	9,3 × 10 ³	5,0 × 10 ⁴	7,7 × 10 ⁴	1,1 × 10 ⁵
64	1,8 × 10 ¹⁹	6.1	1,9 × 10 ²	6,1 × 10 ³	1,9 × 10 ⁵	6,1 × 10 ⁶	1,9 × 10 ⁸	6,1 × 10 ⁸	3,3 × 10 ⁹	5,1 × 10 ⁹	7,2 × 10 ⁹
128	3,4 × 10 ³⁸	2,6 × 10 ¹⁰	8,2 × 10 ¹¹	2,6 × 10 ¹³	8,2 × 10 ¹⁴	2,6 × 10 ¹⁶	8,3 × 10 ¹⁷	2,6 × 10 ¹⁸	1,4 × 10 ¹⁹	2,2 × 10 ¹⁹	3,1 × 10 ¹⁹
256	1,2 × 10 ⁷⁷	4,8 × 10 ²⁹	1,5 × 10 ³¹	4,8 × 10 ³²	1,5 × 10 ³⁴	4,8 × 10 ³⁵	1,5 × 10 ³⁷	4,8 × 10 ³⁷	2,6 × 10 ³⁸	4,0 × 10 ³⁸	5,7 × 10 ³⁸
384	3,9 × 10 ¹¹⁵	8,9 × 10 ⁴⁸	2,8 × 10 ⁵⁰	8,9 × 10 ⁵¹	2,8 × 10 ⁵³	8,9 × 10 ⁵⁴	2,8 × 10 ⁵⁶	8,9 × 10 ⁵⁶	4,8 × 10 ⁵⁷	7,4 × 10 ⁵⁷	1,0 × 10 ⁵⁸
512	1,3 × 10 ¹⁵⁴	1,6 × 10 ⁶⁸	5,2 × 10 ⁶⁹	1,6 × 10 ⁷¹	5,2 × 10 ⁷²	1,6 × 10 ⁷⁴	5,2 × 10 ⁷⁵	1,6 × 10 ⁷⁶	8,8 × 10 ⁷⁶	1,4 × 10 ⁷⁷	1,9 × 10 ⁷⁷

Tabulka ukazuje počet hashes n ( p ) nutná k dosažení daného pravděpodobnost úspěchu, za předpokladu, že všechny hashe jsou stejně pravděpodobně. Pro srovnání, 10 ^-18až 10 ^-15je neopravitelným bitová chybovost typického pevného disku [1] . Teoreticky, MD5 hash neboUUID , je 128 bitů, by měly zůstat v tomto rozsahu až do asi 820 miliard dokumentů, i když její možné výstupy jsou mnohem více.

Je jasné, že v případě, že výstupy funkce jsou nerovnoměrně, pak kolize lze nalézt ještě rychleji. Pojem "rovnováhy" z funkce hash kvantifikuje odpor funkce k narozeninám útoky a umožňuje zranitelnost populárních hash, jako například MD a SHA se odhadnout ( Bellare a Kohno, 2004 ).

Subexpression $\ Ln \ frac {1} {1-p}$ v rovnici pro $n (p, H)$ není počítán přesně pro malé $p$ , když je přímo přeloženy do běžných programovacích jazyků jako log (1 / (1-p)) z důvodu ztráty významu . Když log1p je k dispozici (jako je tomu v ANSI C ), ekvivalentní výraz -log1p (-p) by měl být používán místo toho.^[ 4 ] Pokud se tak neděje, je první sloupec výše uvedené tabulky počítán jako nula, a několik položek v druhém sloupci nemají ani jeden správný významnou číslici.

[ upravit překlad ]Digitální podpis susceptibility

Digitální podpisy mohou být náchylná k narozeninám útoku. Zpráva $m$ je obvykle podepsán tím, že nejprve na počítači $f (m)$ , kde $F$ je šifrovací hash funkce , a pak používat nějaký tajný klíč k podpisu $f (m)$ . Předpokládejme, že Mallory chce přimět Boba do podpisu podvodné smlouvy. Mallory připravuje spravedlivé smlouvu $m$ a podvodné jedno $m '$ . Ona pak najde řadu pozic, kde $m$ mohou být změněny bez změny významu, jako je vkládání čárek, prázdných linek, jeden proti dvěma prostory po větě, nahradí synonyma, atd. Kombinací těchto změn, může si vytvořit obrovský počet variant na $m$ které jsou všechny reálné smlouvy.

Podobným způsobem, Mallory také vytváří velký počet variací na podvodné smlouvy $m '$ . Ona pak aplikuje hash funkci na všechny tyto změny, dokud se najde verzi reálné smlouvy a verzi podvodného smlouvy, která má stejnou hodnotu hash, $f (m) = f (m ')$ . Ona představuje reálnou verzi Bobovi k podpisu. Po Bob podepsal, Mallory má podpis a připojí jej k podvodnému smlouvy. Tento podpis pak "dokazuje", že Bob podepsal smlouvu podvodné.

Pravděpodobnosti mírně lišit od původního narozenin problém, jak získává Mallory ničeho nalezení dvou veletrh nebo dvě podvodných smluv se stejným hash. Malloryho strategie je vytvářet páry jednoho veletrhu a jeden podvodné smlouvy. Rovnice narozenin problém tehdy, pokud $n$ je počet dvojic. Počet hashů Mallory vlastně generuje je $2n$ .

Chcete-li se vyhnout tomuto útoku, může výstup délka hašovací funkce používané pro podpisové schéma být zvolena dostatečně velká, aby narozeniny útok stává výpočetně neproveditelné, tedy asi dvakrát tolik bitů, které jsou zapotřebí, aby se zabránilo obyčejný brute-force útoku .

Pollard se rho algoritmus pro logaritmů je příkladem pro algoritmus pomocí útok narozenin pro výpočet diskrétních logaritmů .

Narozeniny útoky jsou často diskutovány jako potenciální slabost v internetuDomain Name Service systému. ^[ 5 ]