Le funzioni di hash sono fondamentali nella crittografia e in altre applicazioni collegate ad essa. Matematicamente, una funzione di hash H calcola, a partire da un messaggio M di lunghezza arbitraria, un valore h di lunghezza fissata, ovvero
h = H(M)
Le funzioni di hash hanno alcune particolari proprietà:
- Sono deterministiche: ad uno stesso messaggio M deve restituire sempre lo stesso valore h
- Dato M, è facile calcolare h
- Dato h, è difficile calcolare M tale che H(M) = h
- Dato M, è difficile calcolare un altro messaggio M' tale che h = H(M) = H(M')
- È difficile calcolare due messaggi M e M' tali che H(M) = H(M')
Le funzioni di hash sono le colonne portanti della crittografia moderna e sono molto utili in molti altri ambiti, come:
- Verifica dell'autenticità dei file. Anche se non è sicuro come la firma digitale, è molto pratico e diffuso pubblicare su un sito web l'hash h di un file. L'utente, dopo aver scaricato il file può calcolare l'hash in modo indipendente con una utility e confrontarlo con quello pubblicato nel sito web per verificare la sua autenticità.
- Network P2P. Spesso è necessario scaricare un dato file condiviso da vari utenti. Ogni utente ha il file memorizzato sul suo hard disk, e a volte esso viene rinominato. Per capire se un utente ha in condivisione un determinato file, eventualmente con un altro nome, molti programmi P2P usano algoritmi di hash per verificare se corrisponde. Ad esempio, il programma EMule utilizza l'algoritmo MD4 mentre il programma BitTorrent usa un algoritmo di tipo SHA.
- Autenticazione. In molti casi un utente ottiene accesso ad un sistema inserendo la sua userID o username e la password. Nel caso di trasmissione dei dati attraverso una rete (ad esempio quando si consulta la posta elettronica) esiste la possibilità che qualcuno possa intercettare questi dati ed utilizzarli in modo non autorizzato. Poiché il sistema deve avere la certezza che l'utente conosca la password, si usa un espediente: l'utente trasmette la username e l'hash della password. Grazie alle proprietà degli algoritmi di hash di non poter risalire (facilmente), partendo dall'hash, ai dati che lo hanno generato, un eventuale intruso non può sapere la password. Il sistema, ricevuto il username, leggerà la password relativa, effettuerà l'hash e lo confronterà con quello ricevuto: se coincidono allora avverrà l'autenticazione.
- Strutture dati. Alcune strutture dati come le tabelle di hash (detti anche dizionari) utilizzano una funzione di hash associando ad un blocco di dati un valore detto chiave. In questo modo viene creata una coppia chiave-valore (key-value) e si possono recuperare i dati in modo efficiente.
- Firma digitale. La firma digitale consiste di una sequenza di dati cifrati che vengono associati ad un file. Tramite questi dati, chi riceve il file può essere sicuro che esso sia stato inviato da un particolare mittente. Brevemente, la firma digitale di un file viene generata calcolando l'hash di quel file e cifrando l'hash tramite la chiave privata del mittente (con un sistema di crittografia a chiave pubblica). Il destinatario verifica la firma decifrando l'hash cifrato con la chiave pubblica del mittente e ricalcolando l'hash del file: se i due valori coincidono allora il file è esattamente quello inviato dal mittente, perchè ogni modifica comporterebbe un valore di hash non coincidente.
Esempi
Si consideri il seguente messaggio che viene inviato da Alice a Bob: "Ciao Bob, ci vediamo domani alle 17". Questa stringa di caratteri avrà il codice hash seguente (calcolato con l'algoritmo MD5 e l'algoritmo SHA1):
- MD5: d94e3ef5498b0df805b7e3c7dca8a8e3
- SHA1: 1a323b738aa743bbfd3d251fa8e452abcc452fd4
Se si modifica di un solo carattere la stringa precedente, ad esempio facendo iniziare la frase con la lettera "c" minuscola: "ciao Bob, ci vediamo domani alle 17" si può notare che la stringa di hash muta completamente. La modifica riguarda solo un bit, poiché nel codice ASCII la lettera "C" maiuscola corrisponde al valore 67, in binario 01000011, e la lettera "c" minuscola al valore 99, in binario 01100011. I due caratteri differiscono solo nel terzo bit da sinistra.
- MD5: 129db8fc00a3751d60fc0d2013bfdcaa
- SHA1: e0a4ef60034668d012eb1372d51fc4a35e78f91b
Sicurezza
Il NIST ha pubblicato, nel documento SP800-57 [1], una valutazione della sicurezza necessaria per evitare la compromissione degli algoritmi di hash SHA. Essi sono infatti costituiti da un insieme di algoritmi, con una lunghezza del codice hash variabile da 160 bit a 512 bit. Chiaramente, maggiore è la lunghezza del codice prodotto, minore è la possibilità che si verifichi una collisione. Gli algoritmi SHA sono:
- Prima generazione: SHA1 (160 bit)
- Seconda generazione (famiglia SHA2): SHA224 (224 bit), SHA256 (256 bit), SHA384 (384 bit), SHA512 (512 bit)
- Terza generazione (famiglia SHA3): attualmente in fase di studio, la standardizzazione è prevista nel 2012
La valutazione sulla sicurezza è riassunta nella seguente tabella:
| 2010 | 2010 - 2030 | > 2030 | |
| SHA-1 | insufficiente1 | insufficiente | insufficiente |
| SHA-224 | buona | sufficiente | insufficiente |
| SHA-256 | buona | buona | sufficiente |
| SHA-384 | buona | buona | buona |
| SHA-512 | buona | buona | buona |
La National Security Agency statunitense ha stabilito l'impiego dell'algoritmo SHA per proteggere documenti classificati [2]:
| CONFIDENTIAL (livello 1) | SECRET (livello 2) | TOP SECRET (livello 3) | |
| SHA-256 | protezione adeguata | protezione adeguata | protezione non adeguata |
| SHA-384 | protezione adeguata | protezione adeguata | protezione adeguata |
