Hash Collision: ¿cuáles son las posibilidades?

Tengo un código en mi sitio con PHP que crea un hash aleatorio (usando sha1() ) y lo uso para unir registros en la base de datos.

¿Cuáles son las posibilidades de una colisión? Si genero el hash, primero verifique si está en la base de datos (prefiero evitar una consulta adicional) o insértelo automáticamente, según la probabilidad de que probablemente no colisione con otro.

Si supone que SHA-1 hace un buen trabajo, puede concluir que existe una probabilidad 1 en 2 ^ 160 de que dos mensajes tengan el mismo hash (ya que SHA-1 produce un hash de 160 bits).

2 ^ 160 es un número ridículamente grande. Son aproximadamente 10 ^ 48. Incluso si tiene un millón de entradas en su base de datos, todavía hay una probabilidad de 1 en 10 ^ 42 de que una nueva entrada comparta el mismo hash.

SHA-1 ha demostrado ser bastante bueno, así que no creo que deba preocuparse por las colisiones en absoluto.

Como nota al margen, use la función raw_output de PHP cuando use SHA-1 ya que esto conducirá a una cadena más corta y por lo tanto hará que las operaciones de su base de datos sean un poco más rápidas.

EDITAR: Para abordar la paradoja del cumpleaños, una base de datos con 10 ^ 18 (un millón de millones de entradas) tiene una probabilidad de alrededor de 1 en 0.0000000000003 de una colisión. Realmente no vale la pena preocuparse por eso.

Utilice un esquema de cifrado simétrico y una clave de servidor privada para encriptar la ID (y otros valores) cuando los envíe al cliente y descifre nuevamente en la recepción. Tenga cuidado de que su función criptográfica proporcione comprobaciones de confidencialidad e integridad.

Esto le permite usar valores razonables cuando habla con el DB sin ningún tipo de colisión , una gran seguridad cuando habla con el cliente y reduce su probabilidad de aterrizar en el primer WTF en aproximadamente 2 ^ 160.

Ver también Pounding A Nail: Old Shoe o Glass Bottle? !

por qué no hacer algo que garantice que no habrá colisiones, y se asegura de que nadie pueda cambiar un parámetro GET para ver algo que no debería: usando un salt, combine el id y su hash.

 $salt = "salty"; $key = sha1($salt . $id) . "-" . $id; // 0c9ab85f8f9670a5ef2ac76beae296f47427a60a-5 

incluso si tropiezas accidentalmente con dos números que tienen exactamente el mismo hash sha1 (con tu sal), entonces la tecla $ seguirá siendo diferente y evitarás todas las colisiones.