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 partendo da una singola chiave o password.

Definizione modifica

Una hash chain è la successiva applicazione di una funzione crittografica di hash $h$ ad una stringa $x$ .

Per esempio,

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

è una hash chain di lunghezza 4, solitamente denotata con $h^{4}(x)$ .

Applicazioni modifica

Leslie Lamport^[1] suggerì l'uso di hash chain come schema di protezione per password in un ambiente insicuro. Un server che ha bisogno di autenticarsi può salvare un'hash chain piuttosto che una password 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 $h^{1000}(\mathrm {password} )$ , fornita dall'utente. La prima volta che l'utente ha bisogno di autenticarsi, invia $h^{999}(\mathrm {password} )$ al server, il quale calcola $h(h^{999}(\mathrm {password} ))=h^{1000}(\mathrm {password} )$ e verifica se il risultato corrisponde all'hash chain che aveva precedentemente salvato. Infine, salva $h^{999}(\mathrm {password} )$ per la prossima volta che l'utente avrà bisogno di autenticarsi.

Usando una buona funzione di hash, un agente terzo, pur essendo entrato in possesso della password $h^{999}(\mathrm {password} )$ già inviata al server, sarà comunque incapace di calcolare la password seguente ( $h^{998}(\mathrm {password} )$ ). Una funzione di hash sufficientemente sicura deve essere unidirezionale, ovvero, a partire dal valore di $h(x)$ deve essere computazionalmente difficile risalire a $x$ (nel caso specifico delle hash chain, $x$ è 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 modifica

Gli hash tree (letteralmente "alberi di hash"), anche noti come 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 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.^[2]

Un esempio di hash tree con otto nodi foglia

Varianti modifica

Una struttura simile all'hash tree può essere usata per risparmiare parte dello spazio di memoria destinato a salvare le password.^[3]

Per esempio, supponiamo che un certo protocollo per reti ad hoc mobili preveda che l'utente debba salvare l'intera hash chain $H_{i}=(h^{0}(x),h^{2}(x),\dots ,h^{n}(x))$ per ogni interazione con altri utenti. Con $p$ interazioni dovrebbe salvare un vettore di hash chain $H=(H_{0},H_{1},\dots ,H_{p})$ .^[3] Tale matrice occuperebbe uno spazio direttamente proporzionale al prodotto $n\cdot p$ .

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