Hash chain
Una '''hash chain''' (letteralmente "catena di hash") è la ripetuta applicazione di una [[funzione crittografica di hash]] a un certo dato. Nella [[sicurezza informatica]], una hash chain è un metodo per produrre un insieme di chiavi di tipo ''[[One-time password|one-time]]'' partendo da una singola [[Chiave (crittografia)|chiave]] o [[password]].

== Definizione ==
Una hash chain è la successiva applicazione di una [[funzione crittografica di hash]] <math>h</math> ad una [[Stringa (informatica)|stringa]] <math>x</math>.

Per esempio,
:<math>h(h(h(h(x))))</math>
è una hash chain di lunghezza 4, solitamente denotata con <math>h^{4}(x)</math>.

== Applicazioni ==
[[Leslie Lamport]]<ref name="lamporthash">{{cita pubblicazione|lingua=en|autore=L. Lamport|titolo=Password Authentication with Insecure Communication|editore=Communications of the ACM 24.11|data=novembre 1981|pp=770-772|url=https://scholar.google.de/scholar?q=L.+Lamport%2C+%E2%80%9CPassword+Authentication+with+Insecure+Communication%E2%80%9D%2C+Communications+of+the+ACM+24.11+%28November+1981%29%2C+pp+770-772.+&btnG=&hl=de&num=20&as_sdt=0%2C5|doi=10.1145/358790.358797|urlmorto=sì}}</ref> suggerì l'uso di hash chain come schema di protezione per password in un ambiente insicuro. Un server che ha bisogno di [[Autenticazione|autenticarsi]] può salvare un'hash chain piuttosto che una password [[Testo puro|in chiaro]] in modo da prevenirne il furto dal server o durante la trasmissione.

Per esempio, su un server può essere inizialmente salvata la stringa <math>h^{1000}(\mathrm{password})</math>, fornita dall'utente. La prima volta che l'utente ha bisogno di autenticarsi, invia <math>h^{999}(\mathrm{password})</math> al server, il quale calcola <math>h(h^{999}(\mathrm{password})) = h^{1000}(\mathrm{password})</math> e verifica se il risultato corrisponde all'hash chain che aveva precedentemente salvato. Infine, salva <math>h^{999}(\mathrm{password})</math> per la prossima volta che l'utente avrà bisogno di autenticarsi.

Usando una buona [[funzione di hash]], un [[Attacco man in the middle|agente terzo]], pur essendo entrato in possesso della password <math>h^{999}(\mathrm{password})</math> già inviata al server, sarà comunque incapace di calcolare la password seguente (<math>h^{998}(\mathrm{password})</math>). Una funzione di hash sufficientemente sicura deve essere [[Funzione unidirezionale|unidirezionale]], ovvero, a partire dal valore di <math>h(x)</math> deve essere computazionalmente difficile risalire a <math>x</math> (nel caso specifico delle hash chain, <math>x</math> è la password da usare per la autenticazione successiva). Nell'esempio di cui sopra, l'hash chain è utilizzabile per autenticarsi al più mille volte.

== Hash tree ==
Gli hash tree (letteralmente "alberi di hash"), anche noti come [[Albero di Merkle|alberi di Merkle]], sono una generalizzazione di hash chain. Ogni nodo dell'albero è costituito da una funzione di hash binaria che prende due valori in ingresso e calcola l'hasing della loro [[concatenazione]].

Dimostrare che un [[Vertice (teoria dei grafi)|nodo]] foglia appartiene a un hash tree, noto il suo percorso all'interno dell'albero, richiede un numero di passaggi proporzionale al [[logaritmo]] del numero totale di foglie dell'albero stesso.<ref>{{Cita web |lingua=en |url=http://www.emsec.rub.de/media/crypto/attachments/files/2011/04/becker_1.pdf |titolo=Merkle Signature Schemes, Merkle Trees and Their Cryptanalysis |cognome=Becker |nome=Georg |data=18 luglio 2008 |editore=Ruhr-Universität Bochum |p=16 |formato=PDF |accesso=20 novembre 2013 |dataarchivio=22 dicembre 2014 |urlarchivio=https://web.archive.org/web/20141222120036/http://www.emsec.rub.de/media/crypto/attachments/files/2011/04/becker_1.pdf |urlmorto=sì }}</ref>

[[File:Hashtreehashchainjux.png|thumb|center|upright=3|Un esempio di hash tree con otto nodi foglia]]

=== Varianti ===
Una struttura simile all'hash tree può essere usata per risparmiare parte dello spazio di memoria destinato a salvare le password.<ref name="Janzadehetal">{{cita pubblicazione|autore1=H. Janzadeh|autore2=K. Fayazbakhsh|autore3=M. Dehghan|autore4=M. S. Fallah.|titolo=A secure credit-based cooperation stimulating mechanism for MANETs using hash chains|opera=Future Generation Computer Systems|volume=25|data=settembre 2009|pp=926-934|url=https://scholar.google.de/scholar?hl=de&num=20&as_sdt=0%2C5&q=A+secure+credit-based+cooperation+stimulating+mechanism+for+MANETs+using+hash+chains&btnG=|doi=10.1016/j.future.2008.12.002|lingua=en|urlmorto=sì}}</ref>

Per esempio, supponiamo che un certo protocollo per [[Mobile ad-hoc network|reti ad hoc mobili]] preveda che l'utente debba salvare l'intera hash chain <math>H_i=(h^0(x),h^2(x),\dots,h^n(x))</math> per ogni interazione con altri utenti. Con <math>p</math> interazioni dovrebbe salvare un vettore di hash chain <math>H=(H_0,H_1,\dots,H_p)</math>.<ref name="Janzadehetal"/> Tale matrice occuperebbe uno spazio direttamente proporzionale al prodotto <math>n \cdot p</math>.

Tuttavia usando due funzioni di hash distinte <math>h_1</math> e <math>h_2</math>, la quantità di memoria necessaria può essere notevolmente ridotta. Costruendo un [[albero binario]] in cui si userà la funzione <math>h_1</math> per passare da un nodo al proprio figlio destro e la funzione <math>h_2</math> per passare al sinistro, detta <math>d</math> la profondità dell'albero costruito, si potranno salvare <math>2^d</math> hash chain distinte,<ref name="Janzadehetal"/> una per ogni percorso che va dalla radice a una foglia diversa. Di conseguenza, per salvare una matrice di hash <math>n \times p</math>, si potrà usare uno spazio <math>O(log_2(np))</math>.

== Note ==
<references/>

== Voci correlate ==
* [[Challenge–response authentication]]
* [[Hash list]]
* [[One-time password]]
* [[Key stretching]]
* [[Linked timestamping]]

{{portale|sicurezza informatica}}

[[Categoria:Hash crittografici]]