Fødselsdagsangreb

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 15. december 2015; checks kræver 67 redigeringer .

Et fødselsdagsangreb er et navn, der bruges i kryptoanalyse for en metode til at bryde cifre eller finde hashfunktionskollisioner baseret på fødselsdagsparadokset . Essensen af metoden er væsentligt at reducere antallet af argumenter, der sendes til hashfunktionen, hvilket er nødvendigt for at detektere en kollision, da hvis hashfunktionen genererer en n -bit værdi, så er antallet af tilfældige hashfunktionsargumenter for hvilke ved mindst én hash-kollision vil blive detekteret med en høj sandsynlighedsfunktion (det vil sige, at der er mindst ét par lige store hash-koder opnået på forskellige argumenter) er ikke 2 n , men kun omkring 2 n /2 .

Forstå problemet

Overvej et eksempel: Vil to personer i en gruppe på 23 have samme fødselsdag? Et år, eksklusive skudår, er 365 dage, så der er 365 forskellige fødselsdage, et meget større antal end 23.

Hvis vi valgte en bestemt dag, så ville sandsynligheden for, at mindst én person blev født på den pågældende dag, være omkring 6,1 %. Sandsynligheden for, at mindst én person har samme fødselsdag som enhver anden person, er dog omkring 50 % ifølge formlen [1] . For n = 70 er sandsynligheden for et sådant sammenfald 99,9%. $1-(364/365)^{23}$ $1-365!/((365-n)!\cdot 365^{n})$

Matematik

For en given hashfunktion er målet med angrebet at finde en kollision af den anden slags . For at gøre dette beregnes værdier for tilfældigt udvalgte blokke af inputdata, indtil der findes to blokke, der har samme hash. $h$ $h$

Lad være en hash-funktion . Fødselsdagsangrebet er vellykket, hvis der er et par sådan, at $h$ $x_{1}\neq x_{2}$ $h(x_{1})=h(x_{2}).$

Således, hvis en funktion giver nogen af de forskellige output med lige stor sandsynlighed og er stor nok, så er den matematiske forventning om antallet af par af forskellige argumenter , som er . Estimering af antallet af hash-operationer for at finde en kollision af en ideel kryptografisk hashfunktion med en outputstørrelse på bit skrives ofte som og ikke [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}}$

Lad være sandsynligheden for, at mindst to personer i en gruppe mennesker ( ) har samme fødselsdag. $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}}\right).

Fra de to første led af udvidelsen til Taylor - serien af funktionen for , $\displaystyle e^{x}=1+{\dfrac {x}{1!}}+{\dfrac {x^{2}}{2!}}+{\dfrac {x^{3} }{3!}}+\cdots ,$ $|x|\ll 1$ $e^{x}\ca. 1+x.$ $\left(1-{\frac {i}{N))\right)$ ${e}^{-i/N},$

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

Lad os finde sådan et tal $n$ $P(n)\geq {\frac {1}{2)).$

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

Følgelig,

n\geq {\sqrt {2\ln 2\cdot N}}\ca. 1.177{\sqrt {N}}\ca. 23

[1] .

For eksempel, hvis der bruges en 64-bit hash, er der ca. 1,8 × 10 19 forskellige udgange. Hvis de alle er lige sandsynlige (bedste tilfælde), så ville det "kun" tage omkring 5 milliarder forsøg ( 5,38×109 ) at skabe en kollision ved brug af brute force . Andre eksempler:

stykker	Mulige udgange (N)	Ønsket tilfældig kollisionssandsynlighed (P)
stykker	Mulige udgange (N)	10-18 _	10-15 _	10-12 _	10-9 _	10-6 _	0,1 %	en %	25 %	halvtreds %	75 %
16	2 16 (~6,5 x 10 3 )	<2	<2	<2	<2	<2	elleve	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

Tabellen viser antallet af hashes , der er nødvendige for at opnå en given sandsynlighed for succes, forudsat at alle hashes er lige sandsynlige. Til sammenligning er

