Apri il menu principale

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.

DefinizioneModifica

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

Per esempio,

 

è una hash chain di lunghezza 4, solitamente denotata con  .

ApplicazioniModifica

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  , fornita dall'utente. La prima volta che l'utente ha bisogno di autenticarsi, invia   al server, il quale calcola   e verifica se il risultato corrisponde all'hash chain che aveva precedentemente salvato. Infine, salva   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   già inviata al server, sarà comunque incapace di calcolare la password seguente ( ). Una funzione di hash sufficientemente sicura deve essere unidirezionale, ovvero, a partire dal valore di   deve essere computazionalmente difficile risalire a   (nel caso specifico delle hash chain,   è la password da usare per la autenticazione successiva). Nell'esempio di cui sopra, l'hash chain è utilizzabile per autenticarsi al più mille volte.

Hash treeModifica

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

VariantiModifica

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   per ogni interazione con altri utenti. Con   interazioni dovrebbe salvare un vettore di hash chain  .[3] Tale matrice occuperebbe uno spazio direttamente proporzionale al prodotto  .

Tuttavia usando due funzioni di hash distinte   e  , la quantità di memoria necessaria può essere notevolmente ridotta. Costruendo un albero binario in cui si userà la funzione   per passare da un nodo al proprio figlio destro e la funzione   per passare al sinistro, detta   la profondità dell'albero costruito, si potranno salvare   hash chain distinte,[3] una per ogni percorso che va dalla radice a una foglia diversa. Di conseguenza, per salvare una matrice di hash  , si potrà usare uno spazio  .

NoteModifica

  1. ^ (EN) L. Lamport, Password Authentication with Insecure Communication[collegamento interrotto], Communications of the ACM 24.11, novembre 1981, pp. 770-772, DOI:10.1145/358790.358797.
  2. ^ (EN) Georg Becker, Merkle Signature Schemes, Merkle Trees and Their Cryptanalysis (PDF), Ruhr-Universität Bochum, 18 luglio 2008, p. 16. URL consultato il 20 novembre 2013.
  3. ^ a b c (EN) H. Janzadeh, K. Fayazbakhsh, M. Dehghan e M. S. Fallah., A secure credit-based cooperation stimulating mechanism for MANETs using hash chains [collegamento interrotto], in Future Generation Computer Systems, vol. 25, settembre 2009, pp. 926-934, DOI:10.1016/j.future.2008.12.002.

Voci correlateModifica