En criptografía , un ataque de colisión sobre un hash criptográfico intenta encontrar dos entradas que produzcan el mismo valor hash, es decir, una colisión hash . Esto contrasta con un ataque de preimagen en el que se especifica un valor hash objetivo específico.
Existen aproximadamente dos tipos de ataques de colisión:
Más generalmente:
Al igual que los cifrados de clave simétrica son vulnerables a ataques de fuerza bruta , cada función hash criptográfica es inherentemente vulnerable a colisiones mediante un ataque de cumpleaños . Debido al problema del cumpleaños , estos ataques son mucho más rápidos de lo que sería una fuerza bruta. Un hash de n bits se puede romper en 2 n /2 pasos de tiempo (evaluaciones de la función hash).
Dicho matemáticamente, un ataque de colisión encuentra dos mensajes diferentes m1 y m2 , tales que hash(m1) = hash(m2) . En un ataque de colisión clásico, el atacante no tiene control sobre el contenido de ninguno de los mensajes, pero el algoritmo los elige arbitrariamente.
Es posible realizar ataques más eficientes empleando criptoanálisis de funciones hash específicas. Cuando se descubre un ataque de colisión y se descubre que es más rápido que un ataque de cumpleaños, una función hash a menudo se denuncia como "rota". La competencia de funciones hash del NIST fue inducida en gran medida por ataques de colisión publicados contra dos funciones hash muy utilizadas, MD5 [1] y SHA-1 . Los ataques de colisión contra MD5 han mejorado tanto que, a partir de 2007, tardan sólo unos segundos en un ordenador normal. [2] Las colisiones hash creadas de esta manera suelen tener una longitud constante y en gran medida no están estructuradas, por lo que no se pueden aplicar directamente para atacar protocolos o formatos de documentos generalizados.
Sin embargo, es posible encontrar soluciones abusando de las construcciones dinámicas presentes en muchos formatos. De esta forma se crearían dos documentos lo más similares posible para tener el mismo valor hash. Un documento se mostraría a una autoridad para que lo firmara y luego la firma se podría copiar al otro archivo. Un documento malicioso de este tipo contendría dos mensajes diferentes en el mismo documento, pero mostraría condicionalmente uno u otro mediante cambios sutiles en el archivo:
Una extensión del ataque de colisión es el ataque de colisión de prefijo elegido, que es específico de las funciones hash Merkle-Damgård . En este caso, el atacante puede elegir dos documentos arbitrariamente diferentes y luego agregar diferentes valores calculados que den como resultado que todos los documentos tengan el mismo valor hash. Este ataque normalmente es más difícil, un hash de n bits se puede romper en 2 (n/2)+1 pasos de tiempo, pero es mucho más poderoso que un ataque de colisión clásico.
Matemáticamente expresado, dados dos prefijos diferentes p 1 , p 2 , el ataque encuentra dos sufijos s 1 y s 2 tales que hash ( p 1 ∥ s 1 ) = hash ( p 2 ∥ s 2 ) (donde ∥ es la operación de concatenación ) .
También son posibles ataques más eficientes empleando criptoanálisis de funciones hash específicas. En 2007, se descubrió un ataque de colisión de prefijo elegido contra MD5, que requirió aproximadamente 250 evaluaciones de la función MD5. El documento también muestra dos certificados X.509 para diferentes nombres de dominio, con valores hash en colisión. Esto significa que se podría pedir a una autoridad certificadora que firme un certificado para un dominio y luego ese certificado (especialmente su firma) podría usarse para crear un nuevo certificado falso para hacerse pasar por otro dominio. [5]
En diciembre de 2008 se publicó un ataque de colisión del mundo real cuando un grupo de investigadores de seguridad publicó un certificado de firma X.509 falsificado que podría usarse para hacerse pasar por una autoridad certificadora , aprovechando un ataque de colisión de prefijo contra la función hash MD5. Esto significaba que un atacante podría hacerse pasar por cualquier sitio web protegido por SSL como un intermediario , subvirtiendo así la validación de certificados integrada en cada navegador web para proteger el comercio electrónico . Es posible que las autoridades reales no puedan revocar el certificado falso y también podría tener un tiempo de vencimiento falsificado arbitrariamente. Aunque se sabía que MD5 era muy débil en 2004, [1] las autoridades certificadoras todavía estaban dispuestas a firmar certificados verificados por MD5 en diciembre de 2008, [6] y al menos un certificado de firma de código de Microsoft todavía usaba MD5 en mayo de 2012.
El malware Flame utilizó con éxito una nueva variación de un ataque de colisión de prefijo elegido para falsificar la firma del código de sus componentes mediante un certificado raíz de Microsoft que todavía usaba el algoritmo MD5 comprometido. [7] [8]
En 2019, los investigadores encontraron un ataque de colisión de prefijo elegido contra SHA-1 con una complejidad informática de entre 266,9 y 269,4 y un costo de menos de 100.000 dólares estadounidenses. [9] [10] En 2020, los investigadores redujeron la complejidad de un ataque de colisión de prefijo elegido contra SHA-1 a 2 63,4 . [11]
Muchas aplicaciones de funciones hash criptográficas no dependen de la resistencia a las colisiones , por lo que los ataques de colisión no afectan su seguridad. Por ejemplo, los HMAC no son vulnerables. [12] Para que el ataque sea útil, el atacante debe tener el control de la entrada a la función hash.
Debido a que los algoritmos de firma digital no pueden firmar una gran cantidad de datos de manera eficiente, la mayoría de las implementaciones utilizan una función hash para reducir ("comprimir") la cantidad de datos que deben firmarse a un tamaño constante. Los esquemas de firma digital a menudo se vuelven vulnerables a colisiones de hash tan pronto como la función hash subyacente prácticamente se rompe; Técnicas como el hash aleatorio (salado) ganarán tiempo extra al requerir un ataque previo a la imagen más duro . [13]
El escenario de ataque habitual es el siguiente:
En 2008, los investigadores utilizaron un ataque de colisión de prefijo elegido contra MD5 utilizando este escenario para producir un certificado de autoridad de certificación fraudulento . Crearon dos versiones de un certificado de clave pública TLS , una de las cuales parecía legítima y fue enviada para su firma por la autoridad certificadora RapidSSL. La segunda versión, que tenía el mismo hash MD5, contenía indicadores que indicaban a los navegadores web que lo aceptaran como una autoridad legítima para emitir otros certificados arbitrarios. [14]
La inundación de hash (también conocida como HashDoS [15] ) es un ataque de denegación de servicio que utiliza colisiones de hash para explotar el tiempo de ejecución del peor de los casos (sonda lineal) de las búsquedas de tablas hash . [16] Se describió originalmente en 2003. Para ejecutar un ataque de este tipo, el atacante envía al servidor múltiples datos que codifican el mismo valor y luego intenta que el servidor realice búsquedas lentas. Como el enfoque principal de las funciones hash utilizadas en las tablas hash era la velocidad en lugar de la seguridad, la mayoría de los principales lenguajes de programación se vieron afectados, [17] y aún aparecen nuevas vulnerabilidades de esta clase una década después de la presentación original. [dieciséis]
Para evitar la inundación de hash sin hacer que la función hash sea demasiado compleja, se introducen funciones hash con clave más nuevas , con el objetivo de seguridad de que las colisiones sean difíciles de encontrar mientras se desconozca la clave. Pueden ser más lentos que los hashes anteriores, pero siguen siendo mucho más fáciles de calcular que los hashes criptográficos. A partir de 2021, SipHash (2012) de Jean-Philippe Aumasson y Daniel J. Bernstein es la función hash más utilizada en esta clase. [18] (Los hashes "simples" sin clave siguen siendo seguros de usar siempre que la tabla hash de la aplicación no sea controlable desde el exterior).
Es posible realizar un ataque análogo para llenar los filtros Bloom utilizando un ataque de preimagen (parcial). [19]
[...] podemos encontrar colisiones para MD5 en aproximadamente 2 24,1 compresiones para los IHV recomendados, lo que tarda aprox. 6 segundos en un Pentium 4 de 2,6 GHz.
{{cite journal}}: Citar diario requiere |journal=( ayuda ){{cite journal}}: Citar diario requiere |journal=( ayuda )Debido a la forma en que se utilizan las funciones hash en la construcción HMAC, las técnicas utilizadas en estos ataques recientes no se aplican.