Birthday Attack
El ataque de cumpleaños explota la paradoja del cumpleaños: tras aproximadamente 2^(n/2) cálculos de hash hay un 50 % de probabilidad de encontrar una colisión en un hash de n bits, lo que dicta la longitud de salida necesaria.
Propósito
Establece la cota inferior de la longitud de salida del hash para que la búsqueda de colisiones sea inviable.
Mecanismo
Paradoja del cumpleaños: entre 23 personas hay un 50 % de probabilidad de que dos compartan cumpleaños. Para un hash con salida de n bits, unas 1.177×√(2^n) = 1.177×2^(n/2) entradas aleatorias dan una probabilidad de colisión del 50 %. De ahí que un hash de 128 bits sea inseguro con solo 2^64 intentos.
Casos de uso
- Selección de la longitud de salida del hash
- Nivel de seguridad de firmas digitales
- Evaluación de la vigencia de certificados
- Educación en criptografía
Ejemplos
- entrada
128-bit hashOutputCollision found in 2^64 trialsInsecure
Errores comunes
- Assuming an n-bit hash needs 2^n trials to collide
- Collisions take only 2^(n/2); use outputs of at least 256 bits
Términos relacionados
Collision Resistance
La resistencia a colisiones es la propiedad de una función hash por la que resulta inviable encontrar dos entradas distintas que produzcan la misma salida. El ataque del cumpleaños dicta la longitud de salida necesaria. GLOSARIO
SHA-256
SHA-256 es el miembro de la familia SHA-2 con salida de 256 bits, muy usado en TLS, blockchains y aplicaciones criptográficas, sin ataques prácticos conocidos. GLOSARIO
MD5
MD5 es una función hash criptográfica de 128 bits diseñada por Ronald Rivest; demostrada insegura por ataques de colisión, hoy solo se usa para fines no de seguridad como checksums. GLOSARIO