Atacul de ziua de nastere

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 15 decembrie 2015; verificările necesită 67 de modificări .

Un atac de naștere este un nume folosit în criptoanaliza pentru o metodă de spargere a cifrurilor sau de găsire a coliziunilor cu funcțiile hash bazate pe paradoxul zilei de naștere . Esența metodei este reducerea semnificativă a numărului de argumente transmise funcției hash, ceea ce este necesar pentru a detecta o coliziune, deoarece dacă funcția hash generează o valoare de n biți, atunci numărul de argumente ale funcției hash pentru care la cel puțin o coliziune hash va fi detectată cu o funcție de mare probabilitate (adică există cel puțin o pereche de coduri hash egale obținute pe argumente diferite) nu este 2 n , ci doar aproximativ 2 n /2 .

Înțelegerea problemei

Luați în considerare un exemplu: vor avea două persoane dintr-un grup de 23 de ani aceeași zi de naștere? Un an, excluzând anii bisecți, este de 365 de zile, deci există 365 de zile de naștere diferite, un număr mult mai mare decât 23.

Dacă am alege o anumită zi, atunci probabilitatea ca cel puțin o persoană să se fi născut în acea zi anume ar fi de aproximativ 6,1%. Cu toate acestea, probabilitatea ca cel puțin o persoană să aibă aceeași zi de naștere ca orice altă persoană este de aproximativ 50%, conform formulei [1] . Pentru n = 70 , probabilitatea unei astfel de coincidențe este de 99,9%. $1-(364/365)^{23}$ $1-365!/((365-n)!\cdot 365^{n})$

Matematică

Pentru o funcție hash dată, scopul atacului este de a găsi o coliziune de al doilea tip . Pentru a face acest lucru, valorile sunt calculate pentru blocurile de date de intrare selectate aleatoriu până când sunt găsite două blocuri care au același hash. $h$ $h$

Fie o funcție hash . Atacul de ziua de naștere are succes dacă există o pereche astfel încât $h$ $x_{1}\neq x_{2)$ $h(x_{1})=h(x_{2}).$

Astfel, dacă o funcție oferă oricare dintre ieșirile diferite cu probabilitate egală și este suficient de mare, atunci așteptarea matematică a numărului de perechi de argumente diferite pentru care este . Estimarea numărului de operații hash pentru găsirea unei coliziuni a unei funcții hash criptografice ideale cu o dimensiune de ieșire de biți este adesea scrisă ca și nu [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}}$

Fie probabilitatea ca cel puțin două persoane dintr-un grup de persoane ( ) să aibă aceeași zi de naștere. $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}}\dreapta).

Din primii doi termeni ai expansiunii în seria Taylor a funcției pentru , $\displaystyle e^{x}=1+{\dfrac {x}{1!}}+{\dfrac {x^{2}}{2!}}+{\dfrac {x^{3} }{3!}}+\cdots ,$ $|x|\ll 1$ $e^{x}\aprox 1+x.$ $\stanga(1-{\frac {i}{N))\dreapta)$ ${e}^{-i/N},$

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

Să găsim un număr astfel încât $n$ $P(n)\geq {\frac {1}{2)).$

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

Prin urmare,

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

[1] .

De exemplu, dacă se utilizează un hash pe 64 de biți, există aproximativ 1,8 × 10 19 ieșiri diferite. Dacă toate sunt la fel de probabil (cel mai bun caz), atunci ar fi nevoie de „doar” aproximativ 5 miliarde de încercări ( 5,38×109 ) pentru a crea o coliziune folosind forța brută . Alte exemple:

biți	Ieșiri posibile (N)	Probabilitatea de coliziune aleatoare dorită (P)
biți	Ieșiri posibile (N)	10 −18	10 −15	10 −12	10 −9	10 −6	0,1%	unu %	25%	cincizeci la sută	75%
16	2 16 (~6,5 x 10 3 )	<2	<2	<2	<2	<2	unsprezece	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

Tabelul arată numărul de hashe-uri necesare pentru a obține o anumită probabilitate de succes, presupunând că toate hashe-urile sunt la fel de probabile. Prin comparație,

