Saltar al contenido
Omnikalc

Calcular la probabilidad de colisión de un hash o de unos identificadores

Estima la probabilidad de que dos identificadores aleatorios o huellas entre n coincidan para un número de bits dado, cuántos elementos dan un 50 % de riesgo y cuántos lo mantienen por debajo de uno entre un millón.

Actualizado el
Tus datos
bits

Valor fuera de rango

Valor fuera de rango

Resultados

Probabilidad de al menos una colisión

2,674 %

Más de una entre un millón: solo es aceptable si las colisiones no tienen consecuencias graves o se detectan
Número esperado de pares en colisión
0,02711
Elementos para un 50 % de riesgo de colisión
5.056.894.494
Elementos para mantenerse por debajo de un riesgo entre un millón
6.074.001
Valores posibles, en potencia de diez (10^x)
19,27

La paradoja del cumpleaños en informática

¿Cuántas personas hacen falta en una sala para que dos de ellas tengan una probabilidad entre dos de compartir cumpleaños? Solo 23, muy por debajo de los 365 días del año. La misma sorpresa vale para las huellas hash, los identificadores aleatorios y las sumas de verificación: las colisiones aparecen mucho antes de que se llene el espacio de valores posibles. Es la cota de los cumpleaños.

La fórmula

Con b bits existen 2^b valores posibles. Para n elementos aleatorios, el número esperado de pares en colisión vale n(n − 1) ÷ 2^(b+1), y la probabilidad de al menos una colisión es aproximadamente:

p ≈ 1 − e^(−n² ÷ 2^(b+1))

El número de elementos que da un 50 % de riesgo vale aproximadamente 1,1774 × 2^(b/2): la raíz cuadrada del espacio, y no el espacio entero.

Ejemplo

Mil millones de identificadores aleatorios de 64 bits: n² ÷ 2^65 ≈ 0,0271, de modo que p ≈ 2,7 %. El 50 % se alcanza hacia los 5,06 mil millones de elementos, y mantenerse por debajo de un riesgo entre un millón limita a unos 6 millones de elementos.

Bits 50 % de colisión tras Riesgo de uno entre un millón tras
32 77.000 93
64 5,1 mil millones 6,1 millones
128 (el UUID v4 tiene 122) 2,2 × 10¹⁹ 2,6 × 10¹⁶
256 4 × 10³⁸ 4,8 × 10³⁵

Conclusiones prácticas

  • Los hash de 32 bits (CRC-32, identificadores cortos) colisionan enseguida: no los uses nunca como claves únicas.
  • Los identificadores aleatorios de 64 bits sirven para millones de filas, no para miles de millones.
  • Un UUID v4 tiene 122 bits aleatorios: harían falta unos 2,7 trillones para tener una probabilidad entre dos.
  • Truncar un SHA-256 a 8 caracteres hexadecimales deja solo 32 bits.

Colisiones accidentales y colisiones provocadas

Estas cifras suponen valores aleatorios. Un atacante que busca una colisión también necesita unos 2^(b/2) intentos: por eso se recomiendan funciones hash de al menos 256 bits para una seguridad de 128 bits. Los algoritmos rotos, como MD5 y SHA-1, permiten colisiones mucho más rápido que la cota de los cumpleaños.

Preguntas frecuentes

¿Por qué ocurren las colisiones tan pronto?

Cada elemento nuevo puede colisionar con todos los ya almacenados: el número de pares crece como n al cuadrado. Las colisiones se vuelven probables hacia la raíz cuadrada del número de valores posibles.

¿Pueden dos UUID ser idénticos?

En teoría sí, pero un UUID de versión 4 tiene 122 bits aleatorios. Harían falta unos 2,7 trillones para tener una probabilidad entre dos de un solo duplicado: con un buen generador aleatorio, en la práctica no ocurre.

¿Basta un hash de 32 bits como clave de caché?

Solo para conjuntos pequeños. Con 32 bits, una colisión se vuelve probable hacia los 77.000 elementos: por eso la caché debe comparar la clave completa o usar un hash de 64 bits o más.

¿Se aplica a los hash criptográficos?

Sí para las colisiones accidentales, y un atacante también necesita unos 2^(b/2) intentos contra una función sana. Por eso se usa SHA-256 para una seguridad de 128 bits.

¿Te ha resultado útil esta calculadora?

¡Gracias por tu opinión!

Resultados orientativos con fines informativos. No sustituyen el consejo de un profesional.