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 donde se especifica un valor hash objetivo específico.
Existen aproximadamente dos tipos de ataques de colisión:
De manera más general:
De la misma manera que los cifrados de clave simétrica son vulnerables a los ataques de fuerza bruta , toda función hash criptográfica es inherentemente vulnerable a las colisiones mediante un ataque de cumpleaños . Debido al problema del cumpleaños , estos ataques son mucho más rápidos que un ataque de fuerza bruta. Un hash de n bits se puede descifrar en 2 n /2 pasos de tiempo (evaluaciones de la función hash).
En términos matemáticos, un ataque de colisión encuentra dos mensajes diferentes m1 y m2 , de modo 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, sino que el algoritmo los elige arbitrariamente.
Se pueden realizar ataques más eficientes empleando el criptoanálisis para 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, a menudo se denuncia una función hash 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, solo se necesitan unos segundos en una computadora normal. [2] Las colisiones de hash creadas de esta manera suelen tener una longitud constante y en gran parte no están estructuradas, por lo que no se pueden aplicar directamente para atacar formatos o protocolos de documentos generalizados.
Sin embargo, es posible encontrar soluciones alternativas abusando de las construcciones dinámicas presentes en muchos formatos. De esta manera, se crearían dos documentos que fueran lo más similares posible para tener el mismo valor hash. Se mostraría un documento a una autoridad para que lo firmara y luego se podría copiar la firma 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 de Merkle-Damgård . En este caso, el atacante puede elegir dos documentos arbitrariamente diferentes y luego agregar diferentes valores calculados que dan como resultado que todos los documentos tengan un valor hash igual. 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, 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 es posible realizar ataques más eficientes empleando el criptoanálisis para funciones hash específicas. En 2007, se descubrió un ataque de colisión de prefijo elegido contra MD5, que requería aproximadamente 250 evaluaciones de la función MD5. El artículo también demuestra dos certificados X.509 para diferentes nombres de dominio, con valores hash en conflicto. Esto significa que se podría pedir a una autoridad de certificación 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 en el mundo real cuando un grupo de investigadores de seguridad publicó un certificado de firma X.509 falsificado que podía usarse para hacerse pasar por una autoridad de certificación , aprovechando un ataque de colisión de prefijo contra la función hash MD5. Esto significaba que un atacante podía hacerse pasar por cualquier sitio web protegido por SSL como un intermediario , subvirtiendo así la validación de certificados incorporada en cada navegador web para proteger el comercio electrónico . El certificado falso puede no ser revocable por las autoridades reales y también podría tener un tiempo de expiración falsificado arbitrario. Aunque se sabía que MD5 era muy débil en 2004, [1] las autoridades de certificación 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 variante de un ataque de colisión de prefijo elegido para falsificar la firma de código de sus componentes mediante un certificado raíz de Microsoft que todavía utilizaba 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 computacional de entre 2,66,9 y 2,69,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 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 se deben firmar a un tamaño constante. Los esquemas de firma digital a menudo se vuelven vulnerables a las colisiones de hash tan pronto como la función hash subyacente está prácticamente rota; técnicas como el hash aleatorio (salado) ganarán tiempo adicional al requerir el ataque de preimagen más difícil . [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 de certificación RapidSSL. La segunda versión, que tenía el mismo hash MD5, contenía indicadores que indicaban a los navegadores web que la 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 peor caso (sonda lineal) de tiempo de ejecución de las búsquedas en tablas hash . [16] Se describió originalmente en 2003. Para ejecutar un ataque de este tipo, el atacante envía al servidor múltiples piezas de datos que convierten en hash 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] con nuevas vulnerabilidades de esta clase que siguen apareciendo una década después de la presentación original. [16]
Para evitar la inundación de hashes sin hacer que la función hash sea demasiado compleja, se introducen nuevas funciones hash con clave , con el objetivo de seguridad de que las colisiones sean difíciles de encontrar mientras la clave sea desconocida. Pueden ser más lentas 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 compresiones de 24,1 para los IHV recomendados, lo que lleva aproximadamente 6 segundos en un Pentium 4 de 2,6 GHz.
{{cite journal}}: Requiere citar revista |journal=( ayuda ){{cite journal}}: Requiere citar revista |journal=( ayuda )Debido a la forma en que se utilizan las funciones hash en la construcción de HMAC, las técnicas utilizadas en estos ataques recientes no se aplican.