propiedades - ¿Cuál es la probabilidad de que los primeros 4 bytes de hash MD5 calculados a partir del contenido del archivo colisionen?
propiedades de los hash (6)
En ausencia de más información sobre la probabilidad de los valores de byte, el día sería 1 en 2 ^ 32.
EDITAR De hecho, 1 en 2 ^ 16 si está tomando los caracteres hexadecimales en lugar de los bytes puros.
EDITAR basado en un comentario:
¿Se puede considerar MD5 como uniforme que los valores calculados son absolutamente aleatorios?
El algoritmo hash MD5 está diseñado para que un pequeño cambio en la entrada produzca un hash completamente diferente, por lo que diría que los bytes hash MD5 se distribuyen con la misma probabilidad (de todos modos, no apostaría nada). De todos modos, puede aplicar un postproceso a su hash (por ejemplo, puede usar MD5 con clave ) para aumentar su aleatoriedad (y para hacerlo más seguro, por cierto, ya que se ha comprobado que los hash MD5 simples son inseguros ).
Esta es una pregunta combinatoria con cierta teoría en algoritmos hash requeridos.
Digamos que la entrada puede ser cualquier secuencia aleatoria de bytes de 30 kB a 5 MB de tamaño (supongo que hace bastantes combinaciones de valores de entrada :))
¿Cuál es la probabilidad de que los primeros 4 bytes (o primeros n bytes) de un hash MD5 calculado a partir de la secuencia de bytes sea el mismo para los distintos archivos?
En caso de que esto no se pueda calcular específicamente para hash MD5, entonces ¿cuál es la probabilidad de que cualquier función hash que genere hashes m-byte distribuidos uniformemente calculará hash con colisión en primeros n bytes para un rango dado de entradas?
Las probabilidades de una colisión en un hash de n bits son alrededor de 1 en 2 ^ (n / 2) debido a la paradoja del cumpleaños , por lo que aproximadamente 1 en 2 ^ 16 en este caso. Si por alguna razón te refieres a usar 32 bits de la codificación hexadecimal, por supuesto que solo serían los primeros 16 bits reales, entonces las probabilidades de una colisión serían de aproximadamente 1 en 2 ^ 8.
Dado un archivo fijo específico, las probabilidades de que cualquier otro archivo elegido al azar tenga el mismo hash que ese archivo son aproximadamente 2 ^ n. En términos de hashes criptográficos, la diferencia entre estos es que el primero es una colisión, el otro es una preimagen.
En este tamaño hash, las debilidades en MD5 son bastante irrelevantes ya que los ataques más conocidos en MD5 toman aproximadamente 2 ^ 32 cálculos, mientras que uno puede generar una colisión incluso en un hash de 32 bits idealmente seguro en alrededor de 2 ^ 16 cálculos (desde simplemente seleccionando entradas aleatorias, tienes 1 en 2 ^ 16 posibilidades de una colisión, así que después de aproximadamente 2 ^ 16 conjeturas al azar probablemente hayas encontrado un par de entradas en colisión).
Los hashes MD5 son típicamente hexadecimales, por lo que hay 16 valores posibles para cada byte. Por lo tanto, para cuatro bytes hay 16 * 16 * 16 * 16 = 65536 combinaciones posibles, lo que hace que la probabilidad de una colisión hash 1: 65536.
Para una función hash ideal, las salidas están distribuidas uniformemente, por lo que las posibilidades de que dos colisiones sean una en 2 ^ 32. La paradoja del cumpleaños, sin embargo, nos dice que si comparamos todos los pares de valores hash, deberíamos esperar ver una colisión una vez que tengamos 2 ^ 16 hashes, en promedio, así que no confíe solo en 4 bytes sobre la base de que "Tengo mucho menos de 4 mil millones de valores".
MD5 no es una función hash ideal, como sabemos, pero las debilidades son algo incidentales aquí: encontrar una colisión en 4 bytes está dentro del ámbito de un ataque razonable de fuerza bruta, por lo que no es necesario recurrir a debilidades criptográficas. Si solo te preocupan los datos elegidos al azar, no verás una desviación estadística significativa de la aleatoriedad.
Si está interesado en las probabilidades de que dos entradas en particular tengan el mismo hash de 4 bytes, entonces es solo 1/2 ^ 32. Si está interesado en las probabilidades de dos entradas de un conjunto de X entradas totales que tienen las mismas probabilidades, esto se mantiene bastante bajo hasta que empiece a aproximarse a 2 ^ 16 = 65536 entradas distintas en su conjunto, donde alcanza cerca del 50% ( este fenómeno se conoce como la paradoja del cumpleaños).
En general, uno de los criterios para que una función hash sea criptográficamente útil es la uniformidad en todos los bits.
md5 es hexadecimal, por lo que cada personaje puede tener cualquiera de los 16 alelos. Entonces eso haría 16^n
Para 4 caracteres, eso hace 65536 combinaciones posibles diferentes.