Narozeninový útok - Birthday attack

A narozeninový útok je typ kryptografické Záchvat který využívá matematika za narozeninový problém v teorie pravděpodobnosti. Tento útok lze použít ke zneužití komunikace mezi dvěma nebo více stranami. Útok závisí na vyšší pravděpodobnosti kolize mezi náhodnými pokusy o útok a pevným stupněm obměn (holubí díry ). S narozeninovým útokem je možné najít kolizi a hashovací funkce v ${ textstyle { sqrt {2 ^ {n}}} = 2 ^ {n / 2}}$, s ${ textstyle 2 ^ {n}}$ být klasický odpor obrazu bezpečnostní. Existuje obecný (i když sporný^[1]) Výsledek, že kvantové počítače mohou provádět narozeninové útoky, čímž naruší odolnost proti kolizi ${ textstyle { sqrt [{3}] {2 ^ {n}}} = 2 ^ {n / 3}}$.^[2]

Pochopení problému

Jako příklad zvažte scénář, ve kterém učitel s třídou 30 studentů (n = 30) požádá o narozeniny všech (pro zjednodušení ignorujte přestupné roky ) k určení, zda mají dva studenti stejné narozeniny (odpovídající a hash kolize jak je popsáno dále). Tato šance se může intuitivně zdát malá. Pokud si učitel vybral konkrétní den (řekněme 16. září), pak je šance, že se v daný den narodil alespoň jeden student, ${ displaystyle 1- (364/365) ^ {30}}$, přibližně 7,9%. Protiintuitivně však pravděpodobnost, že alespoň jeden student má stejné narozeniny jako žádný jiný student v kterýkoli den je podle vzorce přibližně 70% (pro n = 30) ${ displaystyle 1 - { frac {365!} {(365-n)! cdot 365 ^ {n}}}}$.^[3]

Matematika

Vzhledem k funkci ${ displaystyle f}$, cílem útoku je najít dva různé vstupy ${ displaystyle x_ {1}, x_ {2}}$ takhle ${ displaystyle f (x_ {1}) = f (x_ {2})}$. Takový pár ${ displaystyle x_ {1}, x_ {2}}$ se nazývá a srážka. Metoda použitá k nalezení kolize je jednoduše vyhodnocení funkce ${ displaystyle f}$ pro různé vstupní hodnoty, které lze zvolit náhodně nebo náhodně, dokud se stejný výsledek nenajde více než jednou. Z důvodu problému s narozeninami může být tato metoda docela efektivní. Konkrétně, pokud a funkce ${ displaystyle f (x)}$ výnosy některého z ${ displaystyle H}$ různé výstupy se stejnou pravděpodobností a ${ displaystyle H}$ je dostatečně velká, pak očekáváme získání dvojice různých argumentů ${ displaystyle x_ {1}}$ a ${ displaystyle x_ {2}}$ s ${ displaystyle f (x_ {1}) = f (x_ {2})}$ po vyhodnocení funkce asi ${ displaystyle 1,25 { sqrt {H}}}$ v průměru různé argumenty.

Zvažujeme následující experiment. Ze sady H hodnoty, které si vybereme n hodnoty rovnoměrně náhodně, což umožňuje opakování. Nechat str(n; H) je pravděpodobnost, že během tohoto experimentu bude vybrána alespoň jedna hodnota více než jednou. Tuto pravděpodobnost lze odhadnout jako

${ Displaystyle p (n; H) přibližně 1-e ^ {- n (n-1) / (2H)} přibližně 1-e ^ {- n ^ {2} / (2H)}}$^[4]

Nechat n(str; H) být nejmenší počet hodnot, které musíme zvolit, takže pravděpodobnost zjištění kolize je alespoňstr. Invertováním tohoto výrazu výše najdeme následující aproximaci

${ displaystyle n (p; H) přibližně { sqrt {2H ln { frac {1} {1-p}}}}}$

a přiřadíme 0,5 pravděpodobnosti srážky, ke které dorazíme

${ displaystyle n (0,5; H) přibližně 1,1774 { sqrt {H}}}$

Nechat Q(H) je očekávaný počet hodnot, které musíme zvolit, než najdeme první kolizi. Toto číslo lze odhadnout na

