Probabilidad de colisiones SHA1

Question

Dado un conjunto de 100 cadenas de igual longitud, ¿cómo se puede cuantificar la probabilidad de que una colisión de resumen SHA1 para las cuerdas sea poco probable ...?

Answer 1

son los valores hash de 160 bits generado por SHA-1 lo suficientemente grande como para asegurar la huella digital de cada bloque es único? Suponiendo valores hash aleatoria con una distribución uniforme, una colección de bloques de datos n diferentes y una función hash que genera bits b, el probabilidad p que habrá una o más colisiones está limitada por el número de pares de bloques multiplicado por la probabilidad de que un par determinado colisione.

(fuente: http://bitcache.org/faq/hash-collision-probabilities)

Answer 2

Eso es Birthday Problem - el artículo proporciona aproximaciones agradables que hacen que sea bastante fácil estimar la probabilidad. La probabilidad real será muy, muy baja; consulte this question para ver un ejemplo.

Answer 3

Bueno, la probabilidad de una colisión sería 1 - ((2^160 - 1)/2^160) * ((2^160 - 2)/2^160) * ... * ((2^160 - 99)/2^160).

Piense en la probabilidad de una colisión de 2 elementos en un espacio de 10. El primer elemento es único con una probabilidad del 100%. El segundo es único con probabilidad 9/10. Entonces, la probabilidad de que ambos sean únicos es 100% * 90%, y la probabilidad de una colisión es 1 - (100% * 90%), o 1 - ((10 - 0)/10) * ((10 - 1)/10), o 1 - ((10 - 1)/10).

Es bastante improbable. Tendría que tener muchas más cadenas para que sea una posibilidad remota.

Eche un vistazo a la tabla en this page on Wikipedia; simplemente interpola entre las filas para 128 bits y 256 bits.