¿Por qué son peligrosas las colisiones MD5?

Si entraran al sistema y descargaran el archivo de contraseñas con hash, podrían, con dificultad, encontrar contraseñas que funcionen.

Aunque nadie ha podido convertir la salida del hash MD5 en el texto original. La mala noticia es que el MD5 no requiere mucho tiempo de CPU.

"Espera, ¿son malas noticias?" En realidad, lo es. Al calcular valores hash, desea tomar más tiempo de CPU, en lugar de menos. Cuanto más rápido los malos puedan probar millones y miles de millones de contraseñas, más rápido podrán llegar a la que intenta mantener en secreto.

Hice una prueba de cinco millones de contraseñas de nueve caracteres y obtuve los siguientes resultados en mi máquina (usando openssl, resultados en milisegundos):

• MD5: 2449
• SHA1: 2620
• SHA256: 3884

Si desean probar aproximadamente 5 mil millones de contraseñas, que cubrirían casi todas las contraseñas de seis caracteres posibles, el tiempo de CPU oscilaría entre aproximadamente 28 días para MD5 a 44 días para SHA256. Esto es con un solo hilo en una computadora no muy rápida. Si invirtieron unos pocos cientos de dólares en media docena de tarjetas gráficas, esto podría hacerse en horas.

Es común que el proceso de hash calcule el hash varias veces. Calcularíamos el hash de la contraseña "abc123" y obtendríamos "8be8efb0bfa ...". Si calculamos el hash del hash, obtendremos "98dead38ed2 ...". Puede ver que si hacemos esto diez o cien veces, apenas notaremos la diferencia en el tiempo, pero los malos tendrán que tomar no horas, sino días o meses.

No lo olvides, solo necesitas encontrar una cadena que contenga el valor almacenado en la tabla de contraseñas, no necesariamente el valor original. Cualquier colisión servirá. Hay formas de atacar el hash para encontrar colisiones que pueden ser más simples que este ataque de fuerza bruta. Por lo que vale, dudo que haya muchos pares de cadenas de caracteres imprimibles que tienen el mismo valor.

No estoy seguro de que esto responda exactamente a tu pregunta, pero parece relevante.

Considere un sistema de seguridad donde cada usuario tenga su propia clave secreta, que es conocida por un servidor. Cuando envían comandos al servidor, tienen el comando hash y su clave secreta y luego envían al comando el hash. El servidor hace el mismo hash y confirma que el comando fue hash con su clave secreta. Esto es básicamente lo que hace OAuth (excepto que usan SHA-1).

Si un atacante puede generar hashes sin su clave secreta, puede enviar comandos como usted sin tener acceso a su clave.

Casos similares ocurren cuando se usan funciones hash para verificar datos. Podría tener una base de datos de programas buenos conocidos en mi computadora y rechazar ejecutar cualquier programa que no esté en la base de datos. Si un atacante puede causar una colisión, puede alterar maliciosamente un programa, pero puede aparecer en la base de datos como si no hubiera cambiado. Esto es básicamente lo que hizo el malware Flame :

  

Flame se firmó con un certificado fraudulento supuestamente de la autoridad de certificación de PCA Intermediate Intermediate de Microsoft. Los autores de malware identificaron un certificado del Servicio de licencias de Microsoft Terminal Server que inadvertidamente se habilitó para la firma de código y que aún utilizaba el débil algoritmo de hashing MD5, luego produjo una copia falsificada del certificado que utilizaron para firmar algunos componentes del malware para hacerlos aparecer. tener su origen en Microsoft.

La razón por la que esto no es un problema para el hashing de contraseñas es doble:

• El uso de una función hash criptográfica normal (MD5, SHA- *, etc.) para las contraseñas de hashing está completamente dañado de todos modos. ¿Por qué molestarse en romper la función hash cuando puedes forzar la contraseña con fuerza bruta? Si realiza correctamente el hashing de contraseñas (PBKDF2), no será vulnerable, incluso si la función hash interna es MD5 (supongo que la sal y la gran cantidad de iteraciones hacen esto mucho más difícil).

• Hay muy poco sentido para encontrar una colisión de hash de contraseña. Supongo que podría iniciar sesión como alguien, suponiendo que el programa del servidor (escrito por idiotas que piensan que MD5 es una función de hashing de contraseñas) no se ahogue con su contraseña binaria gigantesca. Y, si tiene acceso a los hashes, probablemente ya tenga acceso al servidor.

Para situaciones como usar un hash de una contraseña (donde todo lo que necesita es resistencia de preimagen contra computadoras clásicas), MD5 en la práctica es básicamente tan bueno como SHA-1 y los hashes SHA-2 (SHA-256, SHA- 512). El mejor ataque publicado contra MD5 solo reduce su resistencia previa a la imagen de su complejidad de 2 ¹²⁸ en un factor de 24 (a 2 ^123.4 ), que es perfectamente seguro

Concedido si se desarrollaran computadoras cuánticas de propósito general a gran escala, los ataques de preimagen con fuerza bruta en MD5 solo requerirían aproximadamente sqrt (2 ¹²⁸ ) = 2 ⁶⁴ . Contra la amenaza de las computadoras cuánticas se recomienda usar hashes más grandes; como SHA-256 (para resistencia de preimagen) o SHA-512 (si también quieres resistencia de colisión con una complejidad superior a sqrt (2 ¹²⁸ ) para un atacante cuántico).

Sí, MD5 es ligeramente más rápido que SHA-1 y la familia SHA-2, lo cual es malo para una función hash; pero la diferencia es aproximadamente un factor de dos, que es bastante insignificante. Y como cualquier función hash criptográfica simple es demasiado rápida para los propósitos modernos, necesita realizar muchas rondas iteradas como MD5-crypt (y tiene una sal única) para evitar ataques de diccionario fáciles de usar computacionalmente.

Pero la conclusión es que los desarrolladores conscientes de la seguridad deben saber para evitar el MD5 cuando la resistencia a la colisión es necesaria. Por razones solo parcialmente justificadas, a menudo deciden evitar el MD5 incluso en dominios donde solo se necesita resistencia previa a la imagen. Tal vez no quieran enfrentarse a las críticas de otros que han oído hablar de ataques de colisión contra MD5 y no entienden la diferencia sutil entre un ataque de preimagen y un ataque de colisión. Tal vez no se hayan convencido completamente de que su sistema solo necesita resistencia previa a la imagen y que un atacante inteligente no podría explotar su sistema mediante un ataque de colisión contra el hash MD5. O tal vez sienten que, dado que el MD5 carece de resistencia a la colisión, el MD5 es inherentemente más débil que los otros y es más probable que se rompa completamente contra los ataques de preimagen antes de que se rompan las funciones de hash SHA-1 / SHA-2.