Collisione hash

In crittografia, una collisione hash è una situazione che avviene quando due diversi input producono lo stesso output tramite una funzione hash.

Potenzialmente, la maggior parte delle funzioni hash danno luogo a collisioni, ma con una buona funzione hash esse avvengono molto raramente (e sono molto difficili da trovare). In certe applicazioni specifiche, in cui si ha un numero relativamente piccolo di input, è possibile costruire una funzione hash perfetta che mappa tutti i diversi input in differenti output. Invece, una funzione che prende in ingresso input di lunghezza arbitraria e ritorna un hash di misura fissa (come l'MD5), deve avere necessariamente delle collisioni, perché il numero di possibili output è finito a fronte di un numero infinito di possibili input.

Collisioni nella ricerca di dati

Un metodo efficiente di ricerca può essere quello di processare una chiave di lookup usando un'altra funzione hash, poi prendere il risultante valore hash e infine usarlo come un indice all'interno di un array di dati. La risultante struttura di dati viene chiamata hash table. Finché chiavi differenti corrispondono a indici differenti (caso ideale di funzione di hash perfetta), il tempo necessario al processo di lookup ha un valore massimo limitato (cioè è indipendente dalle dimensioni della struttura e dalla chiave usata, punto di forza delle hash tables). Nel caso in cui chiavi di lookup puntino ad indici identici, avviene una collisione hash. La maniera più popolare per evitare questo evento è concatenarlo creando una linked list di valori per ogni indice dell'array, e indirizzarlo senza restrizioni (open addressing) cercando altri indici vicini dell'array per trovare uno spazio libero. Entrambi, comunque, svalorizzano i peggiori casi di complessità di lookup per un tempo lineare del numero degli elementi.

Crittografia

Una proprietà desiderabile delle funzioni hash crittografiche è che sia computazionalmente impossibile trovare una collisione. Il valore della funzione hash può essere usato per certificare che un input non sia stato modificato pubblicando la firma dell'hash, se non è fattibile produrre una collisione. Fattibile, in questo contesto, significa che ogni metodo deve essere più veloce di un metodo di forza bruta.

Resistenza alle collisioni debole

La resistenza alle collisioni debole per la funzione di hash $H$, si ha se per ogni messaggio $m$, non è fattibile trovare un altro messaggio $m'$ tale che $H(m')=H(m)$.
Quindi conoscendo l'hash di un messaggio, non sono in grado, con una potenza di calcolo ragionevole, di trovare un altro input che mi genera lo stesso hash. Da notare che la proprietà suppone che io conosca il messaggio di origine e che questo non mi aiuti nel trovare un secondo messaggio con hash identico.

Resistenza alle collisioni forte

Supponiamo invece di non partire da un messaggio dato, ma di poter scegliere una qualsiasi coppia di messaggi che generano lo stesso hash. Se ci riusciamo, non abbiamo violato la resistenza alle collisioni debole. Tuttavia esiste un'altra proprietà, più restrittiva, che impedisce che questo sia fattibile.
Più formalmente: non è fattibile trovare una qualsiasi coppia $(m,m')$ tale che $H(m)=H(m')$

Collegamenti esterni

• (EN) hash collision, in Free On-line Dictionary of Computing, Denis Howe. Disponibile con licenza GFDL