Collisione hash

Esempio di 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.

Collegamenti esterni

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