Születésnapi támadás

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt hozzászólók, és jelentősen eltérhet a 2015. december 15-én felülvizsgált verziótól ; az ellenőrzések 67 szerkesztést igényelnek .

A születésnapi támadás egy olyan név, amelyet a kriptográfiai elemzésben használnak a rejtjelek feltörésére vagy a hash függvény ütközések megtalálására a születésnapi paradoxon alapján . A módszer lényege, hogy jelentősen csökkenti a hash függvénynek átadott argumentumok számát, ami az ütközés észleléséhez szükséges, hiszen ha a hash függvény n bites értéket generál, akkor azon véletlenszerű hash függvény argumentumok száma, amelyekre a A rendszer legalább egy hash ütközést észlel nagy valószínűségű függvénnyel (vagyis legalább egy pár egyenlő hash kódot kapunk különböző argumentumokon) nem 2 n , hanem csak körülbelül 2 n /2 .

A probléma megértése

Vegyünk egy példát: Egy 23 fős csoportban két embernek ugyanaz lesz a születésnapja? Egy év – szökőévek nélkül – 365 nap, tehát 365 különböző születésnap van, ami jóval nagyobb szám, mint a 23.

Ha egy adott napot választanánk, akkor körülbelül 6,1% lenne annak a valószínűsége, hogy legalább egy ember megszületett azon a napon . Az [1] képlet szerint azonban körülbelül 50% annak a valószínűsége, hogy legalább egy személynek ugyanolyan születésnapja van, mint bármely más személynek . n = 70 esetén az ilyen egybeesés valószínűsége 99,9%. $1-(364/365)^{23}$ $1-365!/((365-n)!\cdot 365^{n})$

Matematika

Egy adott hash függvény esetén a támadás célja egy második típusú ütközés megtalálása . Ehhez a véletlenszerűen kiválasztott bemeneti adatblokkok értékeinek kiszámítása mindaddig történik, amíg nem talál két olyan blokkot, amelyeknek ugyanaz a hash. $h$ $h$

Legyen egy hash függvény . A születésnapi támadás akkor sikeres, ha van olyan pár $h$ ${\displaystyle x_{1}\neq x_{2))$ $h(x_{1})=h(x_{2}).$

Így, ha egy függvény a különböző kimenetek bármelyikét azonos valószínűséggel adja meg, és elég nagy, akkor a matematikai elvárás a különböző argumentumpárok számára , amelyre . A kivonatolási műveletek számának becslését egy ideális kriptográfiai hash függvény ütközésének megtalálásához bites kimeneti mérettel gyakran a következővel írják: és nem [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}}$

Legyen annak a valószínűsége, hogy egy embercsoportban ( ) legalább két embernek ugyanaz a születésnapja. $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}}\jobbra).

A függvény Taylor sorozatába való kiterjesztésének első két tagjából , $\displaystyle e^{x}=1+{\dfrac {x}{1!}}+{\dfrac {x^{2}}{2!}}+{\dfrac {x^{3} }{3!}}+\cdots ,$ $|x|\ll 1$ $e^{x}\kb. 1+x.$ $\left(1-{\frac {i}{N))\right)$ ${e}^{-i/N},$

P(n)\approx 1-\prod _{i=0}^{n-1}\ {e}^{-i/N}=1-\exp \sum _{i=0}^ {n-1}(-i/N)=1-{e}^{-n(n-1)/2N}\körülbelül 1-{e}^{-{\frac {n^{2}}{ 2N}}}.

Keressünk egy ilyen számot $n$ $P(n)\geq {\frac {1}{2)).$

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

Következésképpen,

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

[1] .

Például, ha 64 bites hash-t használunk, körülbelül 1,8 × 10 19 különböző kimenet létezik. Ha mindegyik egyformán valószínű (legjobb esetben), akkor "csak" körülbelül 5 milliárd próbálkozásra ( 5,38 × 109 ) lenne szükség ahhoz, hogy nyers erővel ütközést hozzunk létre . Egyéb példák:

bitek	Lehetséges kimenetek (N)	Kívánt véletlenszerű ütközési valószínűség (P)
bitek	Lehetséges kimenetek (N)	10 −18	10-15 _	10 −12	10 −9	10 −6	0,1%	egy %	25%	ötven %	75%
16	2 16 (~ 6,5 x 10 3 )	<2	<2	<2	<2	<2	tizenegy	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

A táblázat azt mutatja , hogy egy adott siker valószínűségének eléréséhez hány kivonat szükséges, feltételezve, hogy minden hash egyformán valószínű. Összehasonlításképpen:

