Födelsedagsattack

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 15 december 2015; kontroller kräver 67 redigeringar .

En födelsedagsattack är ett namn som används i kryptoanalys för en metod för att bryta chiffer eller hitta hashfunktionskollisioner baserat på födelsedagsparadoxen . Kärnan i metoden är att avsevärt minska antalet argument som skickas till hashfunktionen, vilket är nödvändigt för att upptäcka en kollision, eftersom om hashfunktionen genererar ett n -bitarsvärde, då antalet slumpmässiga hashfunktionsargument för vilka vid minst en hashkollision kommer att detekteras med en hög sannolikhetsfunktion (det vill säga att det finns minst ett par lika hashkoder som erhålls på olika argument) är inte 2 n , utan bara cirka 2 n /2 .

Förstå problemet

Tänk på ett exempel: Kommer två personer i en grupp på 23 att ha samma födelsedag? Ett år, exklusive skottår, är 365 dagar, så det finns 365 olika födelsedagar, ett mycket större antal än 23.

Om vi valde en viss dag, så skulle sannolikheten att minst en person föddes just den dagen vara cirka 6,1 %. Sannolikheten för att minst en person har samma födelsedag som vilken annan person som helst är dock cirka 50 %, enligt formeln [1] . För n = 70 är sannolikheten för ett sådant sammanträffande 99,9 %. $1-(364/365)^{23}$ $1-365!/((365-n)!\cdot 365^{n})$

Matematik

För en given hashfunktion är målet med attacken att hitta en kollision av det andra slaget . För att göra detta beräknas värden för slumpmässigt valda block av indata tills två block hittas som har samma hash. $h$ $h$

Låt vara en hashfunktion . Födelsedagsattacken är lyckad om det finns ett par som $h$ $x_{1}\neq x_{2}$ $h(x_{1})=h(x_{2}).$

Således, om en funktion ger någon av de olika utgångarna med lika sannolikhet och är tillräckligt stor, då är den matematiska förväntningen på antalet par av olika argument för vilka . Att uppskatta antalet hashoperationer för att hitta en kollision av en ideal kryptografisk hashfunktion med en utdatastorlek på bitar skrivs ofta som och inte [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}}$

Låt vara sannolikheten att minst två personer i en grupp människor ( ) har samma födelsedag. $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}}\höger).

Från de två första termerna av expansionen till Taylor - serien av funktionen för , $\displaystyle e^{x}=1+{\dfrac {x}{1!}}+{\dfrac {x^{2}}{2!}}+{\dfrac {x^{3} }{3!}}+\cdots ,$ $|x|\ll 1$ $e^{x}\approx 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}\approx 1-{e}^{-{\frac {n^{2}}{ 2N}}}.

Låt oss hitta ett sådant nummer $n$ $P(n)\geq {\frac {1}{2)).$

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

Följaktligen,

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

[1] .

Till exempel, om en 64-bitars hash används, finns det ungefär 1,8 × 10 19 olika utgångar. Om de alla är lika sannolika (bästa fall), så skulle det "bara" ta cirka 5 miljarder försök ( 5,38×109 ) för att skapa en kollision med brute force . Andra exempel:

bitar	Möjliga utgångar (N)	Önskad slumpmässig kollisionssannolikhet (P)
bitar	Möjliga utgångar (N)	10 −18	10 −15	10 −12	10 −9	10 −6	0,1 %	ett %	25 %	femtio %	75 %
16	2 16 (~6,5 x 10 3 )	<2	<2	<2	<2	<2	elva	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 visar antalet hash som behövs för att uppnå en given sannolikhet för framgång, förutsatt att alla hash är lika sannolika. Som jämförelse är

n(P),

10 −18 till 10 −15 den okorrigerbara bitfelsfrekvensen för en typisk hårddisk [3] . Teoretiskt sett bör MD5 -hashar eller en UUID på 128 bitar hålla sig inom detta intervall upp till cirka 820 miljarder dokument, även om dess möjliga resultat är mycket större.

Det är lätt att se att om utsignalerna från en funktion är ojämnt fördelade, kan kollisioner hittas ännu snabbare. Begreppet "balans" för en hashfunktion kvantifierar funktionens motstånd mot en "födelsedag"-attack (med hjälp av olikformig nyckelfördelning). Men att bestämma balansen för en hashfunktion kräver beräkning av alla möjliga indata och är därför inte genomförbart för populära hashfunktioner som MD- och SHA-familjerna.

Digital signatur känslighet

En elektronisk digital signatur , till exempel, kan vara sårbar för denna attack . Låt oss säga att två personer - A och B - vill skriva på ett kontrakt, men A vill ge B en falsk version av kontraktet. Sedan upprättar A ett äkta kontrakt och ett falskt kontrakt. Vidare, genom att göra giltiga ändringar som inte ändrar innebörden av texten (ordna kommatecken, bindestreck, indrag), uppnår A att båda kontrakten har samma hash. Efter det skickar A ett äkta kontrakt till B, B skriver på det, och hans underskrift visar också att han också skrivit på ett falskt kontrakt, eftersom båda kontrakten har samma hash. För att undvika denna typ av sårbarhet räcker det med att öka hashlängden så att det blir beräkningssvårt att hitta 2 kontrakt med samma hash. I synnerhet krävs dubbelt så stor hashlängd för att ge beräkningskomplexitet som är jämförbar med den för brute-force-sökning. Med andra ord, om en angripare kan beräkna hashvärden med brute force , då kommer han att börja hitta hashkollisioner för alla hash som är mindre än lite långa. (se sv:Födelsedagsattack ) $2^{n}$ $2n$

