Lafunzione di hash produce una sequenza dibit (o unastringa), dettadigest, strettamente correlata con i dati in ingresso. La parola deriva dal verbo ingleseto hash, ovvero sminuzzare, pasticciare, che designa originariamente una polpettina fatta di avanzi di carne e verdure; per estensione, indica un composto eterogeneo cui viene data una forma incerta: "To make a hash of something" vuol dire, infatti, creare confusione, o fare una cosa piuttosto male.
Nel linguaggio matematico e informatico, l'hash è unafunzione non invertibile che mappa unastringa di lunghezza arbitraria in una stringa di lunghezza predefinita. Esistono numerosi algoritmi che realizzano funzioni hash con particolari proprietà che dipendono dall'applicazione.
Nelleapplicazioni crittografiche si chiede, per esempio, che la funzione hash abbia le seguenti proprietà:
Nelle applicazioni dibasi di dati la funzione hash è usata per realizzare una particolarestruttura dati chiamatahash table. In questa applicazione non occorrono proprietà crittografiche e generalmente l'unica proprietà richiesta è che non ci siano hash più probabili di altri.
Si definisce hash uniforme semplice quel tipo Hash in cui l'estrazione degli elementi in U è casuale, e la funzione hash
estrae la chiave con probabilità
In tali condizioni la ricerca della chiave avrà complessità costante O(1).
L'algoritmo di hash elabora qualunque mole di bit (in informatica si dice che elabora dati "grezzi"). Si tratta di una famiglia di algoritmi che soddisfa questi requisiti:
Non esiste unacorrispondenza biunivoca tra l'hash e il testo. Dato che i testi possibili, con dimensione finita maggiore dell'hash, sono più degli hash possibili, per ilprincipio dei cassetti ad almeno un hash corrisponderanno più testi possibili. Quando due testi producono lo stesso hash, si parla dicollisione, e la qualità di una funzione di hash è misurata direttamente in base alla difficoltà nell'individuare due testi che generino una collisione. Per sconsigliare l'utilizzo di algoritmi di hashing in passato considerati sicuri è stato infatti sufficiente che un singolo gruppo di ricercatori riuscisse a generare una collisione. Questo è quello che è avvenuto ad esempio per gli algoritmiSNEFRU,MD2,MD4,MD5 eSHA-1.
Un hash crittograficamente sicuro non dovrebbe permettere di risalire, in un tempo confrontabile con l'utilizzo dell'hash stesso, ad un testo che possa generarlo.
Lo stesso argomento in dettaglio:Funzione crittografica di hash.La lunghezza dei valori di hash varia a seconda deglialgoritmi utilizzati. Il valore più comunemente adottato è di 128bit, che offre una buona affidabilità in uno spazio relativamente ridotto. Tuttavia va registrata la possibilità d'uso di hash di dimensione maggiore (SHA, ad esempio, può anche fornire stringhe di 224, 256, 384 e 512 bit) e minore (che però è fortemente sconsigliato).
Le funzioni hash svolgono un ruolo essenziale nellacrittografia: sono utili per verificare l'integrità di un messaggio, poiché l'esecuzione dell'algoritmo su un testo anche minimamente modificato fornisce unmessage digest completamente differente rispetto a quello calcolato sul testo originale, rivelando la tentata modifica.
Le funzioni di hash possono essere anche utilizzate per la creazione difirme digitali, in quanto permettono la rapida creazione della firma anche per file di grosse dimensioni, senza richiedere calcoli lunghi e complessi: è infatti computazionalmente più conveniente eseguire con rapidità un hashing del testo da firmare, e poi autenticare solo quello, evitando così l'esecuzione dei complessi algoritmi dicrittografia asimmetrica su moli di dati molto grandi.
Lafirma digitale è definita come ildigest di un documento che poi viene crittografato con chiave privata (e non con quella pubblica, come avviene di solito). La firma digitale è l'unico caso in cui l'uso delle chiavi è invertito: la chiave pubblica serve a decrittare la firma e trovare poi ildigest iniziale attraverso l'hash, mentre quella privata serve a crittografare una stringa anziché ad aprirla.
Un ulteriore uso delle funzioni di hash si ha nella derivazione di chiavi da password opassphrase: a partire da un valore arbitrario in ingresso (una stringa o unarray di larghe dimensioni) si deriva in modo crittograficamente sicuro (ovvero non è possibile abbreviare il calcolo con una qualche scorciatoia) una chiave di dimensioni adatte alla cifratura. È appena il caso di dire, tuttavia, che a meno di prendere debite contromisure (come l'uso di unsalt crittografico), l'utilità di questa procedura è esclusivamente pratica: infatti la sicurezza della chiave derivata è equivalente a quella della stringa di ingresso ai fini di unattacco a dizionario. Di contro, è certamente più comodo per un essere umano ricordare una stringa piuttosto che una lunga sequenza numerica.
Nel contesto delle funzioni hash, ci si riferisce a diversi concetti di sicurezza:
Questi due concetti di sicurezza vengono distinti anche per via degli effetti che essi possono produrre nel caso in cui ne siano privi: per quanto riguarda ad esempio la possibilità di effettuare una firma digitale, un algoritmo che non garantisca la sicurezza forte, ma quella debole, sarebbe comunque utile dal momento che il messaggio non può essere "controllato" e bisognerebbe quindi trovare un secondo messaggio con uguale funzione di hash, il che sarebbe appunto computazionalmente difficile.
È possibile utilizzare le funzioni di hash per creare unahash table, che è una struttura dati molto efficiente per le operazioni di ricerca. La hash table contiene dati associati ad una chiave di ricerca e viene spesso utilizzato neidatabase per indicizzare gli elementi che saranno oggetto di ricerca. Questa tecnica (detta di hashing) permette di realizzare funzioni di ricerca che riescono ad individuare l'elemento desiderato in un tempo costante, indipendente (almeno in teoria) dal numero di elementi presenti nell'indice.
L'uso delle funzioni hash per trovare errori nelle trasmissioni è molto comune. La funzione hash viene calcolata dal mittente a partire dai dati e il suo valore è inviato insieme ai dati. Il ricevente calcola di nuovo la funzione hash, e se i valori hash non corrispondono, significa che è avvenuto un errore durante la trasmissione. Questo metodo consente un controllo dell'integrità dei dati migliore della più tradizionalechecksum.
Gli algoritmi di hash, in particolareSHA1 eMD5, sono largamente utilizzati nell'ambito dell'informatica forense per validare e ottenere una 'impronta digitale' dei dati acquisiti, tipicamente lecopie forensi. La recente legislazione impone infatti una catena di custodia che permetta di preservare i reperti informatici da eventuali modifiche successive all'acquisizione: tramite i codici hash è possibile in ogni momento verificare che quanto repertato sia rimasto immutato nel tempo. Se i codici hash corrispondono, entrambe le parti in un procedimento giudiziario hanno la ragionevole certezza di lavorare sulla stessa versione dei reperti, garantendo quindi una uniformità di analisi e in genere di risultati. I risultati dei codici hash vengono ormai calcolati di default dalla maggioranza dei software per acquisizione forense e allegati alle copie forensi salvate.
Altri progetti
Wikiversità contiene risorse sullafunzione di hash
Wikimedia Commons contiene immagini o altri file sullafunzione di hash
| Funzioni crittografiche di Hash eCodici di autenticazione dei messaggi (MAC) | |
|---|---|
| Funzioni di hash principali | MD5 ·SHA-1 ·SHA-2 ·SHA-3 |
| Altre funzioni | BLAKE ·GOST ·HAS-160 ·HAVAL ·LM hash ·MDC-2 ·MD2 ·MD4 ·N-Hash ·RIPEMD ·RadioGatún ·Snefru ·Tiger ·Whirlpool |
| Algoritmi diMAC | DAA ·CBC-MAC ·HMAC ·OMAC/CMAC ·PMAC ·UMAC ·Poly1305-AES |
| Attacchi | Collisione hash ·Attacco del compleanno ·Attacco preimmagine ·Tabella arcobaleno ·Attacco del canale laterale ·Attacco a forza bruta |
| Varie | Effetto valanga ·Costruzione di Merkle-Damgård ·NESSIE ·NIST hash function competition |
| Portale Crittografia ·Progetto Crittografia ·Hash crittografici ·MAC | |
| Controllo di autorità | LCCN(EN) sh86004135 ·GND(DE) 4323071-4 ·BNF(FR) cb12103012b(data) |
|---|
