Ataques de cumpleaños y de colisión

En un grupo de 23 personas, la probabilidad de que dos compartan cumpleaños supera el 50 %. Con 70 personas, supera el 99,9 %. Matemáticamente, en un conjunto de tamaño N, la probabilidad de colisión supera el 50 % después de aproximadamente √N muestras. Este es el límite del cumpleaños.

Para una función hash de n bits, se puede encontrar una colisión (H(m1) = H(m2), m1 ≠ m2) con aproximadamente 2^{n/2} intentos aleatorios. Para SHA-256 (256 bits), encontrar una colisión requiere aproximadamente 2^{128} operaciones, una cantidad inviable desde el punto de vista computacional. Para MD5 (128 bits), requiere aproximadamente 2^{64}, una cantidad casi viable.

Búsqueda genérica de colisiones: genere 2^{n/2} mensajes aleatorios, calcule sus hashes, ordénelos por valor hash y encuentre los duplicados. Memoria O(2^{n/2}). El algoritmo Rho (búsqueda de ciclos de Floyd) reduce la memoria a O(1) con el mismo coste temporal. La búsqueda paralela de colisiones de van Oorschot-Wiener reduce el tiempo mediante hardware.

Wang et al. encontraron colisiones prácticas de MD5 (2004) mediante criptoanálisis diferencial, no mediante el ataque de cumpleaños. Dos mensajes diferentes de 1024 bits con el mismo hash MD5 en cuestión de segundos. Hertzbleed y las colisiones de prefijo elegido permiten crear colisiones de certificados. MD5 está completamente roto como mecanismo de resistencia a colisiones.

Es más potente: dados dos prefijos arbitrarios P1 y P2, encuentre sufijos S1 y S2 tales que H(P1||S1) = H(P2||S2). Stevens et al. (2017) encontraron colisiones de MD5 con prefijo elegido. Se utilizaron para crear un certificado de CA malicioso con una firma MD5 válida. Esto provocó que MD5 dejara de utilizarse en certificados.

SHAttered de Google (2017): primera colisión práctica de SHA-1. Dos archivos PDF diferentes con el mismo hash SHA-1. Requirió 2^{63.1} compresiones de SHA-1, equivalente a 6.500 años de CPU y 110 años de GPU. El coste fue de aproximadamente 110.000 dólares. Los navegadores dejaron de admitir los certificados SHA-1 en 2017.

En las funciones hash de Merkle-Damgård (MD5, SHA-1, SHA-2), si conoce H(m), puede calcular H(m||padding||m') sin conocer m. Esto rompe construcciones MAC como H(secret||message). La solución es utilizar HMAC (que usa un relleno interno y otro externo) o SHA-3 (construcción de esponja, inmune a la extensión de longitud).

Resistencia a colisiones: encontrar dos mensajes distintos cualesquiera con el mismo hash (un esfuerzo de 2^{n/2}). Resistencia a segunda preimagen: dado m, encontrar m' ≠ m con el mismo hash (un esfuerzo de 2^n). Resistencia a preimagen: encontrar cualquier mensaje para un hash dado (un esfuerzo de 2^n). La resistencia a colisiones es siempre la más débil.

Si MAC utiliza una función hash vulnerable a colisiones, un atacante que pueda encontrar colisiones en H podría falsificar MAC. HMAC-MD5 se considera seguro a pesar de las colisiones de MD5, porque la construcción de HMAC requiere ataques de preimagen, no solo colisiones. Sin embargo, en los sistemas nuevos debe migrar de HMAC-MD5.

Joux (2004) demostró que, para las funciones hash de Merkle-Damgård, encontrar colisiones de 2^k vías (2^k mensajes con el mismo hash) requiere solo k veces el trabajo necesario para encontrar una colisión, no k veces más. Esto agrava las vulnerabilidades de los hashes concatenados (H1(m)||H2(m) no es tan robusto como podría parecer).

Utilice SHA-256 o SHA-3 para obtener hashes resistentes a colisiones. Evite MD5 y SHA-1 para cualquier fin relacionado con la seguridad. Para MAC: HMAC-SHA-256 o HMAC-SHA-3. Para el hashing de contraseñas: Argon2 (no SHA-2 directamente). Utilice siempre SHA-3 cuando se requiera resistencia a la extensión de longitud.

¿Aproximadamente cuántas evaluaciones de hash se necesitan para encontrar una colisión en una función hash de n bits?

El ataque de cumpleaños encuentra colisiones de hash con un esfuerzo de 2^{n/2}. MD5 presenta colisiones de prefijo elegido prácticas; SHA-1 se vulneró en 2017. Los ataques de extensión de longitud rompen los MAC ingenuos H(key||msg). Utilice SHA-256 o SHA-3; utilice HMAC para autenticar mensajes. A continuación: ataques de encuentro en el medio.