atac de naștere

Un atac de naștere este un tip de criptografic de atac utilizat pentru criptanaliza algoritmilor de criptare; este așa - numita deoarece exploatează principiile matematice ale paradoxului ziua de naștere în teoria probabilităților .

Atacul ziua de nastere poate fi rezumat după cum urmează: având în vedere o funcție f, scopul atacului este de a găsi 2 numere $x_{1},x_{2}$ ${\ Displaystyle X_ {1}, X_ {2}}$ ${\ Displaystyle X_ {1}, X_ {2}}$ astfel încât $f(x_{1})=f(x_{2})$ ${\ F displaystyle (X_ {1}) = f (X_ {2})}$ $f (X_ {1}) = f (X_ {2})$ . O astfel de pereche de valori $x_{1},x_{2}$ ${\ Displaystyle X_ {1}, X_ {2}}$ ${\ Displaystyle X_ {1}, X_ {2}}$ se numește o coliziune . Metoda utilizată pentru a găsi o coliziune este pur și simplu pentru a evalua funcția f pentru diferite de intrare valori care pot fi alese în mod aleatoriu sau pseudo-aleatoriu , până se obține același rezultat. Datorită paradoxului ziua de nastere aceasta metoda poate fi foarte eficient: în mod specific, în cazul în care o funcție $f(x)$ ${\ F displaystyle (x)}$ $f (x)$ returnează valorile gamei sale $H.$ ${\ H} displaystyle$ $H.$ cu probabilitate identică și mărimea gamei $H.$ ${\ H} displaystyle$ $H.$ (Adică numărul de valori posibile) este suficient de mare, după evaluarea funcției de aprox $1.25\cdot {\sqrt {H}}$ ${\ Displaystyle 1.25 \ cdot {\ sqrt {H}}}$ ${\ Displaystyle 1.25 \ cdot {\ sqrt {H}}}$ argumente diferite, există o șansă de 50% de a obține o pereche de valori distincte $x_{1}$ ${\ displaystyle x_ {1}}$ $x_1$ Și $x_{2}$ ${\ displaystyle x_ {2}}$ $x_2$ pentru care este în valoare de $f(x_{1})=f(x_{2})$ ${\ F displaystyle (X_ {1}) = f (X_ {2})}$ ${\ F displaystyle (X_ {1}) = f (X_ {2})}$ .

principii matematice

Același subiect în detaliu: Zi de nastere paradox .

Să considerăm următorul experiment. Dintr-un set de valori $H.$ ${\ H} displaystyle$ $H.$ noi alegem $n$ ${\ N} displaystyle$ $n$ valori uniform la întâmplare, astfel, de asemenea, permițând repetiții ale aceleași. Sa spunem $p(n;H)$ ${\ Displaystyle p (n; H)}$ ${\ Displaystyle p (n; H)}$ probabilitatea ca cel puțin o valoare este aleasă mai mult decât o dată în timpul experimentului. Probabilitatea poate fi aproximată la

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

{\ P displaystyle (n; H) \ circa 1-e ^ {- (n (n-1)) / 2 \ cdot H} \ approx 1-e ^ {- n ^ {2} / {2 \ cdot H }}}

{\ P displaystyle (n; H) \ circa 1-e ^ {- (n (n-1)) / 2 \ cdot H} \ approx 1-e ^ {- n ^ {2} / {2 \ cdot H }}}

Să presupunem că acum $n(p;H)$ ${\ N displaystyle (p; H)}$ ${\ N displaystyle (p; H)}$ ca cel mai mic număr de valorile pe care le-am ales, astfel încât probabilitatea ne putem aștepta să găsească o coliziune este de cel puțin $p$ ${\ P} displaystyle$ $p$ . Răsturnând expresia de mai sus, vom găsi următoarele aproximarea

n(p;H)\approx {\sqrt {2\cdot H\cdot \ln \left({1 \over 1-p}\right)}},

{\ N displaystyle (p; H) \ approx {\ sqrt {2 \ cdot H \ cdot \ ln \ stânga ({1 \ peste 1 p} \ dreapta)}}}

{\ N displaystyle (p; H) \ approx {\ sqrt {2 \ cdot H \ cdot \ ln \ stânga ({1 \ peste 1 p} \ dreapta)}}}

și atribuirea probabilitatea de a găsi o coliziune la 0,5 vom ajunge la

n(0.5;H)\approx 1.1774{\sqrt {H}}

