Hash
Da Wikipedia, l'enciclopedia libera.
Hash ("to hash" sminuzzare, pasticciare) è un termine della lingua inglese 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 scientifico, l'hash è una funzione univoca operante in un solo senso (ossia, che non può essere invertita), atta alla trasformazione di un testo di lunghezza arbitraria in una stringa di lunghezza fissa, relativamente limitata. Tale stringa rappresenta una sorta di "impronta digitale" del testo in chiaro, e viene detta valore di hash, checksum crittografico o message digest.
In informatica, la funzione di trasformazione che genera l'hash opera sui bit di un file qualsiasi, restituendo una stringa di bit di lunghezza predefinita. Spesso il nome della funzione di hash include il numero di bit che questa genera: ad esempio, SHA-256 genera una stringa di 256 bit. L'Hash table è invece una struttura dati.
Indice |
[modifica] Algoritmo di Hash
L'algoritmo di "Hash" elabora qualunque mole di bit (in informatica si dice "digerisce tutto ciò che gli viene dato in pasto"). Si tratta di una famiglia di algoritmi che soddisfa questi requisiti:
1) L'algoritmo restituisce una stringa di numeri e lettere a partire da un qualsiasi flusso di bit di qualsiasi dimensione (può essere un file ma anche una stringa). L'output è detto Digest.
2) La stringa di output è univoca per ogni documento e ne è un identificatore. Perciò, l'algoritmo è utilizzabile per la firma digitale.
3) L'algoritmo non è invertibile, ossia non è possibile ricostruire il documento originale a partire dalla stringa che viene restituita in output.
[modifica] Hash e collisioni
Non esiste una corrispondenza biunivoca tra l'hash e il testo. Dato che i testi possibili, con dimensione finita maggiore dell'hash, sono più degli hash possibili, per il principio dei cassetti ad almeno un hash corrisponderanno più testi possibili. Quando due testi producono lo stesso hash, si parla di collisione, 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 algoritmi SNEFRU, MD2, MD4 ed MD5.
Un hash crittograficamente sicuro non dovrebbe permettere di risalire, in un tempo congruo con la dimensione dell'hash, ad un testo che possa generarlo (che per i più resistenti è, attualmente, superiore alla durata dell'universo, applicando tutta la capacità computazionale immaginabile).
[modifica] Applicazioni
[modifica] Hash e crittografia
La lunghezza dei valori di hash varia a seconda degli algoritmi utilizzati. Il valore più comunemente adottato è di 128 bit, 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ò va fortemente sconsigliato).
Le funzioni hash svolgono un ruolo essenziale nella crittografia: sono utili per verificare l'integrità di un messaggio, poiché l'esecuzione dell'algoritmo su un testo anche minimamente modificato fornisce un message 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 di firme 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 di crittografia asimmetrica su moli di dati molto grandi.
La firma digitale è definita come il Digest di un documento 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 il Digest iniziale, 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 o passphrase: a partire da un valore arbitrario in ingresso (una stringa o un array 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 un salt crittografico), l'utilità di questa procedura è esclusivamente pratica: infatti la sicurezza della chiave derivata è equivalente a quella della stringa di ingresso ai fini di un attacco a dizionario. Di contro, è certamente più comodo per un essere umano ricordare una stringa piuttosto che una lunga sequenza numerica.
[modifica] Hash e basi di dati
È possibile utilizzare le funzioni di hash per creare una hash table: struttura dati molto efficiente per immagazzinare generici dati associati ad una chiave.
[modifica] Correzione degli errori
L'uso delle funzioni hash per trovare errori nelle trasmissioni è molto comune. La funzione hash viene calcolata a partire dai dati dal trasmettitore e il suo valore è inviato insieme ai dati. Il ricevitore calcola di nuovo la funzione hash, e se i valori hash non corrispondono, significa che è avvenuto un errore durante la trasmissione. Questo metodo è chiamato controllo ridondante.
[modifica] Hash uniforme semplice
Si definisce Hash uniforme semplice quel tipo Hash in cui l'estrazione degli elementi in U è casuale, e la funzione hash
h: U -> {m}
estrae la chiave m_i con probabilità 1 / | m |
In tali condizioni la ricerca della chiave avrà complessità costante O(1).
[modifica] Elenco di hash e documenti correlati
MD2
- RFC1319 - The MD2 Message-Digest Algorithm
MD4
- RFC1320 - The MD4 Message-Digest Algorithm
- RFC1321 - The MD5 Message-Digest Algorithm
- RFC1810 - Report on MD5 Performance
- RFC1828 - IP Authentication using Keyed MD5
- [1] - Modification Detection Code
- FIPS PUB 180-1 - SECURE HASH STANDARD
- RFC3174 - US Secure Hash Algorithm 1 (SHA1)
- RFC1852 - IP Authentication using Keyed
SHA-2 (256, 384, 512)
- DFIPS PUB 180-2 - SECURE HASH STANDARD
RIPEMD-160
- The RIPEMD-160 Home Page
PANAMA
TIGER
CRC32 (attenzione: non è corretto considerare CRC32 un algoritmo di hash crittografico)
- RFC1952 - GZIP file format specification version 4.3
ADLER32
- RFC1950 - ZLIB Compressed Data Format Specification version 3.3
HMAC (attenzione: HMAC non è propriamente una funzione di hash, poiché per eseguirlo è necessario non solo il testo in chiaro, ma anche una chiave. Gli algoritmi di hash richiedono un unico parametro di ingresso)
- FIPS PUB 198 - The Keyed-Hash Message Authentication Code (HMAC)
- RFC2104 - HMAC: Keyed-Hashing for Message Authentication
- RFC2202 - Test Cases for HMAC-MD5 and HMAC-SHA-1
- RFC2286 - Test Cases for HMAC-RIPEMD160 and HMAC-RIPEMD128
- RFC2085 - HMAC-MD5 IP Authentication with Replay Prevention
- RFC2403 - The Use of HMAC-MD5-96 within ESP and AH
- RFC2404 - The Use of HMAC-SHA-1-96 within ESP and AH
- RFC2857 - The Use of HMAC-RIPEMD-160-96 within ESP and AH
- RFC2085 - HMAC-MD5 IP Authentication with Replay Prevention
[modifica] Voci correlate
[modifica] Collegamenti esterni
- (EN) Definizione inglese del termine
- (EN) Hash'em all!, per calcolare online l'hash di stringhe e files
Portale Matematica: accedi alle voci di Wikipedia che parlano di matematica
