Le funzioni hash sono uno degli strumenti più usati in informatica, e hanno moltissime applicazioni che ci aiutano a capire come funziona la rete.
In inglese “hash” significa “pasticcio”. Ed è proprio così che dobbiamo immaginare una funzione hash, cioè come una specie di tritacarne:
Una funzione hash funziona essenzialmente come un tritacarne
La carne in ingresso è un qualsiasi file, cioè una qualsiasi sequenza di $0$ e $1$, e quello che esce fuori è un pasticcio (“hash”) del file iniziale, cioè un qualcosa di “irriconoscibile”.
In particolare, in termini più precisi una funzione hash:
- Prende in ingresso file (una sequenza di $0$ e $1$) di qualsiasi dimensione e sputa fuori un numero di lunghezza fissa, indipendente dalla lunghezza del file iniziale.
- Se il file iniziale viene modificato anche solo di poco, l’hash “cambia molto”, cioè è caotico.
- È praticamente irreversibile, cioè è difficile capire da quale sequenza iniziale proviene quale hash.
- È difficile trovare due sequenze che diano lo stesso hash (sebbene esistano per forza: ci sono molti più file possibili che hash possibili, per la proprietà 1), ovvero è resistente alle collisioni.
Queste proprietà non sono precise: dipendono da ciò che si intende per “difficile”, o “cambiare molto” e infatti ciò cambia col tempo, ad esempio perché aumenta la potenza di calcolo, e qualcosa di difficile può diventare facile. Possiamo esaminare queste proprietà facendo riferimento ad una delle più famose funzioni hash, md5. Utilizziamo un calcolatore online di pasticci, ops di hash.
Proviamo ad esempio la proprietà 1:
ciao -> 6e6bc4e49dd477ebc98ef4046c067b5f Nel mezzo del cammin di nostra vita -> cb9d3598141c8445a3ba97d73139697a
Ovvero applicare la funzione md5 alla stringa “ciao” dà come risultato quel numero lì, e stessa cosa per l’incipit dantesco. Se anche avessimo messo dentro un file di 4GB avremmo ottenuto lo stesso una sequenza numerica della stessa lunghezza. Notiamo che le lettere dell’alfabeto nell’hash indicano in realtà numeri, perché per risparmiare spazio gli hash si scrivono in esadecimale.
Proviamo la proprietà 2. Abbiamo detto:
Nel mezzo del cammin di nostra vita -> cb9d3598141c8445a3ba97d73139697a
Ora facciamo un cambiamento minimo:
Nel mezzo del cammin di nostra vite -> f8947f4dea59fc0dcfd261fd94450230
Che è evidentemente molto diverso, nonostante sia impreciso cosa significhi “molto diverso”.
Per quanto riguarda le proprietà 3 e 4, significano che non c’è nessun modo “facile” per recuperare il file iniziale dato l’hash. In termini concreti, questo significa che il modo più efficace per farlo è quello di calcolare l’hash di file a caso finché non si ottiene l’hash desiderato. Se si costruisce bene la funzione hash, questo garantisce che per “craccare” l’hash (cioè per trovare la sequenza che da quell’hash) in media ci voglia un tempo enorme ed è quindi “praticamente” impossibile.
Bisogna però tenere a mente che tutti gli algoritmi hanno le loro vulnerabilità in base al modo in cui sono costruiti, e queste vulnerabilità possono essere sfruttate per violare le proprietà 3 e 4. Ad esempio oggi giorno l’md5 è considerato obsoleto, perché è relativamente facile generare collisioni (cioè trovare due sequenze che danno lo stesso hash), cioè è facile violare la proprietà 4. Di solito oggi si usa l’algoritmo SHA.
Ma a che serve una funzione hash? Due esempi:
- Per proteggere le password. Quando vi iscrivete ad un sito internet e inserite nome utente e password, il sito salva in una tabella il nome utente e l’hash della password. Poi quando vi autenticate, il sito calcola l’hash della password che avete inviato e la confronta con quella della tabella. Perché? Perché in questo modo se qualcuno viola il sito web e ruba la tabella coi nomi utente, non ci farà niente! Questo è garantito dalle proprietà 3 e 4 di cui sopra, per cui anche avendo l’hash, è difficile recuperare la password.
- Per verificare l’integrità dei file. Quando scaricate un file molto grande, tipo 10GB, è possibile che ci sia stato un errore nel trasferimento per cui qualche 1 è stato erroneamente identificato come 0 o viceversa. Come facciamo a verificarlo? Calcoliamo il suo hash! Sul sito da cui abbiamo scaricato originariamente il file, spesso l’autore mette a disposizione l’hash del file corretto. Grazie alla proprietà 2, sappiamo che se il nostro file è diverso anche solo di poco, l’hash sarà diversissimo, e quindi possiamo controllare se il file scaricato è esattamente come quello dell’autore.
Ma come si costruisce una funzione hash? Per costruire una funzione vera e propria si usano algoritmi estremamente complessi. Qui propongo un metodo semplice che da un’idea di come sia possibile costruire una funzione pasticcio, ma è fallata da moltissimi punti di vista.
La prima idea è facilissima: immaginate che vi sia dato un numero qualsiasi. L’hash di questo numero è lo stesso numero modulo $100$. (ovvero: continuate a togliere $100$ finché il numero non è minore di $100$)
Ad esempio, l’hash di $5142$ è $42$. Ora questa funzione rispetta la proprietà $1$ (se il numero è da $0$ a $9$ basta aggiungere uno 0 davanti), ma non rispetta affatto le proprietà $2$, $3$ e $4$. L’hash di $5143$ è $43$, che è molto simile a $42$ (quindi non rispetta la proprietà $2$). Dato $42$, sappiamo subito che sia $42$ che $142$ danno come hash $42$, e quindi le proprietà $3$ e $4$ non sono rispettate. Ci serve qualcosa di meglio.
La seconda idea è anch’essa facile: l’hash di $n$ è $2^n \,\,(\mathrm{mod}\, 100)$. Ora ad esempio l’hash di $5142$ è $2^{5142} \,\,(\mathrm{mod}\, 100) = 4$, mentre l’hash di $5143$ è $8$, che non è troppo diverso ma è meglio di prima. Inoltre è più complicato esibire il numero che da un certo hash (anche se non è ancora sufficientemente difficile). Otterremmo risultati leggermente migliori scegliendo di calcolare il modulo rispetto ad un numero primo, ma niente di eccezionale.
Le funzioni di hash utilizzate in pratica adottano metodi notevolmente più complessi. Ciò che dobbiamo portare a casa è che una funzione hash non è un concetto esatto, ma si basa sulla difficoltà di compiere due operazioni: invertire la funzione stessa e trovare due numeri che danno lo stesso hash. E “difficoltà” dipende essenzialmente da quanto sono potenti i pc che abbiamo a disposizione.