Lanț de haș

Un lanț hash (literal „lanț hash”) este aplicarea repetată a unei funcții hash criptografice la anumite date. În securitatea cibernetică , un lanț de distribuire este o metodă de producere a unei o singură dată set de chei de la o singură tastă sau o parolă .

Definiție

Un lanț hash este aplicarea ulterioară a unei funcții hash criptografice $h$ ${\ displaystyle h}$ $h$ la un șir $X$ ${\ displaystyle x}$ $X$ .

De exemplu,

h(h(h(h(x))))

{\ displaystyle h (h (h (h (x))))}}

{\ displaystyle h (h (h (h (x))))}

este un lanț hash de lungime 4, de obicei notat cu $h^{4}(x)$ ${\ displaystyle h ^ {4} (x)}$ ${\ displaystyle h ^ {4} (x)}$ .

Aplicații

Leslie Lamport ^{[1] a} sugerat utilizarea lanțurilor de hash ca sistem de protecție a parolei într-un mediu nesigur. Un server care trebuie să se autentifice poate salva un lanț hash mai degrabă decât o parolă în text simplu pentru a preveni furarea acestuia de pe server sau în timpul transmiterii.

De exemplu, șirul poate fi salvat inițial pe un server $h^{1000}(\mathrm {password} )$ ${\ displaystyle h ^ {1000} (\ mathrm {parolă})}$ ${\ displaystyle h ^ {1000} (\ mathrm {parolă})}$ , furnizat de utilizator. Prima dată când utilizatorul trebuie să se autentifice, trimite $h^{999}(\mathrm {password} )$ ${\ displaystyle h ^ {999} (\ mathrm {parolă})}$ ${\ displaystyle h ^ {999} (\ mathrm {parolă})}$ la server, care calculează $h(h^{999}(\mathrm {password} ))=h^{1000}(\mathrm {password} )$ ${\ displaystyle h (h ^ {999} (\ mathrm {password})) = h ^ {1000} (\ mathrm {password})}$ ${\ displaystyle h (h ^ {999} (\ mathrm {password})) = h ^ {1000} (\ mathrm {password})}$ și verificați dacă rezultatul se potrivește cu lanțul hash pe care îl salvase anterior. În cele din urmă, salvați $h^{999}(\mathrm {password} )$ ${\ displaystyle h ^ {999} (\ mathrm {parolă})}$ ${\ displaystyle h ^ {999} (\ mathrm {parolă})}$ pentru data viitoare utilizatorul va trebui să se autentifice.

Folosind o funcție hash bună, un agent terț , în ciuda faptului că a deținut parola $h^{999}(\mathrm {password} )$ ${\ displaystyle h ^ {999} (\ mathrm {parolă})}$ ${\ displaystyle h ^ {999} (\ mathrm {parolă})}$ trimis deja la server, acesta nu va putea calcula următoarea parolă ( $h^{998}(\mathrm {password} )$ ${\ displaystyle h ^ {998} (\ mathrm {parolă})}$ ${\ displaystyle h ^ {998} (\ mathrm {parolă})}$ ). O funcție hash suficient de sigură trebuie să fie unidirecțională , adică începând cu valoarea lui $h(x)$ ${\ displaystyle h (x)}$ $h (x)$ trebuie să fie dificil din punct de vedere al calculului să se regăsească înapoi $X$ ${\ displaystyle x}$ $X$ (în cazul specific al lanțurilor de hash, $X$ ${\ displaystyle x}$ $X$ este parola de utilizat pentru autentificarea ulterioară). În exemplul de mai sus, lanțul hash poate fi utilizat pentru autentificare de cel mult o mie de ori.

Hash tree

Copacii Hash, cunoscuți și sub numele de arbori Merkle , sunt o generalizare a lanțurilor de hash. Fiecare nod al arborelui este alcătuit dintr-o funcție hash binară care ia două valori de intrare și calculează hasing-ul concatenării lor.

Demonstrarea faptului că un nod de frunze aparține unui arbore hash, cunoscând calea sa în interiorul arborelui, necesită un număr de pași proporționali cu logaritmul numărului total de frunze din arborele în sine. ^[2]

Un exemplu de copac hash cu opt noduri de frunze

Variante

O structură de tip arbore hash poate fi utilizată pentru a salva o parte din spațiul de memorie destinat stocării parolelor. ^[3]

