hash - funcionamiento - sha-3
¿Es seguro ignorar la posibilidad de colisiones SHA en la práctica? (3)
En primer lugar, no es cero, pero está muy cerca de 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 ser implementado y utilizado simultáneamente en una gran cantidad de computadoras (algunos diminutos microcomputadores integrados que hoy en día se encuentran casi en todas partes). En tal caso, necesita multiplicar la estimación que tiene por el mayor número posible de copias.
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 ir ignorando esta posibilidad, suponiendo que es cero?
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 da una estimación de la probabilidad de una colisión. Si ejecuta los números, verá que todos los discos duros producidos en la Tierra no pueden contener suficientes archivos de 1MB para tener una probabilidad de colisión de hasta el 0.01% para SHA-256.
Básicamente, simplemente puedes ignorar la posibilidad.
La respuesta habitual es la siguiente: ¿cuál es la probabilidad de que un asteroide rebelde se estrelle en la Tierra en el siguiente 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 a esa no es realmente muy importante.
Si tenemos una función hash "perfecta" con un tamaño de salida n , y tenemos p mensajes para hash (la longitud del mensaje individual no es importante), entonces la probabilidad de colisión es de aproximadamente p 2/2 n + 1 (esta 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 asesina masiva ocurre una vez cada 30 millones de años en promedio. Esto conduce a una probabilidad de que tal evento ocurra en el siguiente segundo a alrededor de 10 -15 . Eso es 45 órdenes de magnitud más probable que la colisión SHA-256. En pocas palabras, si encuentra colisiones SHA-256 aterradoras, entonces sus prioridades son incorrectas.
En una configuración de seguridad, donde un atacante puede elegir los mensajes que serán hash, entonces el atacante puede usar sustancialmente más de mil millones de mensajes; sin embargo, descubrirá que la probabilidad de éxito del atacante aún será insignificante. Ese es el objetivo de utilizar una función hash con una salida de 256 bits: para que los riesgos de colisión se puedan descuidar.
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.