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

tipos de funciones hash (8)

(Parece ser el Hash Function Sunday).

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 afirma, la tasa nunca puede ser cero.

La página de Wikipedia es informativa.

Soy consciente de que MD5 ha tenido algunas colisiones, pero esto es más una pregunta de alto nivel sobre las funciones hash.

Si MD5 mezcla cualquier cadena arbitraria en un valor hexadecimal de 32 dígitos, entonces, de acuerdo con el Principio de Casillero, seguramente esto no puede ser único, ya que hay más cadenas arbitrarias únicas que valores únicos de hexágono de 32 dígitos.

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

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

Como han señalado otros, 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 tiene un objeto O y su hash h _O. Obtienes otro objeto P y deseas comprobar si es igual a O Esto podría ser una contraseña o un archivo que descargó (en cuyo caso no tendrá O sino más bien el hash h _O que vino con P , lo más probable). Primero, hash P para obtener h _P.

Ahora hay 2 posibilidades:

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. Los hashes son deterministas. No hay falsos negativos.
h _O y h _P son iguales. Como dijiste, debido al Principio de Casillero, esto podría significar que diferentes objetos tienen el mismo valor, y es posible que sea necesario tomar medidas adicionales.
a. Debido a que el número de posibilidades es tan alto, si tiene fe en su función hash, puede ser suficiente decir "Bueno, hubo 1 en 2 ¹²⁸ posibilidad de colisión (caso ideal), así que podemos suponer O = P Esto puede trabaje para contraseñas si restringe la longitud y complejidad de los caracteres, por ejemplo, es por eso que ve hashes de contraseñas almacenadas en bases de datos en lugar de las contraseñas mismas. b. Puede decidir que solo porque el hash salió igual no significa los objetos son iguales, y hacen una comparación directa de O y P Puede tener un falso positivo.

Entonces, aunque pueda 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 hash puede ser un paso superfluo.

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, por lo tanto, aunque puede haber muchas entradas distintas que producirán el mismo resultado de hash (una "colisión"), encontrar dos de ellas es inviable desde el punto de vista computacional.

Las funciones hash criptográficas unidireccionales son, por naturaleza de definición, no Injective . En términos de funciones hash, "único" no tiene sentido. Estas funciones se miden por otros atributos, lo que afecta su fuerza al dificultar la creación de una imagen previa de un hash dado. Por ejemplo, nos puede importar cuántos bits de imagen se ven afectados al cambiar un solo bit en la imagen previa. Nos puede importar cuán difícil es realizar un ataque de fuerza bruta (encontrar una prie-image para una determinada imagen hash). Puede que nos importe lo difícil que es encontrar una colisión: encontrar dos imágenes previas que tengan la misma imagen hash, para usarlas en un ataque de cumpleaños .

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

MD5 fue creado principalmente para realizar verificaciones de integridad, por lo que es muy sensible a los cambios mínimos. Una pequeña modificación en la entrada dará como resultado una salida drásticamente diferente. Es por eso que es difícil adivinar una contraseña basada solamente en el valor hash.

Si bien el hash en sí mismo no es reversible, aún es posible encontrar un posible valor de entrada por pura fuerza bruta. Esta es la razón por la que siempre debe asegurarse de agregar una sal si está usando 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 dar como resultado el mismo cadena de salida porque de lo contrario la cadena de entrada sin procesar que coincida con la salida no coincidirá después de la salazón automatizada (es decir, no puede simplemente "revertir" el MD5 y usarlo para iniciar sesión porque el hash MD5 invertido probablemente no sea salado cadena que originalmente dio como resultado la creación del hash).

Así que los hashes no son únicos, pero el mecanismo de autenticación puede ser lo suficientemente único (que es un argumento un tanto plausible para las restricciones de contraseña en lugar de salazón: el conjunto de cadenas que resulta en el mismo hash probablemente contendrá muchas cadenas que hacen no obedecer las restricciones de contraseña, por lo que es más difícil revertir el hash por la fuerza bruta; obviamente, las sales siguen siendo una buena idea).

Los hashes más grandes significan un conjunto mayor de hashes posibles para el mismo conjunto de entrada, por lo que hay menos posibilidades de solapamiento, pero hasta que la potencia de procesamiento avance lo suficiente como para hacer trivial el MD5, sigue siendo una opción decente para la mayoría de los propósitos.

Tiene razón en que no puede garantizar la singularidad, sin embargo, hay aproximadamente 3.402823669209387e + 38 valores diferentes en un valor hexadecimal de 32 dígitos (16 ^ 32). Eso significa que, suponiendo que la matemática detrás del algoritmo ofrece una buena distribución, tus probabilidades son increíblemente pequeñas de que habrá un duplicado. Debe tener en cuenta que ES POSIBLE duplicar cuando está pensando en cómo se usará. MD5 se usa generalmente para determinar si algo ha cambiado (es decir, es una suma de comprobación). Sería ridículamente improbable que algo pueda modificarse y dar como resultado la misma suma de comprobación MD5.

Editar: (noticias recientes re: SHA1 hash) La respuesta anterior, todavía se mantiene, pero no debe esperar que un hash MD5 sirva como un tipo de control de seguridad contra la manipulación. SHA-1 Hashes como 2 ^ 32 (más de 4 billones) de veces menos probabilidades de colisionar, y se ha demostrado que es posible generar una entrada para producir el mismo valor. (Esto se demostró en MD5 hace bastante tiempo). Si está buscando asegurarse de que nadie haya modificado maliciosamente algo para producir el mismo valor hash, actualmente, necesita que SHA-2 tenga una garantía sólida.

Por otro lado, si no está en un contexto de verificación de seguridad, MD5 todavía tiene su utilidad.

Se podría argumentar que un hash SHA-2 es lo suficientemente barato como para calcularlo, que debería usarlo de todos modos.

Usted es absolutamente correcto. Pero los hashes no son "únicos", se tratan de "lo suficientemente únicos".