{\ N displaystyle (0,5; H) \ cca 1.1774 {\ sqrt {H}}}

{\ N displaystyle (0,5; H) \ cca 1.1774 {\ sqrt {H}}}

.

Sa spunem $Q(H)$ ${\ Displaystyle Q (H)}$ ${\ Displaystyle Q (H)}$ cum ar fi numărul așteptat de valori noi trebuie să aleagă înainte de a găsi prima coliziune. Numărul poate fi aproximată prin

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

{\ Displaystyle Q (H) \ aprox {\ pi \ peste 2} {\ sqrt {H}}.}

{\ Displaystyle Q (H) \ aprox {\ pi \ peste 2} {\ sqrt {H}}.}

Ca un exemplu, în cazul în care un 64- bit este utilizat hash, există aproximativ 1,8 x 10 ¹⁹ rezultate diferite. Dacă acestea sunt toate la fel de probabile (cel mai bun), atunci va dura aproximativ „doar“ 5.1 × 10 ⁹ încercări de a genera o coliziune folosind forta bruta . Această valoare se numește constrângere pentru ziua de naștere și coduri de biți n- poate fi calculată ca $2^{n/2}$ ${\ Displaystyle 2 ^ {n / 2}}$ ${\ Displaystyle 2 ^ {n / 2}}$ ^[1] . Alte exemple sunt următoarele:

Pic	Posibil rezultate (H)	probabilitate dorită de coliziune aleatorii (p)
Pic	Posibil rezultate (H)	10 ⁻¹⁸	10 ⁻¹⁵	10 ⁻¹²	10 ⁻⁹	10 ⁻⁶	0,1%	1%	25%	50%	75%
32	4,3 × 10 ⁹	2	2	2	2.9	93	2,9 x 10 ³	9,3 x 10 ³	5,0 x 10 ⁴	7,7 x 10 ⁴	1,1 × 10 ⁵
64	1.8 × 10 ¹⁹	6.1	1,9 x 10 ²	6,1 x 10 ³	1,9 x 10 ⁵	6,1 x 10 ⁶	1,9 x 10 ⁸	6,1 × 10 ⁸	3,3 × 10 ⁹	5,1 x 10 ⁹	7,2 × 10 ⁹
128	3.4 × 10 ³⁸	2,6 x 10 ¹⁰	8,2 × 10 ¹¹	2,6 x 10 ¹³	8,2 × 10 ¹⁴	2,6 x 10 ¹⁶	8,3 × 10 ¹⁷	2,6 x 10 ¹⁸	1.4 × 10 ¹⁹	2.2 × 10 ¹⁹	3,1 × 10 ¹⁹
256	1.2 x 10 ⁷⁷	4.8 x 10 ²⁹	1,5 × 10 ³¹	4.8 x 10 ³²	1,5 × 10 ³⁴	4.8 x 10 ³⁵	1,5 x 10 ³⁷	4.8 x 10 ³⁷	2,6 x 10 ³⁸	4,0 × 10 ³⁸	5,7 x 10 ³⁸
384	3.9 x 10 ¹¹⁵	8,9 × 10 ⁴⁸	2,8 × 10 ⁵⁰	8.9 × 10 ⁵¹	2,8 × 10 ⁵³	8,9 x 10 ⁵⁴	2,8 × 10 ⁵⁶	8,9 × 10 ⁵⁶	4.8 x 10 ⁵⁷	7,4 × 10 ⁵⁷	1,0 × 10 ⁵⁸
512	1.3 x 10 ¹⁵⁴	1,6 × 10 ⁶⁸	5,2 x 10 ⁶⁹	1,6 x 10 ⁷¹	5,2 x 10 ⁷²	1,6 × 10 ⁷⁴	5,2 x 10 ⁷⁵	1,6 × 10 ⁷⁶	8,8 × 10 ⁷⁶	1,4 x 10 ⁷⁷	1.9 x 10 ⁷⁷

Arată tabelul numărul hashes n (p) este necesar pentru a obține probabilitatea specificată de succes, presupunând că toate hashes sunt egal posibile. Ca o comparație, rata nerectificabile bit eronată a unui hard disk variază de la 10 ^-18-10 ^-15 [1] . În teorie, MD5 , cu hash de 128 de biți lung, ar trebui să intre în acel interval de până la 820 de miliarde de documente, cu toate că rezultatele sale posibile sunt mult mai mult.

Implicații în criptografie