${ displaystyle Q (H) přibližně { sqrt {{ frac { pi} {2}} H}}}$

Jako příklad, pokud se použije 64bitový hash, existuje přibližně 1,8 × 10¹⁹ různé výstupy. Pokud jsou všechny stejně pravděpodobné (nejlepší případ), pak by to trvalo „pouze“ přibližně 5 miliard pokusů (5,38 × 10⁹) generovat kolizi hrubou silou. Tato hodnota se nazývá narozeniny svázané^[5] a pro n-bitové kódy, které lze vypočítat jako 2^n/2.^[6] Další příklady jsou následující:

Bity	Možné výstupy (H)	Požadovaná pravděpodobnost náhodné kolize (2 s.f.) (p)
		10−18	10−15	10−12	10−9	10−6	0.1%	1%	25%	50%	75%
16	216 (~ 6,5 x 104)	<2	<2	<2	<2	<2	11	36	190	300	430
32	232 (~4.3 × 109)	<2	<2	<2	3	93	2900	9300	50,000	77,000	110,000
64	264 (~1.8 × 1019)	6	190	6100	190,000	6,100,000	1.9 × 108	6.1 × 108	3.3 × 109	5.1 × 109	7.2 × 109
128	2128 (~3.4 × 1038)	2.6 × 1010	8.2 × 1011	2.6 × 1013	8.2 × 1014	2.6 × 1016	8.3 × 1017	2.6 × 1018	1.4 × 1019	2.2 × 1019	3.1 × 1019
256	2256 (~1.2 × 1077)	4.8 × 1029	1.5 × 1031	4.8 × 1032	1.5 × 1034	4.8 × 1035	1.5 × 1037	4.8 × 1037	2.6 × 1038	4.0 × 1038	5.7 × 1038
384	2384 (~3.9 × 10115)	8.9 × 1048	2.8 × 1050	8.9 × 1051	2.8 × 1053	8.9 × 1054	2.8 × 1056	8.9 × 1056	4.8 × 1057	7.4 × 1057	1.0 × 1058
512	2512 (~1.3 × 10154)	1.6 × 1068	5.2 × 1069	1.6 × 1071	5.2 × 1072	1.6 × 1074	5.2 × 1075	1.6 × 1076	8.8 × 1076	1.4 × 1077	1.9 × 1077

Tabulka ukazuje počet hashů n(str) potřebné k dosažení dané pravděpodobnosti úspěchu za předpokladu, že všechny hashe jsou stejně pravděpodobné. Pro srovnání, 10⁻¹⁸ na 10⁻¹⁵ je neopravitelná bitová chybovost typického pevného disku.^[7] Teoreticky, MD5 hash nebo UUID, který má 128 bitů, by měl zůstat v tomto rozsahu až do přibližně 820 miliard dokumentů, i když jeho možných výstupů je mnohem více.

Je snadné vidět, že pokud jsou výstupy funkce rozloženy nerovnoměrně, mohla by být kolize nalezena ještě rychleji. Pojem „rovnováha“ hašovací funkce kvantifikuje odolnost funkce proti útokům narozenin (využití nerovnoměrného rozložení klíčů.) Stanovení rovnováhy hashovací funkce však obvykle vyžaduje výpočet všech možných vstupů, a proto je pro populární nemožné hashovací funkce, jako jsou rodiny MD a SHA.^[8]Podvýraz ${ displaystyle ln { frac {1} {1-p}}}$ v rovnici pro ${ displaystyle n (p; H)}$ není vypočítán přesně pro malé ${ displaystyle p}$ při přímém překladu do běžných programovacích jazyků jako log (1 / (1-p)) kvůli ztráta významu. Když log1p je k dispozici (tak, jak je v C99 ) například ekvivalentní výraz -log1p (-p) místo toho by měl být použit.^[9] Pokud se tak nestane, první sloupec výše uvedené tabulky se vypočítá jako nula a několik položek ve druhém sloupci nemá ani jednu správnou významnou číslici.

Jednoduchá aproximace

Dobrý pravidlo pro které lze použít mentální výpočet je vztah

${ displaystyle p (n) přibližně {n ^ {2} nad 2H}}$

které lze také zapsat jako