För att undvika denna attack kan utdatalängden för hashfunktionen som används för signaturschemat väljas tillräckligt stor för att göra "födelsedag"-attacken beräkningsmässigt omöjlig, dvs ungefär dubbelt så många bitar som behövs för att förhindra en konventionell "brute force"-attack (fullständig uppräkning) .

BIND födelsedagsattack

DNS är ett distribuerat datorsystem för att få information om . Används oftast för att få en IP-adress från värdnamnet (dator eller enhet).

Termen "rekursion" i DNS hänvisar till beteendet hos DNS-servern, där servern utför på uppdrag av klienten en fullständig sökning efter nödvändig information i hela DNS-systemet, vid behov, med hänvisning till andra DNS-servrar. I fallet med en "rekursiv" fråga frågar DNS-servern servrarna (i fallande ordning efter zonnivån i namnet) tills den hittar ett svar eller finner att domänen inte existerar (i praktiken startar sökningen från DNS-servrar närmast den önskade, om information om är cachad och uppdaterad, kanske servern inte frågar andra DNS-servrar).

2002 publicerade Wagner från Sacramento en rekommendation som visar ett problem med BIND:s implementering av DNS-protokollet. Han fann att BIND skickade flera samtidiga rekursiva förfrågningar för samma IP-adress.

Angriparen skickar en fråga till offrets DNS-server. Den väljer ett domännamn som DNS-server A inte kan hitta i sin cache och tvingas vidarebefordra till nästa DNS-server B. Varje behörighetsutbyte mellan A och B autentiseras genom ett slumpmässigt TID. Innan DNS Server A kan ta emot svarspaket från DNS Server B, skickar angriparen N falska svarspaket till DNS Server A. Om ett av dessa falska paket har samma TID som DNS Server A:s TID, kommer de falska paketen att accepteras av servern A som giltiga paket. Det verkliga svaret från DNS-server B kommer inte att behandlas av DNS-server A. Således kan en angripare "förgifta" DNS-server A:s cache för att mappa den komprometterade domänen till den IP-adress som angriparen tillhandahåller.

I en normal attack skickar angriparen N falska svar för en begäran, sannolikheten för framgång är (TID - 16-bitars nummer). ${\frac {N}{65535}}$

Födelsedagsattacken gör det lättare att bryta BIND-protokollet. Angriparen skickar ett stort antal N frågor till offrets DNS-server, alla med samma domännamn. Vi skickar N falska svar för N förfrågningar. Därför är sannolikheten att attacken kommer att lyckas [4]

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

Enkel approximation

En bra tumregel som kan användas för en snabb mental bedömning är relationen

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

som också kan skrivas som

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

eller

n\approx {\sqrt {2N\ gånger P(n))).

Denna approximation fungerar bra för sannolikheter mindre än eller lika med 0,5.

Detta approximationsschema är särskilt lätt att använda när man arbetar med indikatorer. Låt oss till exempel uppskatta hur många dokument som kan behandlas av en 32-bitars hashfunktion ( ) så att sannolikheten för en kollision inte är mer än en på en miljon ( ). En uppskattning av största möjliga antal handlingar för sådana förhållanden är $N=2^{32}$ $P=10^{-6}\approx 2^{-20}$

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

som är nära det korrekta svaret 93.

Exempel

Antag att för att angripa ett 64-bitars blockchiffer måste en angripare få två klartext/chiffertextpar som bara skiljer sig åt i den minst signifikanta biten. Tolkningen av detta problem i termer av födelsedagsparadoxen leder till slutsatsen att utrymmet för endast kända klartexter kommer att innehålla det nödvändiga paret med hög sannolikhet [5] . $2^{32}$

Som ett annat exempel, betrakta cykeln för ett 64-bitars Feistel-chiffer . Antag att chiffret använder en slumpmässig funktion F (32 till 32 bitar). En angripare kanske vill veta hur många klartexter han behöver få för att få en kollision av funktion F . Enligt födelsedagsparadoxen måste man för detta sortera igenom öppna texter [5] . $2^{16}$

En konsekvens av födelsedagsparadoxen är att för ett n -bitars blockchiffer kan upprepade förekomster av ett chiffertextblock förväntas med en sannolikhet på cirka 0,63 givet endast slumpmässiga klartexter krypterade på samma nyckel (oavsett nyckelstorlek). För ECB-läge, om två chiffertextblock matchar, måste motsvarande klartexter också matcha. Detta innebär att i en känd chiffertextattack kan information om klartexterna avslöjas från chiffertextblocken. $2^{{n/2}}$

Anteckningar

↑ 1 2 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein Introduction to algorithms, tredje upplagan, sid. 130-133
↑ Bukhantsov A. D., Druzhkova I. V. Om modifieringen av MD5-algoritmen // Belgorod State National Research University, 2016, sid. 176.
↑ Gray, Jim & van Ingen, Catharine (25 januari 2007), Empiriska mätningar av diskfelfrekvenser och felfrekvenser, arΧiv : cs/0701166 .
↑ Joe Stewart , DNS-cacheförgiftning, s. 4-5.
↑ 1 2 Babenko L. K., Ischukova E. A. , Analysis of symmetric cryptosystems, sid. 146.

Litteratur

Mihir Bellare, Tadayoshi Kohno : Hash-funktionsbalans och dess inverkan på födelsedagsattacker. EUROCRYPT 2004: s. 401-418
Don Coppersmith : Another Birthday Attack, Proceeding CRYPTO '85 Advances in Cryptology sid. 14-17