Birthday Bound
El límite de cumpleaños es el suelo de complejidad de ataque fijado por la paradoja del cumpleaños: encontrar una colisión en un conjunto de N elementos requiere unas sqrt(N) muestras.
Propósito
Fija el techo de seguridad de las funciones hash y de los modos de cifrado por bloques: un hash de n bits solo ofrece 2^(n/2) de resistencia a colisiones, y los modos CBC/CTR de un bloque de n bits se repiten tras 2^(n/2) bloques.
Mecanismo
Por la paradoja del cumpleaños, el muestreo aleatorio de un conjunto de N elementos repite con alta probabilidad tras unas sqrt(N) extracciones. De ahí que una colisión de un hash de n bits requiera 2^(n/2) operaciones, y SHA-256 ofrezca 128 bits de resistencia a colisiones.
Casos de uso
- Evaluación de la fuerza de seguridad de funciones hash
- Techos de recuento de bloques para modos de cifrado por bloques
- Elección de longitudes de hash de firma