Cuando el hashing, ¿los mensajes más largos tienen una mayor probabilidad de colisiones?

  

¿Qué piezas del rompecabezas me faltan? ¿La facilidad para encontrar una colisión depende de la longitud de entrada?

Para encontrar una colisión, no es relevante la longitud de una cadena (aparte del tiempo necesario para calcular el hash, que en realidad es más largo para cadenas largas), sino la cantidad de cadenas diferentes que intenta. Debido a que mientras más entradas diferentes tenga, mayor será la posibilidad de que cualquiera de estos resultados tenga el mismo valor hash (longitud fija), es decir, una colisión. Y simplemente hay más cadenas largas diferentes que cadenas cortas.

Por ejemplo: hay 10 ^ 3 = 1000 cadenas con 3 dígitos pero ya 10 ^ 6 = 1000000 cadenas con 6 dígitos. Si imaginas un hash que consta de 4 dígitos, entonces podría haber una colisión con las cadenas de 3 dígitos, pero definitivamente habrá muchas colisiones dentro de las cadenas de 6 dígitos porque hay mucho más valores de cadena que valores de hash.

  

Cuanto más larga sea la entrada permitida, más fácil será proporcionar una entrada que podría causar una colisión de hash

La declaración que cita es incorrecta en el formulario actual. Es cierto que la probabilidad es mayor de que las cadenas que encontrarás sean largas. Pero como hay muchas más cadenas largas que cortas, esto no hace que encontrar una colisión sea más fácil. Nuevamente, lo que cuenta es la cantidad de entradas diferentes que tiene y no la longitud.

Creo que el póster del comentario hacía referencia a lo siguiente:

A medida que aumenta el tamaño del espacio de entrada (todas las cadenas de entrada posibles), la probabilidad de encontrar una colisión al agotar el espacio aumenta y, finalmente, alcanza el 100% cuando el tamaño del espacio de entrada es mayor que el tamaño de todos los valores hash posibles.

Ejemplo :

Suponiendo una función hash de 32 bits bien comportada. Si solo permite las cadenas "0" y "1" como entrada, la probabilidad de colisión hash es baja ya que la cantidad de valores de entrada (2) es mucho, mucho menor que la cantidad de valores hash (2 ^ 32 = 4,294,967,296) . La probabilidad de colisión es en realidad 1/2 ^ 32.

Sin embargo, si permite todas las cadenas posibles de exactamente 8 letras minúsculas, se le garantiza que eventualmente encontrará una colisión de hash, ya que ahora hay 26 ^ 8 = 208,827,064,576 valores de entrada, que es mucho mayor que 2 ^ 32.

Editar: quería publicar esto como un comentario, pero todavía no puedo comentar ...