Colisiones, paradoja del cumpleaños y longitud efectiva

En una sala con solo 23 personas, la probabilidad de que dos personas compartan día de cumpleaños supera el 50%. En criptografía ocurre lo mismo: para encontrar un mensaje concreto que coincida con un hash dado (resistencia a preimagen) se necesitan 2^n intentos. Pero para encontrar DOS mensajes cualesquiera que colisionen entre sí (resistencia a colisiones), el espacio de búsqueda se reduce drásticamente a la raíz cuadrada del total: 2^(n/2). Esto significa que un hash de 128 bits como MD5 solo ofrece 64 bits de seguridad frente a colisiones.

En 2012, el sofisticado ciberespionaje industrial Flame utilizó una colisión de prefijo elegido (Chosen-Prefix Collision) en MD5. Los atacantes generaron un certificado digital fraudulento que compartía el mismo hash MD5 que una solicitud legítima firmada por Microsoft. Gracias a ello, el malware pudo hacerse pasar por una actualización legítima de Windows Update en redes locales infectadas, firmando código con una firma matemática válida ante los clientes de la red.

En 2017, investigadores del CWI de Ámsterdam y Google publicaron SHAttered: dos documentos PDF con colores y textos completamente diferentes que arrojaban exactamente el mismo hash SHA-1 de 160 bits. El cálculo requirió el equivalente a 6.500 años de computación en una sola CPU y 110 años en una GPU dedicada. Este ataque demostró que la complejidad teórica de 2^63 operaciones ya era alcanzable en la práctica, forzando la jubilación inmediata de SHA-1 en navegadores y autoridades certificadoras.

Como consecuencia de la paradoja del cumpleaños, para garantizar que un sistema ofrezca un nivel de seguridad militar de 128 bits frente a adversarios con supercomputadores, el tamaño mínimo del digest debe ser de 256 bits (como SHA-256 o SHA3-256). Asimismo, NIST estandarizó SHA-3 (Keccak), que utiliza operaciones de permutación en esponja (Sponge Construction) con fases de absorción y exprimido, garantizando que un fallo futuro en la familia SHA-2 no afecte a SHA-3.