¿Cómo son únicas las funciones hash como MD5?

Tienes toda la razón. Pero los hashes no son "únicos", son "lo suficientemente únicos".

Como otros han señalado, el objetivo de una función hash como MD5 es proporcionar una forma de verificar fácilmente si dos objetos son equivalentes, sin saber qué eran originalmente (contraseñas) o compararlos en su totalidad (archivos grandes).

Digamos que tienes un objeto Oy su hash h _O. Obtiene otro objeto P y desea comprobar si es igual a O. Esto podría ser una contraseña, o un archivo descargado (en cuyo caso no tendrá O pero más bien el hash de la misma h _O que vino con P, lo más probable). Primero, haces hash P para obtener h _P.

Ahora hay 2 posibilidades:

1. h_O y h_P son diferentes. Esto debe significar que O y P son diferentes, porque usar el mismo hash en 2 valores/objetos debe producir el mismo valor. Hashes son deterministas. No hay falsos negativos.

2. H_O y h_P son iguales. Como usted declaró, debido al Principio de Casillero esto podría significar que diferentes objetos hash al mismo valor, y puede ser necesario tomar medidas adicionales.

   A. Debido a que el número de posibilidades es tan alto, si tienes fe en tu función hash, puede ser suficiente decir " Bueno, hubo un 1 en 2¹²⁸ chance of collision (ideal case), so we can assume O = P. Esto puede funcionar para contraseñas si restringes la longitud y complejidad de los caracteres, por ejemplo. Es por eso que ves hashes de contraseñas almacenadas en bases de datos en lugar de las propias contraseñas. b. Usted puede decidir que solo porque el hash salió igual no significa que los objetos son iguales, y hacer una comparación directa de O y P. Usted puede tener un falso positivo.

Así que si bien puede tener coincidencias de falsos positivos, no tendrá falsos negativos. Dependiendo de su aplicación, y si espera que los objetos sean siempre iguales o siempre diferentes, el hashing puede ser un paso superfluo.

Las funciones hash unidireccionales criptográficas son, por naturaleza de definición, no Inyectivas. En términos de funciones hash, "único"no tiene sentido. Estas funciones se miden por otros atributos, lo que afecta su fuerza al hacer difícil crear una pre-imagen de un hash dado. Por ejemplo, podemos preocuparnos por cuántos bits de imagen se ven afectados al cambiar un solo bit en la pre-imagen. Podemos preocuparnos por lo difícil que es llevar a cabo un ataque de fuerza bruta (encontrar una imagen prie para un imagen de hash dada). Podemos preocuparnos por lo difícil que es encontrar una colisión: encontrar dos pre-imágenes que tengan la misma imagen hash, para ser utilizadas en un ataque de cumpleaños .

Si bien es probable que se produzcan colisiones si los valores que se hash son mucho más largos que el hash resultante, el número de colisiones sigue siendo suficientemente bajo para la mayoría de los propósitos (hay 2¹²⁸ total de hashes posibles, por lo que la probabilidad de que dos cadenas aleatorias produzcan el mismo hash es teóricamente cercana a 1 en 10³⁸).

MD5 fue creado principalmente para hacer comprobaciones de integridad, por lo que es muy sensible a cambios mínimos. Una modificación menor en la entrada resultado en una salida drásticamente diferente. Esta es la razón por la que es difícil adivinar una contraseña basándose solo en el valor hash.

Mientras que el hash en sí no es reversible, todavía es posible encontrar un posible valor de entrada por fuerza bruta pura. Esta es la razón por la que siempre debe asegurarse de agregar una sal si está utilizando MD5 para almacenar hashes de contraseña: si incluye una sal en la cadena de entrada, una cadena de entrada coincidente debe incluir exactamente la misma sal para obtener la misma cadena de salida porque de lo contrario, la cadena de entrada sin procesar que coincide con la salida no coincidirá después del salado automático (es decir, no puede simplemente "invertir" el MD5 y usarlo para iniciar sesión porque el hash MD5 invertido probablemente no será la cadena salada que originalmente resultó en la creación del hash).

Así que los hashes no son únicos, pero el mecanismo de autenticación se puede hacer para hacerlo lo suficientemente único (que es un argumento algo plausible para las restricciones de contraseña en lugar de salar: el conjunto de cadenas que resulta en el mismo hash probablemente contendrá muchas cadenas que no obedecen a las restricciones de contraseña, por lo que es más difícil revertir el hash por fuerza bruta obviously obviamente, las sales siguen siendo una buena idea sin embargo).

Hashes más grandes significan un conjunto más grande de hashes posibles para el mismo conjunto de entrada, por lo que una menor probabilidad de superposición, pero hasta que el poder de procesamiento avance lo suficiente como para que el forzamiento bruto MD5 sea trivial, sigue siendo una opción decente para la mayoría de los propósitos.

(Parece ser la Función Hash del Domingo.)

Las funciones hash criptográficas están diseñadas para tener tasas de duplicación muy, muy, muy bajas. Por la razón obvia que usted dice, la tasa nunca puede ser cero.

La página de Wikipedia es informativa.

Como dijo Mike (y básicamente todos los demás), no es perfecto, pero hace el trabajo, y el rendimiento de colisión realmente depende de algo (que en realidad es bastante bueno).

Lo que es de interés real es la manipulación automática de archivos o datos para mantener el mismo hash con datos diferentes, ver esta Demo

Como otros han respondido, las funciones hash no están garantizadas por definición para devolver valores únicos, ya que hay un número fijo de hashes para un número infinito de entradas. Su cualidad clave es que sus colisiones son impredecibles .

En otras palabras, no son fácilmente reversibles so así que aunque puede haber muchas entradas distintas que producirán el mismo resultado hash (una "colisión"), encontrar dos de ellas es computacionalmente inviable.