n(P),

10 −18 til 10 −15 den ukorrigerbare bitfejlrate for en typisk harddisk [3] . Teoretisk set bør MD5 -hash eller en UUID på 128 bit forblive inden for dette område op til omkring 820 milliarder dokumenter, selvom dets mulige resultater er meget større.

Det er let at se, at hvis udgangene af en funktion er ujævnt fordelt, så kan kollisioner findes endnu hurtigere. Begrebet "balance" af en hash-funktion kvantificerer funktionens modstand mod et "fødselsdag"-angreb (ved hjælp af uensartet nøglefordeling). Men at bestemme balancen i en hashfunktion kræver beregning af alle mulige input og er derfor ikke mulig for populære hashfunktioner såsom MD- og SHA-familierne.

Digital signaturfølsomhed

En elektronisk digital signatur kan for eksempel være sårbar over for dette angreb . Lad os sige, at 2 personer - A og B - ønsker at underskrive en kontrakt, men A ønsker at give B en falsk version af kontrakten. Så udarbejder A en ægte kontrakt og en falsk kontrakt. Yderligere, ved at foretage gyldige ændringer, der ikke ændrer betydningen af teksten (arrangere kommaer, bindestreger, indrykninger), opnår A, at begge kontrakter har samme hash. Herefter sender A B en ægte kontrakt, B underskriver den, og hans underskrift viser også, at han også underskrev en falsk kontrakt, da begge kontrakter har samme hash. For at undgå denne form for sårbarhed er det nok at øge hash-længden, så det bliver beregningsmæssigt svært at finde 2 kontrakter med de samme hashes. Især kræves dobbelt så lang hash-længde for at give beregningsmæssig kompleksitet, der kan sammenlignes med brute-force-søgning. Med andre ord, hvis en angriber kan beregne hash-værdier ved hjælp af brute force , så vil han begynde at finde hash-kollisioner for alle hash-værdier, der er mindre end lidt lange. (se en: Fødselsdagsangreb ) $2^{n}$ $2n$

For at undgå dette angreb kan outputlængden af hashfunktionen, der bruges til signaturskemaet, vælges stor nok til at gøre "fødselsdage" angrebet beregningsmæssigt umuligt, dvs. omkring dobbelt så mange bits, som er nødvendige for at forhindre et konventionelt "brute force" angreb (fuld opregning) .

BIND fødselsdagsangreb

DNS er et distribueret computersystem til at indhente information om . Oftest brugt til at få en IP-adresse fra værtsnavnet (computer eller enhed).

Udtrykket "rekursion" i DNS refererer til DNS-serverens adfærd, hvor serveren på vegne af klienten udfører en komplet søgning efter den nødvendige information i hele DNS-systemet, om nødvendigt med henvisning til andre DNS-servere. I tilfælde af en "rekursiv" forespørgsel poller DNS-serveren serverne (i faldende rækkefølge af zoneniveauet i navnet), indtil den finder et svar eller finder ud af, at domænet ikke eksisterer (i praksis starter søgningen fra DNS-servere tættest på den ønskede, hvis oplysninger om er cachelagrede og opdaterede, kan serveren ikke forespørge andre DNS-servere).

I 2002 udgav Wagner fra Sacramento en anbefaling, der viser et problem med BINDs implementering af DNS-protokollen. Han fandt ud af, at BIND sendte flere samtidige rekursive anmodninger om den samme IP-adresse.

Angriberen sender en forespørgsel til offerets DNS-server. Den vælger et domænenavn, som DNS-server A ikke kan finde i sin cache og er tvunget til at videresende til den næste DNS-server B. Hver tilladelsesudveksling mellem A og B autentificeres gennem et tilfældigt TID. Før DNS Server A kan modtage svarpakker fra DNS Server B, sender angriberen N falske svarpakker til DNS Server A. Hvis en af disse falske pakker har samme TID som DNS Server A's TID, vil de falske pakker blive accepteret af serveren A som gyldige pakker. Det rigtige svar fra DNS Server B vil ikke blive behandlet af DNS Server A. En angriber kan således "forgifte" DNS Server A's cache for at kortlægge det kompromitterede domæne til den IP-adresse, som angriberen har angivet.