n(P),

10 −18 până la 10 −15 este rata de eroare de biți necorecabilă a unui hard disk tipic [3] . Teoretic, hashurile MD5 sau un UUID de 128 de biți ar trebui să rămână în acest interval până la aproximativ 820 de miliarde de documente, chiar dacă posibilele sale rezultate sunt mult mai mari.

Este ușor de observat că, dacă ieșirile unei funcții sunt distribuite neuniform, atunci coliziunile pot fi găsite și mai repede. Conceptul de „echilibru” al unei funcții hash cuantifică rezistența funcției la un atac „de ziua de naștere” (folosind distribuția neuniformă a tastelor). Totuși, determinarea echilibrului unei funcții hash necesită calcularea tuturor intrărilor posibile și, prin urmare, nu este fezabilă pentru funcțiile hash populare, cum ar fi familiile MD și SHA.

Sensibilitatea semnăturii digitale

O semnătură digitală electronică , de exemplu, poate fi vulnerabilă la acest atac . Să presupunem că 2 persoane - A și B - vor să semneze un contract, dar A vrea să-i strecoare lui B o versiune falsă a contractului. Apoi A întocmește un contract autentic și un contract fals. În plus, făcând modificări valide care nu schimbă sensul textului (aranjarea virgulelor, cratimelor, liniuțelor), A realizează ca ambele contracte să aibă același hash. După aceea, A îi trimite lui B un contract autentic, B îl semnează, iar semnătura lui mai arată că a semnat și un contract fals, deoarece ambele contracte au același hash. Pentru a evita acest tip de vulnerabilitate, este suficient să măriți lungimea hash-ului, astfel încât să devină dificil din punct de vedere computațional să găsiți 2 contracte cu aceleași hash-uri. În special, este necesară o lungime de două ori mai mare pentru a oferi o complexitate de calcul comparabilă cu cea a căutării cu forță brută. Cu alte cuvinte, dacă un atacator poate calcula valorile hash folosind forța brută , atunci va începe să găsească coliziuni hash pentru toate hashurile mai puțin lungi. (vezi ro:Atacul de naștere ) $2^{n}$ $2n$

Pentru a evita acest atac, lungimea de ieșire a funcției hash utilizată pentru schema de semnătură poate fi aleasă suficient de mare pentru a face ca atacul „zi de naștere” să nu fie fezabil din punct de vedere computațional, adică aproximativ de două ori mai mulți biți decât sunt necesari pentru a preveni un atac convențional de „forță brută”. (enumerarea completă) .

Atacul de ziua BIND

DNS este un sistem computerizat distribuit pentru obținerea de informații despre . Cel mai frecvent folosit pentru a obține o adresă IP de la numele gazdei (computer sau dispozitiv).

Termenul de „recursie” în DNS se referă la comportamentul serverului DNS, în care serverul efectuează în numele clientului o căutare completă a informațiilor necesare în întregul sistem DNS, dacă este cazul, referindu-se la alte servere DNS. În cazul unei interogări „recursive”, serverul DNS interogează serverele (în ordinea descrescătoare a nivelului zonei din nume) până când găsește un răspuns sau constată că domeniul nu există (în practică, căutarea începe de la Serverele DNS cele mai apropiate de cel dorit, dacă informațiile despre sunt stocate în cache și sunt actualizate, serverul nu poate interoga alte servere DNS).

În 2002, Wagner din Sacramento a publicat o recomandare care arată o problemă cu implementarea de către BIND a protocolului DNS. El a descoperit că BIND trimitea mai multe solicitări recursive simultane pentru aceeași adresă IP.

Atacatorul trimite o interogare la serverul DNS al victimei. Alege un nume de domeniu pe care serverul DNS A nu îl poate găsi în memoria cache și este forțat să îl redirecționeze către următorul server DNS B. Fiecare schimb de permisiuni între A și B este autentificat printr-un TID aleatoriu. Înainte ca serverul DNS A să poată primi pachete de răspuns de la serverul DNS B, atacatorul trimite N pachete de răspuns false către serverul DNS A. Dacă unul dintre aceste pachete false are același TID ca și TID-ul serverului DNS A, atunci pachetele false vor fi acceptate de server. A ca pachete valide. Răspunsul real de la DNS Server B nu va fi procesat de DNS Server A. Astfel, un atacator poate „otrăvi” cache-ul DNS Server A pentru a mapa domeniul compromis la adresa IP furnizată de atacator.

