Hash chain: differenze tra le versioni

Versione delle 20:17, 31 mar 2023

Versione attuale delle 22:28, 28 mag 2023

Riga 13:

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 ==

Riga 27:

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 ==