n(P),

10 -18 és 10 -15 között van egy tipikus merevlemez javíthatatlan bithibaaránya [3] . Elméletileg az MD5 - kivonatoknak vagy a 128 bites UUID -nek ebben a tartományban kell maradnia körülbelül 820 milliárd dokumentumig, még akkor is, ha a lehetséges eredmények sokkal nagyobbak.

Könnyen belátható, hogy ha egy függvény kimenetei egyenlőtlenül oszlanak el, akkor még gyorsabban találhatunk ütközéseket. A hash függvény „egyensúlyának” fogalma számszerűsíti a függvény „születésnapi” támadással szembeni ellenállását (nem egységes kulcselosztást használva). A hash-függvény egyensúlyának meghatározása azonban az összes lehetséges bemenet kiszámítását igényli, ezért ez nem kivitelezhető olyan népszerű hash-függvényeknél, mint az MD és az SHA család.

Digitális aláírás érzékenysége

Egy elektronikus digitális aláírás például sebezhető lehet ezzel a támadással szemben . Tegyük fel, hogy 2 ember – A és B – szeretne szerződést kötni, A viszont B-nek a szerződés hamis változatát akarja csúsztatni. Ezután A valódi és hamis szerződést köt. Továbbá, ha olyan érvényes változtatásokat hajt végre, amelyek nem változtatják meg a szöveg jelentését (vesszők, kötőjelek, behúzások elrendezése), A eléri, hogy mindkét szerződésben ugyanaz a hash legyen. Ezek után A küld B-nek egy valódi szerződést, B aláírja, és az aláírásából is kiderül, hogy ő is hamis szerződést írt alá, mivel mindkét szerződésben ugyanaz a hash. Az ilyen típusú sebezhetőség elkerülése érdekében elegendő a hash hosszát megnövelni, így számításilag nehézkessé válik 2 azonos hash-sel rendelkező szerződés megtalálása. Különösen a kétszeres hash-hosszra van szükség ahhoz, hogy a számítási bonyolultságot a nyers erejű kereséshez hasonlítható legyen. Más szóval, ha a támadó nyers erővel ki tudja számítani a hash értékeket , akkor minden, egy kicsit hosszúnál rövidebb hash-hez kezd hash ütközéseket találni . (lásd : Születésnapi támadás ) $2^{n}$ $2n$

A támadás elkerülése érdekében az aláírási sémához használt hash függvény kimeneti hosszát elég nagyra lehet választani ahhoz, hogy a "születésnapi" támadás számításilag kivitelezhetetlen legyen, azaz körülbelül kétszer annyi bit, mint amennyi a hagyományos "brute force" támadás megakadályozásához szükséges. (teljes felsorolás) .

BIND születésnapi támadás

A DNS egy elosztott számítógépes rendszer információszerzésre a következővel kapcsolatban . A leggyakrabban használt IP-cím beszerzése a gazdagép nevéből (számítógép vagy eszköz).

