Funzioni hash

 :: Funzioni hash ::

Torna alla pagina di Crittografia

Che cosa sono

Le funzioni hash sono delle funzioni che, preso in pasto un input di lunghezza arbitraria (comunque finita), producono un output di lunghezza fissa che dipende dall'input.
L'output di questa funzione è detto fingerprint, digest oppure hash del messaggio M.

A che cosa servono

Gli scopi delle funzioni hash sono essenzialmente 3:

• firma digitale
• integrità dei dati
• certificazione del tempo

Per quanto riguarda la firma digitale, il procedimento è in genere di calcolare l'hash di un messaggio e trasmetterlo in modo sicuro al destinatario, in genere tramite cifrature asimmetriche, così che il destinatario è in grado di verificare che il messaggio proviene proprio da chi dice di mandarlo.

L'integrità dei dati, parimenti, si ha quando genero un hash a partire da un messaggio M. L'hash è unico per ogni messaggio M (sotto vedremo meglio). Il mittente, che scrive il messaggio M, allega al messaggio anche l'hash del messaggio, che è unico. Il destinatario riceve il messaggio e anche l'hash: deve quindi calcolare in proprio l'hash del messaggio, e vedere se corrisponde all'hash che il mittente ha inviato. Se sì, allora il messaggio è arrivato integro. Se no, vuol dire che qualcuno ha modificato il messaggio.

La certificazione del tempo la ottengo generando l'hash del messaggio unito alla data di creazione. Se qualcuno modifica la data, anche l'hash cambierà, e il destinatario se ne accorge.

Proprietà delle funzioni hash

Tutte le cose viste qui sopra sono dovute a tre proprietà:

• one-wayness
• weak collision resistance
• strong collision resistance

One-wayness

La proprietà di one-wayness mi dice che è impossibile risalire da un valore hash al messaggio che l'ha generato.

Ciò vuol dire che se ho il messaggio M, ed il suo hash è h(M), io, avendo il solo h(M), non so dire niente del messaggio M.

Sopra abbiamo detto che le funzioni hash prendono in input un messaggio di lunghezza arbitraria, e generano un output di lunghezza fissa, che supponiamo essere di n bit.
Questo vuol dire che tutti gli infiniti messaggi vengono mappati dalla funzione hash in "soli" 2ⁿ valori.

Ciò sta a significare che è perfettamente plausibile che due messaggi diversi possano avere lo stesso hash, e infatti sotto vedremo come sfruttare questa proprietà.

Ciononostante, la one-wayness mi garantisce che, dato un hash, non so dire niente a proposito del messaggio che lo origina. Infatti, ci saranno infiniti messaggio che vengono mappati nello stesso valore hash, proprio per il fatto che l'hash ha una dimensione finita.

Weak collision resistance

La weak collision resistance mi dice che, se ho un messaggio M ed il corrispondente valore hash h(M), non sono in grado di calcolare in qualche modo un messaggio Z tale che h(Z) = h(M).

In pratica, non so trovare un messaggio che dia come valore hash lo stesso hash di un messaggio che ho già in mano. La collisione si ha quando due messaggi diversi hanno lo stesso hash.

Strong collision resistance

La strong collision resistance è una proprietà per cui non sono in grado di calcolare ex-novo due messaggi, M e Z, che diano lo stesso hash.

Da notare la differenza con la weak: la weak parte dal presupposto che HO GIÀ un M e il suo hash. Qui invece parto da 0: non ho in mano niente, e voglio fare il "miracolo" di generare con un algoritmo due valori x e y che diano lo stesso hash.

Relazioni tra queste proprietà

Le proprietà si implicano a vicenda: strong -> weak -> one-wayness.

Il paradosso del compleanno

Il paradosso del compleanno recita così: quante persone devo scegliere, a caso, affinché io abbia la probabilità maggiore di 0,5 che due compiano gli anni lo stesso giorno?

La risposta è che basta scegliere 23 persone, per avere probabilità maggiore di 0.5 che due di esse compiano gli anni lo stesso giorno, non importa quale. Per avere la certezza, dovrei avere 366 persone. Ma già con 23 so che 50% due compiono gli anni lo stesso giorno.

Torniamo alle proprietà delle nostre funzioni hash: quanti messaggi casuali devo generare per trovarne due che hanno lo stesso hash, cioè avere una collisione?

