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.