Este ușor de observat că, dacă ieșirile functiei sunt distribuite inegal, atunci o coliziune poate fi găsit mult mai rapid. Noțiunea de echilibrare o funcție hash cuantifică rezistența la funcția de la atacuri de ziua de naștere și ne permite să se estimeze vulnerabilitatea populare hash - uri , cum ar fi MDX și SHA ( Bellare și Kohno, 2004 ).

Semnăturile digitale pot fi vulnerabile la un atac ziua de nastere. Un mesaj $m$ ${\ displaystyle m}$ $m$ acesta este, în general, semnat înainte de a calcula $f(m)$ ${\ F displaystyle (m)}$ $f (m)$ , unde este $f$ ${\ F displaystyle}$ $f$ este o funcție criptografică de hashing , și apoi folosind unele cheie secretă pentru semn $f(m)$ ${\ F displaystyle (m)}$ $f (m)$ . Să presupunem că Oscar vrea să păcălească Bob în semnarea unui contract fraudulos. Oscar pregătește un contract $m$ ${\ displaystyle m}$ $m$ corectă și unul $m^{'}$ ${\ M displaystyle „}$ $eu$ necinstit. Oscar găsește apoi un număr de puncte în contract pentru care $m$ ${\ displaystyle m}$ $m$ acesta poate fi modificat fără a schimba sensul, de exemplu, prin introducerea virgule, linii goale, una sau două spații după o propoziție, înlocuind sinonime, etc. Prin combinarea acestor modificări, Oscar poate crea un număr semnificativ de variații ale $m$ ${\ displaystyle m}$ $m$ care sunt, practic, toate contractele corecte. În mod similar, se creează, de asemenea, un număr mare de variante ale contractului fraudulos $m^{'}$ ${\ M displaystyle „}$ $eu$ . În cele din urmă, Oscar hashes toate aceste variante până când găsește o variantă a contractului corectă și o variantă a celui fraudulos, care au aceeași valoare hash, adică $f(m)=f(m')$ ${\ F displaystyle (m) = f (m „)}$ ${\ F displaystyle (m) = f (m „)}$ . În acest moment, Oscar prezintă Bob cu versiunea corectă pentru semnare. După ce Bob îl semnează, Oscar ia semnătura și acordă-o la contractul fraudulos. Acum semnătura „dovedește“ că Bob a semnat contractul fraudulos.

Acest mod de funcționare diferă puțin de paradoxul ziua de naștere original ca Oscar câștigă nimic de la obtinerea două contracte de drepturi sau două contracte frauduloase cu același hash. strategia optimă Oscar este aceea de a genera perechi formate dintr-un corectă și un singur contract fraudulos. Oscar compară fiecare pereche nou generat cu toți ceilalți, adică compară hash copia corect cu hash de toate copiile frauduloase anterioare, și noul contract fraudulos cu rosturi ale lemnului tuturor contractelor corecte anterioare (fără a se deranja să compare hash contract de frauduloase generate cu toate contractele de rosturi ale lemnului frauduloase anterioare, nici hash contractului corect generate cu toate contractele de rosturi ale lemnului corecte anterioare). Ecuațiile paradox ziua de nastere aplica cu n luând valoarea numărului de perechi (numărul de hashes care Oscar trebuie să genereze este 2n).

Pentru a evita acest atac, lungimea ieșirii unei funcții hash utilizate într - o schemă de semnătură digitală trebuie să fie suficient de mare , astfel încât atacul ziua de nastere devine computațional impracticabil: de obicei, suntem pe ordinea de două ori numărul de biți necesari pentru a preveni o clasic atac brute force.

Algoritmul rho Pollard este un exemplu de un algoritm care utilizează un atac de ziua de nastere pentru a calcula logaritmi discreți .

Notă

^ Jacques Patarin, Audrey Montreuil: Benes și Fluture scheme Revisited - 2005

Bibliografie

Mihir Bellare , Tadayoshi Kohno: Hash Funcția Balance și sa de impact asupra naștere Atacuri - EUROCRYPT 2004
Bruce Schneier : Criptografie Aplicată , ediția a doua

Elemente conexe

Meet-in-the-middle atac

linkuri externe

„Ce este o semnătură digitală și ceea ce este de autentificare?“ de la RSA criptografic FAQ
Michael Wiener și Paul C. van Oorschot: „căutare coliziune paralel cu aplicatii criptanalitice“

Portal de criptografie

Portal de securitate IT

[1] Jacques Patarin, Audrey Montreuil: Benes și Fluture scheme Revisited - 2005

[1]