Digamos que tenemos mil millones de imágenes únicas, un megabyte cada una. Calculamos el hash SHA-256 para el contenido de cada archivo. La posibilidad de colisión depende de:
- la cantidad de archivos
el tamaño del archivo único
¿Hasta dónde podemos llegar ignorando esta posibilidad, suponiendo que sea cero?
Respuestas:
La respuesta habitual es la siguiente: ¿cuál es la probabilidad de que un asteroide deshonesto se estrelle en la Tierra en el próximo segundo, destruyendo la civilización tal como la conocemos y matando a unos pocos miles de millones de personas? Se puede argumentar que cualquier evento desafortunado con una probabilidad menor que eso no es realmente muy importante.
Si tenemos una función hash "perfecto" con tamaño de salida n , y tenemos p mensajes en Hash (longitud del mensaje individual no es importante), entonces la probabilidad de colisión es de aproximadamente p 2 /2 n + 1 (esto es una aproximación que es válido para "pequeño" p , es decir, sustancialmente más pequeño que 2 n / 2 ). Por ejemplo, con SHA-256 ( n = 256 ) y mil millones de mensajes ( p = 10 9 ), entonces la probabilidad es de aproximadamente 4.3 * 10 -60 .
Una roca espacial de asesino en masa ocurre aproximadamente una vez cada 30 millones de años en promedio. Esto conduce a una probabilidad del evento un tales que ocurre en el siguiente segundo a alrededor de 10 -15 . Son 45 órdenes de magnitud más probables que la colisión SHA-256. En pocas palabras, si las colisiones SHA-256 dan miedo, sus prioridades son incorrectas.
En una configuración de seguridad, donde un atacante puede elegir los mensajes que serán procesados, entonces el atacante puede usar sustancialmente más de mil millones de mensajes; sin embargo, encontrará que la probabilidad de éxito del atacante seguirá siendo muy pequeña. Ese es el objetivo de usar una función hash con una salida de 256 bits: para que se puedan ignorar los riesgos de colisión.
Por supuesto, todo lo anterior supone que SHA-256 es una función hash "perfecta", que está lejos de ser probada. Aún así, SHA-256 parece bastante robusto.
fuente
La posibilidad de una colisión no depende del tamaño de los archivos, solo de su número.
Este es un ejemplo de la paradoja del cumpleaños. . La página de Wikipedia ofrece una estimación de la probabilidad de una colisión. Si ejecuta los números, verá que todos los discos duros jamás producidos en la Tierra no pueden contener suficientes archivos de 1 MB para tener una probabilidad de una colisión de incluso 0.01% para SHA-256.
Básicamente, simplemente puede ignorar la posibilidad.
fuente
En primer lugar, no es cero, sino muy cercano a cero .
La pregunta clave es ¿qué sucede si realmente ocurre una colisión ? Si la respuesta es "una planta de energía nuclear explotará", entonces probablemente no debería ignorar la posibilidad de colisión. En la mayoría de los casos, las consecuencias no son tan graves, por lo que puede ignorar la posibilidad de colisión.
Además, no olvide que su software (o una pequeña parte de él) podría implementarse y utilizarse simultáneamente en una gran cantidad de computadoras (algunas microcomputadoras pequeñas incrustadas que se incluyen en casi todas partes hoy en día). En tal caso, debe multiplicar la estimación que tiene por el mayor número posible de copias.
fuente