La risposta è che devo generare in media 2^n/2 messaggi, dove n è la lunghezza in bit dell'output della funzione hash. Se una funzione hash ha un'output di 64 bit, vuol dire che devo generare 2³² messaggi in media per avere una collisione: con la tecnologia odierna, tutti i calcoli che sono inferiori asintoticamente a 2^'80^'0' sono potenzialmente insicuri => una funzione hash con un output di 64 bit è altamente insicura!

Ecco perché le funzioni hash moderne hanno output di almeno 160 bit.

Attacco a compleanno

Come Cattivo può sfruttare questa proprietà a suo vantaggio?

Supponiamo che Alice debba firmare, con una funzione hash, un certo messaggio, ad esempio: "Alice ha un credito di 1000 dollari con Bob. Firmato, Alice". Alice prende il suo messaggio, genera l'hash, e lo invia a Bob con la chiave pubblica di Bob, così Bob riceve il messaggio, ne calcola l'hash, e verifica che sia uguale a quello che Alice gli ha inviato. Se sì, vuol dire che il messaggio è arrivato integro.

L'attaccante Cattivo può fare questo: può generare un certo numero di variazioni del messaggio originale M. Ad esempio, una variazione può essere "Alice è in attesa di 1000 dollari da Bob", oppure "Bob deve 1000 dollari ad Alice" e cose del genere.

Poi, deve generare un certo numero di messaggi fraudolenti, ovvero messaggi che dicono quello che Cattivo vuole far dire ad Alice: "Alice ha un DEBITO di 1000 dollari con Bob" e via dicendo.
In particolare, Cattivo genererà variazioni del messaggio fraudolento, in modo che l'hash della variazione del messaggio fraudolento sia uguale all'hash di una delle variazioni del messaggio originale.

Quello che deve fare, alla fine, è far firmare ad Alice una delle variazioni del messaggio originale, ma poi inviare a Bob il messaggio fraudolento che ha lo stesso hash della variazione appena firmata. Se ha lo stesso hash, significa che la firma sarà identica: Alice firma una cosa, ma questa firma è al 100% valida anche per un messaggio che dice l'esatto opposto.

Il problema qui è: quante variazioni deve generare Cattivo prima di avere una collisione?
Il punto è che io voglio che una variazione del messaggio "Alice ha un credito" e una variazione del messaggio "Alice ha un debito" abbiano lo stesso hash.

Per avere collisioni, abbiamo visto sopra che è necessario, in media, calcolare 2^n/2 messaggi, il che non è affatto improponibile come sembra.

Alcune funzioni hash

Le funzioni hash che studiamo sono derivate di MD4, e ne condividono la struttura di base

MD5

• Input: testo di 2⁶⁴ bit
• Output: 128 bit

La prima cosa da fare è il padding, ovvero sistemare la lunghezza del messaggio originale. Siccome la funzione lavora su blocchi di 512 bit, occorre che il messaggio sia lungo esattamente un multiplo di 512 bit.
Per avere ciò, lavoro in 2 passi:

1. al messaggio appendo un 1 seguito da tanti 0 fino a quando non ho una lunghezza che è congruente a 448 modulo 512
2. avanzano 64 bit: in questi 64 bit metto la lunghezza del messaggio

C'è un buffer di 4 word da 32 bit ciascuna: A, B, C e D. Queste 4 word vengono inizializzate con certi valori.
Ci sono 4 fasi di 16 passi ciascuna, che prendono in input il blocco del messaggio, il buffer e delle costanti da una tabella (16 * 4 = 64 voci in tabella), spaciugano il tutto e come risultato modificano il buffer.

Ogni fase ha una sua particolare operazione primitiva: le fasi hanno la stessa forma, ma cambia l'operazione che ciascuna fase esegue.

Alla fine, l'output è dato dal contenuto del buffer.

MD4

• 3 fasi di 16 passi
• Output di 128 bit
• a differenza di MD5 (MD4 è il predecessore di MD5) non si usano costanti nella prima fase, e il valore di un passo non dipende dal valore del passo precedente della stessa fase

SHA-1

• Input: 2⁶⁴
• Output: 160 bit
• 4 fasi di 20 passi ciascuna => ho una tabella con 80 voci (4 * 20)
• Il buffer è composto da 5 word di 32 bit: A, B, C, D, E

Anche questa è come MD5, per il resto.

Torna alla pagina di Crittografia