En cuanto a su actualización, sus funciones hash criptográficas estándar (MD5, SHA-1, SHA-2, SHA-3) intentan aproximarse a oráculos aleatorios (y no intentes ser inyectivo). Es decir, intentan asignar cualquier entrada a una salida elegida de manera uniforme y aleatoria en su espacio de salida (y hacer esta asignación de manera consistente). Con una probabilidad abrumadora, los oráculos aleatorios no serán inyectivos cuando el número de entradas posibles sea significativamente mayor que la raíz cuadrada del número de salidas posibles, debido a la paradoja de cumpleaños .

Por ejemplo, si tiene una salida de hash de 128 bits (un hash de 16 bytes con 2 posibles salidas ¹²⁸ ) y usa un oráculo aleatorio para hacer hash significativamente más que sqrt (2 ¹²⁸ ) = 2 ⁶⁴ entradas, comienza a ser abrumadoramente probable de que haya colisiones. Por otro lado, si tiene menos de 2 entradas ⁶⁴ , es muy poco probable que tenga una colisión si comenzó con un oráculo aleatorio ideal. (Si tiene alrededor de 2 entradas ⁶⁴ la probabilidad de ser inyectivo es aproximadamente 1/2; puede haber una colisión o no).

Como ejemplo específico, si hash todas las entradas de 9 bytes posibles de 2 ⁷² , la probabilidad de que un oráculo aleatorio sea inyectivo en un espacio de 16 bytes es aproximadamente exp (-n ^{2 / 2m} ) ≈ 10 ^-14231 , donde n = 2 ⁷² ≈ 4.7 x 10 ²¹ y m = 2 ¹²⁸ ≈ 3.4 x 10 ³⁸ . Esto es increíblemente improbable; aproximadamente el equivalente a jugar powerball (probabilidades de ganar 1 en 292 millones) dos veces a la semana durante 16 años y ganar el premio mayor cada vez sin perder boletos. Y nuevamente, esto es solo para una entrada de 9 bytes; con una entrada de 15 bytes, la probabilidad de ser inyectivo es aproximadamente 10 ^{-1127492937032632506267955467381579} !

Mientras tanto, si tiene todas las entradas posibles de 7 bytes, solo hay 2 ⁵⁶ , por lo que es muy probable que no haya colisiones (es decir, será inyectivo). Como esto es significativamente menor que sqrt (2 ¹²⁸ ), un oráculo aleatorio no sería inyectivo con probabilidad con 0.0000076 (aproximadamente 1 en 130 000 veces no sería inyectivo y el resto del tiempo sería inyectivo).

Consulte la tabla de probabilidad en wikipedia para obtener más información.

Por supuesto, esto no es una prueba para ninguna función hash específica; para demostrarlo, tendríamos que generar una colisión específica dentro del espacio de entrada que, en general, sería difícil de mostrar.

Ahora, si necesita una función inyectiva que actúe de manera similar a un hash, esto es bastante sencillo de lograr mediante el uso de un cifrado de bloque (conocido formalmente como permutación pseudoaleatoria ) como AES y elige una clave aleatoria para cifrarla. Los cifrados de bloque son necesariamente tanto inyectivos como superyectivos. Si un cifrado de bloque no era inyectivo, entonces una persona con la clave y la función de descifrado y un bloque de texto cifrado para descifrar no podrían recuperar el bloque original.

La desventaja de usar un cifrado de bloque en lugar de una función hash es que el cifrado de bloque requiere una entrada de solo una longitud fija y la transforma en una salida de la misma longitud fija. Por ejemplo, AES solo puede tomar una entrada de 128 bits y transformarla en una salida de 128 bits. (Sí, podría usar los modos de cifrado de bloque para transformar entradas más grandes, pero para que sea uno a uno, el tamaño de salida sería de la misma longitud que la entrada). El hecho de que una función hash pueda tomar entradas de tamaño variable y generar un hash de tamaño fijo la hace ideal para muchos propósitos. El hecho de que este requisito de hashes para asignar entradas de tamaño variable tomadas de un espacio de entrada muy grande a un espacio de salida más pequeño significa que no será un inyectivo según el principio del casillero generalmente no es un problema en la práctica.     

Actualización:

Todavía no. Incluso si restringes el espacio de entrada para que tenga el mismo tamaño que (o sea menor que) el espacio de salida, no hay garantía ni prueba formal de que una función hash determinada sea una colisión -free (al menos, no hay pruebas de las que tenga conocimiento).

Parte de la razón por la que nos gustan las funciones hash criptográficas es que, por lo que sabemos, no tienen patrones discernibles. Esta es una espada de doble filo que hace casi imposible hacer un análisis matemático de ellos (y si pudiéramos, los declararíamos débiles y pasaríamos a algo más complejo).

Supongo que podría escribir un programa para verificar las 2 entradas ¹²⁸ a MD5 y ver por sí mismo si hay colisiones, pero necesitará aproximadamente 10 ²⁷ Los discos duros de 1 terabyte solo almacenan la tabla de búsqueda para saber cuándo se produce una colisión.

Respuesta anterior

En términos generales, las funciones hash no son inyectivas; no ofrecen ninguna garantía de no colisión .

Todas las funciones hash estándar (incluidas las que usted mencionó) toman una entrada de longitud arbitraria y producen una salida de longitud fija. Tomemos, por ejemplo, el SHA-256 con una salida de 256 bits, podría asignar las primeras 2 entradas ²⁵⁶ a salidas únicas, pero ¿qué pasa con las 2 ²⁵⁶ + 1 th inupt? tiene para colisionar con algo que ya ha sido mapeado - esto se conoce como el Principio de paloma .

Más formalmente, cualquier función cuyo dominio (espacio de entrada) sea mayor que su rango (espacio de salida) no puede ser inyectiva.

Por lo que sé, la razón principal por la que el MD5 fue desaprobado por el uso criptográfico es que conocemos varios pares de cadenas cortas (de 128 bits) que producen colisiones en el MD5. Consulte la Demostración de MD5 Collision .

Hasta donde sé, no hay colisiones conocidas para ningún hash en la familia SHA (aunque en teoría sabemos que deben existir según el principio del casillero).

Aparte: esto está fuera del alcance de su pregunta, para el interés, mencionaré que está en un problema abierto en cuanto a si los hashes en la familia SHA son superyectivos (es decir, si cada salida posible se asigna realmente, o si hay brechas).

Las funciones de hash se usan generalmente para verificar la integridad de los datos. Permiten que un usuario verifique que algunos datos de entrada se asignan a un valor hash dado, pero si los datos de entrada son desconocidos, es imposible reconstruirlos al conocer el valor hash almacenado. En pocas palabras puedo generar una cadena que identifique un cierto tipo de datos con una función hash. ¿Es posible generar dos hashes iguales a partir de dos entradas diferentes? La respuesta es sí, pero es muy rara. Esta situación se llama colisión. Las colisiones ocurren cuando, los miembros de un conjunto muy grande (como todos los archivos de computadora posibles) se asignan a una cadena de bits relativamente corta. Dicho matemáticamente, un ataque de colisión encuentra dos mensajes diferentes m1 y m2, de manera que hash (m1) = hash (m2). Esta es una demostración de ataque de colisión MD5 donde se genera el mismo hash a partir de dos archivos ejecutables diferentes. Otro ejemplo es la función hash SHA1 que se ha sustituido con SHA-2 que tiene menos probabilidades de ser explotada con un ataque de colisión.