Algoritmi Hash

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à:

  1. Sono deterministiche: ad uno stesso messaggio M deve restituire sempre lo stesso valore h
  2. Dato M, è facile calcolare h
  3. Dato h, è difficile calcolare M tale che H(M) = h
  4. Dato M, è difficile calcolare un altro messaggio M' tale che h = H(M) = H(M')
  5. È 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:

  1. 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à.
  2. 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.
  3. 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.
  4. 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.
  5. 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
Bibliography
1. NIST, SP800-57 part 1, "Recommendation for Key Management – Part 1: General (Revised)", 2006, Sito web: http://csrc.nist.gov/publications/nistpubs/800-57/SP800-57-Part1.pdf
2. National Security Agency, "NSA Suite B Cryptography", novembre 2009, Sito web: http://www.nsa.gov/ia/programs/suiteb_cryptography/index.shtml
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License