De exemplu, să presupunem că un anumit protocol pentru rețelele mobile ad hoc necesită ca utilizatorul să salveze întregul lanț hash $H_{i}=(h^{0}(x),h^{2}(x),\dots ,h^{n}(x))$ ${\ displaystyle H_ {i} = (h ^ {0} (x), h ^ {2} (x), \ dots, h ^ {n} (x))}$ ${\ displaystyle H_ {i} = (h ^ {0} (x), h ^ {2} (x), \ dots, h ^ {n} (x))}$ pentru orice interacțiune cu alți utilizatori. Cu $p$ ${\ displaystyle p}$ $p$ interacțiunile ar trebui să salveze un vector de lanț hash $H=(H_{0},H_{1},\dots ,H_{p})$ ${\ displaystyle H = (H_ {0}, H_ {1}, \ dots, H_ {p})}$ ${\ displaystyle H = (H_ {0}, H_ {1}, \ dots, H_ {p})}$ . ^[3] Această matrice ar ocupa un spațiu direct proporțional cu produsul $n\cdot p$ ${\ displaystyle n \ cdot p}$ ${\ displaystyle n \ cdot p}$ .

Cu toate acestea, folosind două funcții hash distincte $h_{1}$ ${\ displaystyle h_ {1}}$ $h_ {1}$ Și $h_{2}$ ${\ displaystyle h_ {2}}$ $h_ {2}$ , cantitatea de memorie necesară poate fi redusă semnificativ. Prin construirea unui copac binar în care funcția va fi utilizată $h_{1}$ ${\ displaystyle h_ {1}}$ $h_ {1}$ pentru a trece de la un nod la copilul și funcția potrivită $h_{2}$ ${\ displaystyle h_ {2}}$ $h_ {2}$ a merge în stânga, a spus $d$ ${\ displaystyle d}$ $d$ adâncimea arborelui construit, acestea pot fi salvate $2^{d}$ ${\ displaystyle 2 ^ {d}}$ ${\ displaystyle 2 ^ {d}}$ lanțuri de hash distincte, ^[3] unul pentru fiecare cale care merge de la rădăcină la o frunză diferită. În consecință, pentru a salva o matrice hash $n\times p$ ${\ displaystyle n \ times p}$ ${\ displaystyle n \ times p}$ , puteți utiliza un spațiu $O(log_{2}(np))$ ${\ displaystyle O (log_ {2} (np))}$ ${\ displaystyle O (log_ {2} (np))}$ .

Notă

^ (RO) L. Lamport, Autentificare parolă cu comunicare nesigură ^{[ link broken ]} , Comunicări ale ACM 24.11, noiembrie 1981, pp. 770-772, DOI : 10.1145 / 358790.358797 .
^ (EN) Georg Becker, Merkle Signature Schemes, Merkle Trees and Their Cryptanalysis (PDF) pe emsec.rub.de, Ruhr-Universität Bochum, 18 iulie 2008, p. 16. Accesat la 20 noiembrie 2013 .
^ ^a ^b ^c ( EN ) H. Janzadeh, K. Fayazbakhsh, M. Dehghan și MS Fallah., Un mecanism sigur de stimulare a cooperării bazat pe credit pentru MANET-uri care utilizează lanțuri de hash ^{[ link rupt ]} , în Future Generation Computer Systems , vol. 25, septembrie 2009, pp. 926-934, DOI : 10.1016 / j.future.2008.12.002 .

Elemente conexe

Portal de securitate cibernetică : accesați intrările Wikipedia care se ocupă de securitatea cibernetică

[lamporthash-1] (RO) L. Lamport, Autentificare parolă cu comunicare nesigură ^{[ link broken ]} , Comunicări ale ACM 24.11, noiembrie 1981, pp. 770-772, DOI : 10.1145 / 358790.358797 .

[2] (EN) Georg Becker, Merkle Signature Schemes, Merkle Trees and Their Cryptanalysis (PDF) pe emsec.rub.de, Ruhr-Universität Bochum, 18 iulie 2008, p. 16. Accesat la 20 noiembrie 2013 .

[Janzadehetal-3] ( EN ) H. Janzadeh, K. Fayazbakhsh, M. Dehghan și MS Fallah., Un mecanism sigur de stimulare a cooperării bazat pe credit pentru MANET-uri care utilizează lanțuri de hash ^{[ link rupt ]} , în Future Generation Computer Systems , vol. 25, septembrie 2009, pp. 926-934, DOI : 10.1016 / j.future.2008.12.002 .

[1] a

[2]

[3]