${ displaystyle H cca {n ^ {2} nad 2p (n)}}$.

nebo

${ displaystyle n přibližně { sqrt {2H krát p (n)}}}$.

To funguje dobře pro pravděpodobnosti menší nebo rovné 0,5.

Toto schéma aproximace je obzvláště snadné při práci s exponenty. Předpokládejme například, že vytváříte 32bitové hashe (${ displaystyle H = 2 ^ {32}}$) a chtějí, aby šance na kolizi byla maximálně jedna ku milionu (${ displaystyle p přibližně 2 ^ {- 20}}$), kolik dokumentů bychom mohli mít maximálně?

${ displaystyle n cca { sqrt {2 krát 2 ^ {32} krát 2 ^ {- 20}}} = { sqrt {2 ^ {1 + 32-20}}} = { sqrt {2 ^ {13}}} = 2 ^ {6,5} přibližně 90,5}$

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

Citlivost digitálního podpisu

Digitální podpisy může být náchylný k narozeninovému útoku. Zpráva ${ displaystyle m}$ je obvykle podepsán prvním výpočtem ${ displaystyle f (m)}$, kde ${ displaystyle f}$ je kryptografická hashovací funkce a poté pomocí nějakého tajného klíče podepsat ${ displaystyle f (m)}$. Předpokládat Mallory chce Boba oklamat do podpisu a podvodný smlouva. Mallory připravuje spravedlivou smlouvu ${ displaystyle m}$ a podvodný ${ displaystyle m '}$. Poté najde řadu pozic, kde ${ displaystyle m}$ může být změněna beze změny významu, jako je vložení čárky, prázdné řádky, jedna proti dvěma mezerám za větou, nahrazení synonym atd. Kombinací těchto změn může vytvořit obrovské množství variací na ${ displaystyle m}$ což jsou všechny spravedlivé smlouvy.

Podobným způsobem Mallory také vytváří obrovské množství variací podvodné smlouvy ${ displaystyle m '}$. Poté použije hashovací funkci na všechny tyto varianty, dokud nenajde verzi spravedlivé smlouvy a verzi podvodné smlouvy, které mají stejnou hodnotu hash, ${ displaystyle f (m) = f (m ')}$. Představuje spravedlivou verzi Bobovi k podpisu. Poté, co Bob podepsal, Mallory vezme podpis a připojí jej k podvodné smlouvě. Tento podpis pak „dokazuje“, že Bob podepsal podvodnou smlouvu.

Pravděpodobnosti se mírně liší od původního problému s narozeninami, protože Mallory nezíská nic, když najde dvě férové ​​nebo dvě podvodné smlouvy se stejným hashem. Strategií Mallory je generovat páry jedné spravedlivé a jedné podvodné smlouvy. Kde platí rovnice problému narozenin ${ displaystyle n}$ je počet párů. Počet hash, které Mallory ve skutečnosti generuje, je ${ displaystyle 2n}$.

Aby se tomuto útoku zabránilo, lze výstupní délku hashovací funkce použité pro schéma podpisu zvolit dostatečně velkou, aby se narozeninový útok stal výpočetně neproveditelným, tj. Přibližně dvakrát tolik bitů, než je potřeba, aby se zabránilo běžnému útok hrubou silou.

Kromě použití větší bitové délky se může signatář (Bob) chránit provedením náhodných, neškodných změn v dokumentu před jeho podepsáním a ponecháním kopie smlouvy, kterou podepsal, ve svém vlastním vlastnictví, aby mohl alespoň u soudu prokázat, že jeho podpis odpovídá té smlouvě, nejen té podvodné.

Pollardův rho algoritmus pro logaritmy je příkladem algoritmu používajícího k výpočtu útoku narozeniny diskrétní logaritmy.

Viz také

• Kolizní útok
• Meet-in-the-middle útok

Poznámky

Reference

• Mihir Bellare, Tadayoshi Kohno: Bash Function Balance and its Impact on Birthday Attacks. EUROCRYPT 2004: pp401–418
• Applied Cryptography, 2. vyd. podle Bruce Schneier

externí odkazy

• „Co je digitální podpis a co je ověření?“ z Zabezpečení RSA je krypto FAQ.
• „Narozeninový útok“ X5 Networks Crypto FAQ