¿Que significa/implica que una función HASH sea libre de colisiones?

Una función hash es un algoritmo matemático que para un mensaje/cadena de entrada de cualquier tamaño x, es capaz de generar (de manera eficiente) una cadena de salida de longitud fija H(x), que funciona como resumen del mensaje de entrada. Esto es debido a que el mas mínimo cambio en el conjunto de entrada, daría como resultado una hash totalmente diferente. 

En SHA-2, (Algoritmo de Hash Seguro) de 256 bits, para cada conjunto de datos de entrada, la función hash produce un único valor de salida de 256 bits.

 

Para que la premisa anterior se cumpla debemos asumir que la función (SHA-2) es libre de colisiones (collision-free). Significa que nadie e capaz de encontrar una situación donde partiendo de mensajes de entrada diferentes x!=y, al aplicar la función obtenga la misma salida  H(x)=H(y).

Pero las colisiones existen, lo que pasa es que muy poco probable que con una computadora convencional se puedan encontrar.

Una manera muy sencilla de verlo es la siguiente: como el conjunto de entrada (todas las entradas posibles) de la función hash, puede ser una cadena de cualquier tamaño (2 posibilidades). Y todas la salidas posibles tienen que ser de 256 bits de tamaño (2256 posibilidades). Está claro que si mapeas el suficiente número de entradas posibles contra el conjunto de salidas posibles, muchas tienen que coincidir.

Sin embargo, la cantidad de operaciones que sería necesario realizar para tener una alta probabilidad de encontrar una colisión (en el orden de 2130) es una cifra astronómica. Esta es la razón por la que elegimos creer que nuestra función hash es collision-free

Si podemos asumir que tenemos una función de hash libre de colisiones, entonces podemos usar ésta como resumen de mensajes. Lo que significa que, si H(x)=H(y), x=y.