Hash

La funzione di hash è una funzione non invertibile che mappa una stringa di lunghezza arbitraria in una stringa di lunghezza definita, detta digest o hash. Il digest non permette di ottenere la stringa originale. La stringa può essere composta da qualsiasi tipo di dato (caratteri, numeri, oggetti, ecc.) ma a basso livello viene considerata sempre come una stringa di bit.

Cenni matematici

Una funzione non invertibile è una funzione  per cui non esiste una funzione  inversa.

Nello specifico la funzione di hash è non invertibile, questo perché è fatta in modo tale che il codominio B, che rappresenta le stringhe di una certa dimensione fissa, è molto più piccolo del dominio A (che invece contiene tutte le stringhe di lunghezza arbitraria) e quindi allo stesso digest corrisponde più di una stringa originale.

La funzione di hash ha lo scopo di trasformare una certa stringa in una più corta e di dimensione fissa ma più piccola da memorizzare e più veloce da confrontare. 

Facciamo un esempio. Come dominio abbiamo tutte le stringhe fino a 40 caratteri che possono essere chiave di un progetto. Come codominio definiamo quello delle stringhe di lunghezza di 6 caratteri.

Ipotizziamo di avere due chiavi:

• “progetto-prenotazioni-bianchi-barilla-23-24”

• “progetto-prenotazioni-ospedale-verdi-bartolomei-23-24“,

che hanno rispettivamente come hash

• “42defg”

• “67sde2“

tramite opportuna funzione di hash che riduce i 40 caratteri in uno spazio di 6. 

Si tratta di una compressione dell’informazione e quindi in teoria molte stringhe del dominio potrebbero avere potenzialmente lo stesso hash nel codominio e quindi potrebbero esserci in teoria collisioni. Infatti il dominio ha una dimensione di 32⁴⁰ ed il codominio di 32⁶.^[1]

Tuttavia in realtà le combinazioni di caratteri realmente utilizzate nel mondo reale sono solo una infinitesima parte del dominio (formato da tutte le combinazioni possibili di caratteri) e quindi il rischio di collisioni è praticamente nullo. Questo è reso possibile anche grazie al fatto che la funzione di hash è fatta in modo tale da rendere l’hash di due stringhe quasi identiche molto differente.^[2] perché lavora a livello di bit e non di carattere.

Utilizzi della funzione di hash

– verifica dell’integrità di un messaggio o di un file: in sicurezza informatica il mittente invia tramite due canali diversi un messaggio ed il suo digest. Il ricevente ricevere il messaggio ne rigenera il digest e lo confronta con quello ricevuto.;

– autenticazione dell’identità: viene criptato solo il digest di un testo, per ragioni prestazionali;

– generazione di chiavi di un dizionario: le chiavi piccole di dimensione fissa sono più facili da cercare ed occupano meno spazio;

– generazione di token da password: per generare una password OTP (es. banca) normalmente si esegue un digest di una stringa composta da una password e un timestamp.

---

^[1] 32 è la dimensione in bit della codifica di un carattere in un moderno sistema operativo.

^[2] Questo è ottenuto tramite una complessa serie di operazioni and, or, xor tra gruppi di bit della stringa originale, per cui anche solo un bit di differenza tra due stringhe originali produce un hash completamente diverso.