Într-un atac normal, atacatorul trimite N răspunsuri false pentru o cerere, probabilitatea de succes este (TID - număr de 16 biți). ${\frac {N}{65535}}$

Atacul zilei de naștere face mai ușoară încălcarea protocolului BIND. Atacatorul trimite un număr mare de N interogări către serverul DNS al victimei, toate cu același nume de domeniu. Trimitem N răspunsuri false pentru N cereri. Prin urmare, probabilitatea ca atacul să aibă succes este [4]

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

Aproximare simplă

O regulă de bază care poate fi folosită pentru o evaluare mentală rapidă este raportul

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

care poate fi scris și ca

N\aproximativ {n^{2} \peste 2P(n))

n\aprox {\sqrt {2N\times P(n))).

Această aproximare funcționează bine pentru probabilități mai mici sau egale cu 0,5.

Această schemă de aproximare este deosebit de ușor de utilizat atunci când lucrați cu indicatori. De exemplu, să estimăm câte documente pot fi procesate de o funcție hash pe 32 de biți ( ) astfel încât probabilitatea unei coliziuni să nu fie mai mare de unu la un milion ( ). O estimare a celui mai mare număr posibil de documente pentru astfel de condiții este $N=2^{32}$ $P=10^{-6}\aprox 2^{-20}$

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

care este aproape de răspunsul corect 93.

Exemple

Să presupunem că pentru a ataca un cifr bloc pe 64 de biți, un atacator trebuie să obțină două perechi text clar/text cifrat care diferă doar în bitul cel mai puțin semnificativ. Interpretarea acestei probleme în termenii paradoxului zilei de naștere duce la concluzia că spațiul doar al textelor clare cunoscute va conține perechea necesară cu o probabilitate mare [5] . $2^{32}$

Ca un alt exemplu, luați în considerare ciclul unui cifr Feistel pe 64 de biți . Să presupunem că cifrul folosește o funcție aleatorie F (32 până la 32 de biți). Un atacator ar putea dori să știe câte texte clare trebuie să obțină pentru a obține o coliziune a funcției F . Conform paradoxului zilei de naștere, pentru aceasta trebuie să sortați despre textele deschise [5] . $2^{16}$

O consecință a paradoxului zilei de naștere este că pentru un cifr de bloc de n biți, se pot aștepta apariții repetate ale unui bloc de text cifrat cu o probabilitate de aproximativ 0,63, având în vedere doar texte clare aleatorii criptate pe aceeași cheie (indiferent de dimensiunea cheii). Pentru modul ECB, dacă două blocuri de text cifrat se potrivesc, și textele clare corespunzătoare trebuie să se potrivească. Aceasta înseamnă că într-un atac de text cifrat cunoscut, informațiile despre textele clare pot fi dezvăluite din blocurile de text cifrat. $2^{{n/2}}$

Note

↑ 1 2 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein Introduction to algorithms, ediția a treia, p. 130-133
↑ Bukhantsov A. D., Druzhkova I. V. Despre modificarea algoritmului MD5 // Belgorod State National Research University, 2016, p. 176.
↑ Gray, Jim & van Ingen, Catharine (25 ianuarie 2007), Empirical Measurements of Disk Failure Rates and Error Rates, arΧiv : cs/0701166 .
↑ Joe Stewart , DNS Cache Poisoning, p. 4-5.
↑ 1 2 Babenko L. K., Ischukova E. A. , Analysis of symmetric cryptosystems, p. 146.

Literatură

Mihir Bellare, Tadayoshi Kohno : Echilibrul funcției Hash și impactul său asupra atacurilor de naștere. EUROCRYPT 2004: pp401-418
Don Coppersmith : Another Birthday Attack, Proceeding CRYPTO '85 Advances in Cryptology p. 14-17