Una funzione crittografica di hash, in informatica, è una classe speciale delle funzioni di hash, che dispone di alcune proprietà che la rendono adatta all'uso in crittografia.
Si tratta di un algoritmo matematico che mappa dei dati di lunghezza arbitraria (messaggio) in una stringa binaria di dimensione fissa chiamata valore di hash, ma spesso viene indicata anche con il termine inglese message digest (o semplicemente digest). Tale funzione di hash è progettata per essere unidirezionale (one-way), ovvero una funzione difficile da invertire: l'unico modo per ricreare i dati di input dall'output di una funzione di hash ideale è quello di tentare una ricerca di forza-bruta di possibili input per vedere se vi è corrispondenza (match). In alternativa, si potrebbe utilizzare una tabella arcobaleno di hash corrispondenti.
La funzione crittografica di hash ideale deve avere alcune proprietà fondamentali: deve identificare univocamente il messaggio, non è possibile che due messaggi differenti, pur essendo simili, abbiano lo stesso valore di hash; deve essere deterministico, in modo che lo stesso messaggio si traduca sempre nello stesso hash; deve essere semplice e veloce calcolare un valore hash da un qualunque tipo di dato; deve essere molto difficile o quasi impossibile generare un messaggio dal suo valore hash se non provando tutti i messaggi possibili. Tali caratteristiche permettono alle funzioni crittografiche di hash di trovare ampio utilizzo negli ambiti della sicurezza informatica, quali firme digitali, codici di autenticazione dei messaggi (MAC) e altre forme di autenticazione. Possono essere utilizzati anche come funzioni di hash ordinarie, per indicizzare i dati nelle tabelle di hash, per la rilevazione di impronte digitali, per rilevare dati duplicati o identificare in modo univoco i file e come checksum per rilevare la corruzione accidentale dei dati. Infatti, nei contesti di sicurezza informatica, i valori di hash crittografici sono talvolta chiamati «impronte digitali» o «checksum» anche se tutti questi termini hanno funzioni più generali con proprietà e scopi piuttosto diversi.
Proprietà La maggior parte delle funzioni di hash crittografiche è progettata per prendere in input una stringa di qualsiasi lunghezza e produrre in output un valore di hash di lunghezza fissa. Queste funzioni devono essere in grado di resistere a tutti gli attacchi basati sulla crittoanalisi: per fare questo, si definisce il livello di sicurezza di una funzione di hash crittografica facendo riferimento alle seguenti proprietà:
Resistenza alla preimmagineDato un valore di hash , deve essere difficile risalire ad un messaggio con . Questa proprietà deriva dal concetto di funzione unidirezionale. Funzioni che non dispongono di questa proprietà sono vulnerabili agli attacchi alla preimmagine. Resistenza alla preimmagine secondariaDato un messaggio , deve essere difficile trovare un secondo messaggio tale che . Funzioni che non dispongono di questa proprietà sono vulnerabili agli attacchi alla seconda preimmagine. Resistenza alle collisioniDati due messaggi e , deve essere difficile che i due messaggi abbiano lo stesso hash, quindi con . Tale coppia è chiamata collisione di hash crittografica. Questa proprietà a volte è indicata come forte resistenza alla collisione. La resistenza alla collisione implica una resistenza alla seconda preimmagine, ma non implica la resistenza alla preimmagine: rispetto a quest'ultimo, richiede un valore di hash almeno due volte più lungo, altrimenti le collisioni possono essere trovate da un attacco del compleanno. Queste proprietà implicano che un eventuale attacco non permetta di rimpiazzare o modificare un messaggio senza conseguenze sul risultante valore di hash. Pertanto, se due stringhe hanno lo stesso digest, si può essere fiduciosi nel pensare che siano identiche. In particolare, la resistenza alla seconda preimmagine dovrebbe impedire ad avversario maligno di elaborare un messaggio con lo stesso hash di un messaggio che l'avversario stesso non può controllare. La resistenza alla collisione, invece, impedisce all'attaccante di creare due messaggi distinti con lo stesso hash.
In pratica, una funzione hash è solo una resistenza alla seconda pre-immagine; motivo per cui è considerata insicura e, di conseguenza, non raccomandata per applicazioni reali. D'altra parte, la resistenza alle collisioni risulta insufficiente per molti usi pratici: oltre ad essa, non dovrebbe essere possibile per un avversario trovare due messaggi con digest sostanzialmente simili o poter dedurre informazioni utili del messaggio partendo dal suo valore di hash. Quindi una funzione crittografica di hash deve essere il più possibile simile a una funzione casuale (spesso chiamata oracolo random) rimanendo comunque deterministica e semplice da calcolare. Ciò esclude le funzioni SWIFFT, delle quali è dimostrato che sono rigorosamente resistenti alla collisione, sempre se si suppone che determinati problemi sui reticoli ideali siano computazionalmente difficili; se intese come funzioni lineari, non portano a soddisfare queste proprietà. Gli algoritmi di checksum, ad esempio, come CRC e altri controlli di ridondanza ciclici, poiché lineari, sono progettati per soddisfare requisiti molto più deboli essendo troppo facili da invertire e generalmente non sono adatti come funzioni di hash crittografiche.
È importante precisare però che, pur possedendo una funzione in grado di soddisfare tutti questi criteri, si può ancora andare incontro a delle proprietà indesiderate. Le funzioni crittografiche di hash attualmente usate sono vulnerabili agli attacchi di lunghezza-estensione: dati e , ma non , scegliendo un appropriato , un attaccante può calcolare , dove indica la concatenazione. Questa proprietà può essere utilizzata per rompere gli schemi di autenticazione ingenui basati sulle funzioni hash. La costruzione di HMAC lavora su questi tipi di problemi.
Grado di difficoltà Nella crittografia pratica, con il termine "difficile" in genere si intende "quasi certamente oltre la portata di un qualsiasi avversario al quale deve essere impedito di rompere il sistema finché la sicurezza del sistema venga ritenuta importante". Il significato del termine è quindi leggermente dipendente dall'applicazione, poiché lo sforzo che un agente maligno può dedicare al suo lavoro è di solito proporzionale al suo guadagno previsto. Tuttavia, dal momento che gli sforzi da parte dell'attaccante aumentano rapidamente con la lunghezza del digest, gioverebbe il sistema se ad esso venissero aggiunte alcune dozzine di bit, con la capacità di neutralizzare anche un vantaggio di un migliaio di volte nel potere di elaborazione.
Per messaggi brevi, come ad esempio le password, si può riuscire ad invertire un hash provando tutti i messaggi possibili nell'insieme ma, poiché le funzioni crittografiche di hash sono progettate per essere calcolate rapidamente, sono state sviluppate delle funzioni di derivazione della chiave che richiedono maggiori risorse di calcolo rendendo, di conseguenza, più difficili possibili attacchi di forza bruta.
In alcune analisi teoriche, "difficile" assume un significato matematico specifico, come "non risolvibile nel tempo polinomiale asintotico". Tali interpretazioni di difficoltà sono importanti nello studio di funzioni crittografiche di hash probabilmente sicure, ma solitamente non hanno corrispondenza nella sicurezza pratica. Ad esempio, si può notare come un algoritmo di tempo esponenziale può talvolta essere abbastanza veloce da rendere un attacco fattibile; d'altra parte, un algoritmo di tempo polinomiale, contrariamente a quello esponenziale, può risultare troppo lento per qualsiasi uso pratico.
Illustrazione Un'illustrazione del potenziale uso di un hash crittografico è la seguente: Alice pone un problema difficile di matematica a Bob, affermando di averlo risolto; Bob vorrebbe risolvere anche lui lo stesso problema, ma vorrebbe essere sicuro che Alice non stia bluffando; Alice scrive la sua soluzione, calcola il suo hash e lo riferisce a Bob (mantenendo la soluzione segreta); quando Bob torna con la soluzione pochi giorni dopo, Alice può dimostrare di aver avuto la soluzione in precedenza rivelandola; Una volta rivelata, avendo l'hash di Bob, Alice può controllare che questo corrisponda effettivamente al valore di hash precedentemente calcolato da lei. Nella pratica reale, Alice e Bob sono spesso programmi informatici e, ovviamente, il segreto consisterà in qualcosa di poco facile da imbrogliare: tale esempio riconduce quelli che in inglese vengono detti “schemi di impegno”.
Applicazioni Verifica dell'integrità di un messaggio
Un'importante applicazione delle funzioni crittografiche di hash è nella verifica dell'integrità di un messaggio. Per mezzo di tali funzioni è possibile determinare, ad esempio, se sono state compiute modifiche ad un messaggio (o ad un ) confrontando il suo hash prima e dopo la trasmissione. Un particolare uso ne viene fatto nella maggior parte degli algoritmi di firma digitale, i quali utilizzano le funzioni di hash al fine di produrre una firma tale da garantire l'autenticità di un messaggio, evitando che un possibile destinatario modifichi un documento firmato da qualcun altro. Per questo motivo il valore di hash viene anche detto impronta digitale del messaggio. La verifica quindi dell'autenticità del valore di hash del messaggio viene considerata come prova di autenticità del messaggio stesso.
Verifica delle password
Nelle applicazioni che necessitano di un'adeguata autenticazione è troppo rischioso memorizzare le password di tutti gli utenti in chiaro, cioè su un file non cifrato, soprattutto nel caso in cui quest'ultimo venga compromesso. Un modo per evitare di andare incontro a una vera e propria violazione della sicurezza è quello di memorizzare solo il valore di hash di ogni password: una volta avvenuta l'autenticazione da parte dell'utente, viene calcolato l'hash della password da lui inserita e il risultato viene confrontato con l'hash memorizzato in precedenza. Spesso, la password viene concatenata con un valore casuale e non segreto, denominato salt (sale), prima ancora che venga applicata la funzione hash. Utilizzati insieme, ma memorizzati separatamente, producono un output che sostituisce le sole password, consentendo dunque agli utenti di autenticarsi. Tenendo in considerazione il sale e il fatto che, generalmente, gli utenti ne possiedono diversi, non è possibile archiviare tabelle di valori di hash pre-computati per le password comuni. Però, come già accennato in precedenza, essendo da un lato le password dei messaggi brevi e le funzioni di hash progettate per essere calcolate rapidamente dall'altro, è possibile essere soggetti ad attacchi di forza bruta (basta considerare che la GPU può provare miliardi di possibili password al secondo). In compenso, esistono delle funzioni, denominate funzioni di stretching della chiave, come PBKDF2, Bcrypt o Scrypt che "potenziano" le password per renderle più sicure di fronte ad un attacco di forza bruta.
Proof-of-Work