Narozeninový útok

 

Narozeninový útok je v kryptografii typ kryptoanalytického útoku, jehož název pochází z matematicky vyřešeného narozeninového problému v teorii pravděpodobnosti. Útok slouží k nalezení kolize v kryptografické hašovací funkci f, což znamená nalézt dvě odlišné vstupní hodnoty x1 a x2 pro funkci f takové, že ƒ(x1) = ƒ(x2). Pro nalezení kolize jsou v tomto útoku náhodně vybírány vstupní hodnoty a vypočítávána z nich výstupní hodnota funkce f, přičemž se nalezení kolize předpokládá průměrně po vyhodnocení 1,25×√H různých vstupních hodnot.

Narozeninový problém

Narozeninový problém říká, že má-li funkce f(x) určitý počet H různých výstupů, které mají stejnou pravděpodobnost výskytu ve výstupech a zároveň je H dostatečně velké, můžeme očekávat, že obdržíme stejný výstup funkce f pro různé vstupní hodnoty x1 a x2, kde ƒ(x1) = ƒ(x2) průměrně po vyhodnocení 1,25×√H různých vstupních hodnot.

Matematicky

Ze sady H hodnot vybereme n hodnot, abychom dovolili rovnoměrné opakování. Nechejte p(n; H) pravděpodobnost, že během tohoto experimentu vybereme alespoň jednu hodnotu více než jednou. Může to být přibližně takto:

p(n;H) \approx 1 - e^{-n(n-1)/(2H)} \approx 1-e^{-n^2/(2H)}, \,

Nechejte n(p; H) nejmenší množství hodnot, které je potřeba vybrat, abychom dosáhli alespoň p pravděpodobnosti kolize. Inverzí horního výrazu dosáhneme následující vzorec:

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

a dosažením 0,5 dosáhneme následující pravděpodobnosti kolize:

n(0.5;H) \approx 1.1774 \sqrt H. \,

Nechejte Q(H) takové, kde je potřeba vybrat tolik hodnot, než dosáhneme první srážky. Toto číslo může být přibližně:

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

Příklad: jestliže používáme 64-bitový otisk, máme přibližně 1.8 × 1019 různých výstupů. Pokud jsou všechny pravděpodobně stejné (nejlepší případ), poté by vyžadovali "pouze" 5.1 × 109 pokusů o generování kolize brutální silou. Tato hodnota je nazývána narozeninovou hranicí a pro n-bitů kódu, které by mohli být vypočteny jako 2n/2. Další příklady jsou zde:

Bitů

Možné
výstupy
(H)

Pravděpodobnost náhodné kolize (p)

10−18

10−15

10−12

10−9

10−6

0.1%

1%

25%

50%

75%

32

4.3 × 109

2

2

2

2.9

93

2.9 × 103

9.3 × 103

5.0 × 104

7.7 × 104

1.1 × 105

64

1.8 × 1019

6.1

1.9 × 102

6.1 × 103

1.9 × 105

6.1 × 106

1.9 × 108

6.1 × 108

3.3 × 109

5.1 × 109

7.2 × 109

128

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

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

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

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 množství otisků n(p) potřebných k dosažení dané pravděpodobnosti úspěchu za předpokladu, že všechny otisky jsou stejně pravděpodobné. Pro srovnání: 10−18 až 10−15 je hodnota, která vyjadřuje počet neopravitelných chyb typického pevného disku. Teoreticky by 128bitový MD5 otisk mohl zůstat v tomto rozsahu až do množství 820 miliard dokumentů, i když počet možných výstupů tohoto otisku je daleko větší.

Citlivost digitálního podpisu

Digitální podpisy mohou být náchylné na narozeninový útok. Zpráva m je typicky podepsána první vypočtenou f(m), kde f je kryptografická hašovací funkce a poté používá tajného klíče k podepsání f(m). Předpokládejme, že Alice chce nalákat Boba do podepsání podvodného kontraktu. Alice připraví kontrakt m a také jeden falešný m'. Alice poté nalézá několik pozic, kde může m změnit tak, aby zpráva neztratila svůj prvotní význam, například: čárky ve větách, prázdné řádky, jednu mezeru proti dvěma mezerám na konci věty, nahrazování synonym, atd. Po zkombinování těchto změn může vytvořit několik variací pro zprávu m, které jsou všechny správné kontrakty.

Podobným způsobem Alice vytváří obrovské množství variací na podvodném kontraktu m'. Poté aplikuje otiskovou funkci ke všem těmto variacím do té doby, než nalezne takový otisk, který bude pro oba kontrakty stejný: f(m) = f(m'). Správnou verzi kontraktu předá k podepsání Bobovi. Poté co Bob podepsal správný kontrakt, Alice vezme podpis a připojí jej k falešnému kontraktu. Tento podpis poté prokazuje, že Bob podepsal falešný kontrakt. Postup se mírně liší od původního narozeninového problému, protože Alice by nezískala ze dvou poctivých (nebo dvou falešných) kontraktů se stejným otiskem prospěch. Alice se snaží nalézt dva různé kontrakty (jeden poctivý a druhý falešný) se stejnými otisky.

Alice srovná každý nově nalezený otisk se všemi předchozími podvodnými otisky a nový podvodný otisk se všemi předchozími správnými otisky. Narozeninový problém používá n různých výstupů. Proto počet otisků, které Alice ve skutečnosti vygeneruje je 2n.

Pro vyhnutí se tomuto útoku musí být délka otiskové funkce užívané pro schéma podpisu tak velká, že se narozeninový útok stává výpočtově neproveditelným, to jest dvakrát více bitů, než by bylo potřeba pro provedení útoku hrubou silou.

Pollardův rho algoritmus pro logaritmy je příkladem algoritmu používající narozeninový útok pro výpočet diskrétních logaritmů.