Hash crittografiche

Funzione di hash

Si tratta di trasformare un blocco di lunghezza in generale variabile in un blocco di dati di lunghezza fissa e molto più piccola. Dato un messaggio M in input si ha la seguente funzione di hash H che fornisce un valore di uscita h: h = H(M). Il concetto principale nell’effettuare questa trasformazione è che il blocco di uscita è di lunghezza fissa ed è molto più piccolo della lunghezza del blocco in ingresso. L’obiettivo è quello dell’integrità dei dati (in questo caso per integrità si intende che se cambia il messaggio in ingresso anche di un solo bit allora cambia anche il valore di hash).

La funzione di hash è una funzione non biunivoca ossia è una funzione molti-uno perché se il messaggio di ingresso è un messaggio che ha molti più bit del valore di hash, è chiaro che si deve mappare tante configurazioni in un numero di configurazioni più piccolo.

Pre-immagine e collisione

Pre-immagine: Il valore di ingresso che corrisponde ad un certo valore di uscita è chiamato pre-immagine: h(m) = y dove m è una pre-immagine di y. Ogni valore di hash ha tante più pre-immagini tanto più alto è il rapporto di compressione che utilizziamo.

Collisione: se abbiamo più pre-immagini che corrispondono ad uno stesso valore di hash, allora le due pre-immagini collidono. Non si vuole avere collisioni ma in generale è impossibile avere zero collisioni.

Funzioni hash crittografiche

Le proprietà che ci permettono di distinguere una funzione hash generica da una funzione hash crittografica sono:

• Computazionalmente quasi impossibile invertire le funzioni di hash ossia dal valore di hash risalire alla pre-immagine  Proprietà one-way.
• Si vuole che non ci siano collisioni ossia che dato un valore di hash non ci si riesce a determinare 2 dati in ingresso che corrispondano allo stesso valore di hash  collision-free.

Nelle strutture dati desideriamo evitare collisioni, in quella crittografica avere collisioni è un prerequisito. Nelle strutture dati l’insieme di elementi di dati è scelto indipendentemente dalla funzione hash. Nella crittografia un avversario potrebbe selezionare elementi con l’obiettivo esplicito che causa la collisione.

Applicazioni delle funzioni di hash crittografiche

• Autenticazione dei messaggi
• Firme digitali: qui l’utilizzo è simile a quello del MAC.
• One way password file
• Rivelazione di intrusioni
• Rilevazioni di virus

Nell’autenticazione del messaggio si vuole impedire una modifica, inserimento, cancellazione o replay di parti del messaggio. Si prende il blocco di dati, gli si applica la funzione di hash che dà luogo al message digest; appendiamo il message digest al blocco di dati e trasmettiamo entrambi. A destinazione, B prende il blocco di dati con l’hash, estrae il blocco di dati e se non è cambiato ritrova la stessa funzione di hash e se è cambiato deve cambiare anche il valore di hash. Questo si basa sul principio che il valore di hash che viene trasmesso deve essere preservato ossia arrivare integro.

Nel precedente schema ci sono 4 modi diversi per ottenere l’autenticazione del messaggio attraverso la funzione di hash. La funzione H sta per hash e la funzione E ed D stanno per cifratura e decifratura.