A DNS-ben a "rekurzió" kifejezés a DNS-kiszolgáló viselkedésére utal, amelyben a szerver a kliens nevében teljes körű keresést végez a szükséges információk után a teljes DNS-rendszerben, szükség esetén más DNS-kiszolgálókra hivatkozva. „Rekurzív” lekérdezés esetén a DNS-kiszolgáló lekérdezi a szervereket (a névben szereplő zónaszint csökkenő sorrendjében), amíg választ nem talál, vagy nem találja, hogy a tartomány nem létezik (a gyakorlatban a keresés a A kívánthoz legközelebbi DNS-kiszolgálók, ha az információk gyorsítótárban vannak és naprakészek, előfordulhat, hogy a szerver nem kérdez le más DNS-kiszolgálókat.

2002-ben Wagner of Sacramento közzétett egy ajánlást, amely egy problémát mutatott be a DNS-protokoll BIND általi megvalósításával kapcsolatban. Azt találta, hogy a BIND több egyidejű rekurzív kérést küld ugyanarra az IP-címre.

A támadó lekérdezést küld az áldozat DNS-kiszolgálójának. Olyan tartománynevet választ, amelyet az A DNS-kiszolgáló nem talál a gyorsítótárában, és kénytelen továbbítani a következő B DNS-kiszolgálónak. Minden engedélycsere A és B között véletlenszerű TID-n keresztül történik. Mielőtt az A DNS-kiszolgáló válaszcsomagokat fogadhatna a B DNS-kiszolgálótól, a támadó N hamis válaszcsomagot küld az A DNS-kiszolgálónak. Ha ezen hamis csomagok egyikének TID-je megegyezik az A DNS-kiszolgáló TID-jével, akkor a szerver elfogadja a hamis csomagokat. A mint érvényes csomagok. A B DNS-kiszolgáló valódi válaszát az A DNS-kiszolgáló nem dolgozza fel. Így a támadó "megmérgezheti" az A DNS-kiszolgáló gyorsítótárát, hogy a feltört tartományt a támadó által megadott IP-címre képezze le.

Normál támadás esetén a támadó N hamis választ küld egy kérésre, a siker valószínűsége (TID - 16 bites szám). ${\frac {N}{65535}}$

A születésnapi támadás megkönnyíti a BIND protokoll feltörését. A támadó nagyszámú N lekérdezést küld az áldozat DNS-kiszolgálójának, mindegyik ugyanazzal a tartománynévvel. N kérésre N hamis választ küldünk . Ezért a támadás sikerességének valószínűsége [4]

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

Egyszerű közelítés

A gyors mentális értékeléshez használható jó hüvelykujjszabály az arány

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

ami úgy is felírható

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

vagy

n\approx {\sqrt {2N\time P(n))).

Ez a közelítés jól működik 0,5-nél kisebb vagy azzal egyenlő valószínűségek esetén.

Ez a közelítési séma különösen könnyen használható indikátorokkal végzett munka során. Például becsüljük meg, hány dokumentumot tud feldolgozni egy 32 bites hash függvény ( ) úgy, hogy az ütközés valószínűsége ne legyen nagyobb, mint egy a millióhoz ( ). Az ilyen állapotokhoz tartozó dokumentumok lehetséges legnagyobb számának becslése az $N=2^{32}$ $P=10^{-6}\kb. 2^{-20}$

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

ami közel áll a helyes válaszhoz 93.

Példák

Tegyük fel, hogy egy 64 bites blokkrejtjel megtámadásához a támadónak két egyszerű szöveg/titkosszöveg párt kell szereznie, amelyek csak a legkisebb jelentőségű bitben különböznek egymástól. A probléma születésnapi paradoxon szerinti értelmezése arra a következtetésre jut, hogy a csak ismert nyílt szövegek tere nagy valószínűséggel tartalmazza majd a szükséges párt [5] . $2^{32}$

Egy másik példaként vegyük egy 64 bites Feistel-rejtjel ciklusát . Tegyük fel, hogy a rejtjel egy F véletlenszerű függvényt használ (32-32 bit). Egy támadónak tudnia kell, hogy hány egyszerű szövegre van szüksége ahhoz, hogy az F függvény ütközését megkapja . A születésnapi paradoxon szerint ehhez a nyitott szövegek körül kell válogatni [5] . $2^{16}$

A születésnapi paradoxon egyik következménye, hogy egy n bites blokkrejtjel esetében egy rejtjelezett szöveg blokk ismételt előfordulása körülbelül 0,63 valószínűséggel várható, ha csak véletlenszerű, ugyanazon a kulccsal titkosított egyszerű szövegeket (a kulcs méretétől függetlenül). Az ECB módban, ha két rejtjelezett szöveg blokk egyezik, a megfelelő egyszerű szövegeknek is meg kell egyeznie. Ez azt jelenti, hogy egy ismert titkosított szöveges támadásnál a nyílt szövegekre vonatkozó információk feltárhatók a titkosított szöveg blokkokból. $2^{{n/2}}$

Jegyzetek

↑ 1 2 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein Bevezetés az algoritmusokba, harmadik kiadás, p. 130-133
↑ Bukhantsov A. D., Druzhkova I. V. Az MD5 algoritmus módosításáról // Belgorodi Állami Nemzeti Kutatóegyetem, 2016, p. 176.
↑ Gray, Jim és van Ingen, Catharine (2007. január 25.), Empirical Measurements of Disk Failure Rates and Error Rates, arΧiv : cs/0701166 .
↑ Joe Stewart , DNS-gyorsítótár mérgezés, p. 4-5.
↑ 1 2 Babenko L. K., Ischukova E. A. , Analysis of symmetric cryptosystems, p. 146.

Irodalom

Mihir Bellare, Tadayoshi Kohno : Hash függvény egyensúlya és hatása a születésnapi támadásokra. EUROCRYPT 2004: 401-418
Don Coppersmith : Újabb születésnapi támadás, Proceeding CRYPTO '85 Advances in Cryptology p. 14-17