Le funzioni hash sono particolari funzioni che permettono di dare a un messaggio un’impronta digitale tale da identificarlo univocamente. In altre parole creano una stringa associata al messaggio da spedire e per il quale, una volta applicata la funzione, non dovrebbe essere più possibile ritornare al testo originale.
Quindi, il valore hash h(M) è una rappresentazione non ambigua e non falsificabile di un messaggio M, facile da calcolare e tale da comprimere il messaggio stesso.
Una delle sue maggiori applicazioni si ha nell’utilizzo delle firme digitali: se si deve firmare un messaggio di grosse dimensioni, si firma il suo hash, in modo da avere un messaggio più piccolo. Permettono, inoltre, di avere integrità dei dati: ad esempio, a un certo tempo T si computa l’hash di un file M, H = h(M) e, successivamente, per controllare se il file è stato modificato si calcola h(M’) e si verifica se H = h(M’). Quindi h(M) è l’impronta digitale del file.

In generale, le funzioni hash vengono sfruttate anche in tanti altri scenari, ad esempio nella realizzazione di servizi di timestamping (marcatura temporale di documenti digitali), o nella realizzazione del MAC (Message Authentication Code), per dare autenticità ai messaggi.

Tra le principali proprietà delle funzioni hash ricordiamo che: sono facili da calcolare, godono della proprietà di sicurezza forte (è computazionalmente difficile trovare 2 messaggi diversi con lo stesso valore hash), godono della proprietà di sicurezza debole (dato M, è computazionalmente difficile trovare M’ tale che h(M) = h(M’)), e sono One-way, cioè, dato y è computazionalmente difficile trovare M tale che y = h(M).

Per poter costruire una funzione hash si possono comporre più funzioni hash, oppure si possono usare modelli per funzioni hash iterate o, ancora, si possono usare tecniche basate su cifrari a blocchi.

Le principali funzioni hash presenti attualmente sono:

• MD2: acronimo di Message Digest Algorithm, produce un valore hash di 128 bit e richiede come input multipli di 16 byte. La funzione, inoltre, usa un padding, cioè aggiunge dei bit mancanti ai messaggi in input che non hanno la lunghezza giusta. Questo algoritmo è già stato violato.
• MD4: anche questa funzione usa hash a 128 bit, ma è più veloce di MD2. Processa il messaggio dividendolo in blocchi di 512 bit. Il padding del messaggio, inoltre, comprende un valore di 64 bit che indica la lunghezza del messaggio originale. Questa funzione è piu sicura della precedente, in quanto la difficoltà di produrre due messaggi che hanno la stessa lunghezza con modulo 2^64 è maggiore.
• MD5: è stato ideato dopo la violazione di MD4, su cui è basato. Il testo è diviso in blocchi 512 bit e viene generato un hash di 128 bit. E’ basto su XOR e operazioni logiche. L’unico svantaggio è dovuto dal fatto che è un po’ più lento di MD4.
• RIPEMD: sviluppata dal progetto European RIPE, i cui autori hanno scoperto collisioni per una sua versione, in due casi. L’algoritmo originale è stato successivamente migliorato con RIPEMD/160, che utilizza output di 160, 256 o 320 bit.
• SHA-1: acronimo di Secure Hash Algorithm-1 (anche SHS, Secure Hash Standard), sviluppato dal NSA su richiesta del NIST (National Institute of Standard and Technology). Utilizza gli stessi principi di MD4 e MD5. Il progetto originale del 1994 aveva il nome di SHA, poi modificato nel codice dal NSA. Produce output di 160 bit a partire da una lunghezza arbitraria. Attualmente è uno dei più sicuri, usato anche dai servizi PGP e GPG per firmare documenti.
• SHA-2: versione successiva a SHA-1, genera impronte di documenti da 256, 384 e 512 bit.
• SNEFRU: sviluppata da Ralph Merkle. La versione denominata 2-round, è stata violata e attualmente esiste SNEFRU 4-round. Produce output di 128 o 256 bit.

Tra le altre ricordiamo: HAVAL, FFT-hash I, FFT-hash II, MDC-2 basata sul DES.