I et normalt angreb sender angriberen N falske svar for én anmodning, sandsynligheden for succes er (TID - 16-bit nummer). ${\frac {N}{65535}}$

Fødselsdagsangrebet gør det nemmere at bryde BIND-protokollen. Angriberen sender et stort antal N forespørgsler til offerets DNS-server, alle med det samme domænenavn. Vi sender N falske svar for N anmodninger. Derfor er sandsynligheden for, at angrebet vil lykkes [4]

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

Simpel tilnærmelse

En god tommelfingerregel , der kan bruges til en hurtig mental vurdering , er parforholdet

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

som også kan skrives som

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

eller

n\ca. {\sqrt {2N\gange P(n))).

Denne tilnærmelse fungerer godt for sandsynligheder mindre end eller lig med 0,5.

Dette tilnærmelsesskema er særligt nemt at bruge, når du arbejder med indikatorer. Lad os for eksempel estimere, hvor mange dokumenter der kan behandles af en 32-bit hash-funktion ( ), så sandsynligheden for en kollision ikke er mere end én ud af en million ( ). Et skøn over det størst mulige antal dokumenter for sådanne forhold er $N=2^{32}$ $P=10^{-6}\ca. 2^{-20}$

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

som er tæt på det rigtige svar 93.

Eksempler

Antag, at for at angribe en 64-bit blokchiffer, skal en angriber opnå to klartekst/ciffertekst-par, der kun adskiller sig i den mindst signifikante bit. Fortolkningen af dette problem i forhold til fødselsdagsparadokset fører til den konklusion, at rummet af kun kendte klartekster vil indeholde det nødvendige par med stor sandsynlighed [5] . $2^{32}$

Som et andet eksempel kan du overveje cyklussen af en 64-bit Feistel-chiffer . Antag, at chifferen bruger en tilfældig funktion F (32 til 32 bit). En angriber vil måske gerne vide, hvor mange klartekster han skal have for at få en kollision af funktion F . Ifølge fødselsdagsparadokset skal man hertil sortere i åbne tekster [5] . $2^{16}$

En konsekvens af fødselsdagsparadokset er, at for en n -bit blokchiffer kan gentagne forekomster af en chiffertekstblok forventes med en sandsynlighed på omkring 0,63 givet kun tilfældige klartekster krypteret på den samme nøgle (uanset nøglestørrelse). For ECB-tilstand, hvis to chiffertekstblokke matcher, skal de tilsvarende klartekster også matche. Det betyder, at i et kendt chiffertekstangreb kan information om klarteksterne afsløres fra chiffertekstblokkene. $2^{{n/2}}$

Noter

↑ 1 2 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein Introduction to algorithms, tredje udgave, s. 130-133
↑ Bukhantsov A. D., Druzhkova I. V. Om ændringen af MD5-algoritmen // Belgorod State National Research University, 2016, s. 176.
↑ Gray, Jim & van Ingen, Catharine (25. januar 2007), Empirical Measurements of Disk Failure Rate and Error Rate, arΧiv : cs/0701166 .
↑ Joe Stewart , DNS Cache Poisoning, s. 4-5.
↑ 1 2 Babenko L. K., Ischukova E. A. , Analyse af symmetriske kryptosystemer, s. 146.

Litteratur

Mihir Bellare, Tadayoshi Kohno : Hash-funktionsbalance og dens indvirkning på fødselsdagsangreb. EUROCRYPT 2004: s. 401-418
Don Coppersmith : Another Birthday Attack, Proceeding CRYPTO '85 Advances in Cryptology s. 14-17