De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda

En criptografía , un ataque de colisión en un hash criptográfico intenta encontrar dos entradas que produzcan el mismo valor de hash, es decir, una colisión de hash . Esto contrasta con un ataque de preimagen en el que se especifica un valor de hash objetivo específico.

Existen aproximadamente dos tipos de ataques de colisión:

Ataque de colisión
Encuentre dos mensajes diferentes m1 y m2 tales que hash (m1) = hash (m2) .

Más generalmente:

Ataque de colisión de prefijo elegido
Dados dos prefijos diferentes p1 y p2 , encuentre dos apéndices m1 y m2 tales que hash (p1 ∥ m1) = hash (p2 ∥ m2) , donde ∥ denota la operación de concatenación .

Ataque de colisión clásico [ editar ]

Enunciado matemáticamente, 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, pero son elegidos arbitrariamente por el algoritmo.

Al igual que los cifrados de clave simétrica son vulnerables a los ataques de fuerza bruta , cada función de 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 de lo que sería una fuerza bruta. Un hash de n bits se puede romper en 2 n / 2 veces (evaluaciones de la función hash).

Es posible 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, una función hash a menudo se denuncia como "rota". La competencia de la función hash del NIST fue inducida en gran medida por los 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 toma unos segundos en una computadora 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 formatos o protocolos de documentos generalizados.

Sin embargo, son posibles soluciones si se abusa de las construcciones dinámicas presentes en muchos formatos. De esta forma se crearían dos documentos lo más parecidos posible para tener el mismo valor hash. Un documento se mostraría a una autoridad para que lo firmara, y luego la firma podría copiarse en el otro archivo. Dicho documento malicioso contendría dos mensajes diferentes en el mismo documento, pero mostraría condicionalmente uno u otro a través de cambios sutiles en el archivo:

  • Algunos formatos de documentos como PostScript o macros en Microsoft Word tienen construcciones condicionales. [3] [4] (si-entonces-si no) que permiten probar si una ubicación en el archivo tiene un valor u otro para controlar lo que se muestra.
  • Los archivos TIFF pueden contener imágenes recortadas, con una parte diferente de una imagen que se muestra sin afectar el valor hash. [4]
  • Los archivos PDF son vulnerables a los ataques de colisión mediante el uso de valores de color (de manera que el texto de un mensaje se muestra con un color blanco que se mezcla con el fondo y el texto del otro mensaje se muestra con un color oscuro) que luego se puede modificar para cambiar el contenido del documento firmado. [4]

Ataque de colisión de prefijo elegido [ editar ]

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 dan como resultado que todos los documentos tengan el mismo valor hash. Este ataque es mucho más poderoso que un ataque de colisión clásico.

Enunciado matemáticamente, dados dos prefijos diferentes p1, p2 , el ataque encuentra dos apéndices m1 y m2 tales que hash (p1 ∥ m1) = hash (p2 ∥ m2) (donde ∥ es la operación de concatenación ).

En 2007, se encontró un ataque de colisión de prefijo elegido contra MD5, que requirió aproximadamente 2 50 evaluaciones de la función MD5. El documento también demuestra dos certificados X.509 para diferentes nombres de dominio, con valores hash en conflicto. Esto significa que se le 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 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 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 no puede ser revocado por autoridades reales, y también podría tener un tiempo de caducidad 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 usó con éxito una nueva variación 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 aún 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 entre 2 66,9 y 2 69,4 y costaba menos de 100.000 dólares estadounidenses. [9] [10] En 2020, los investigadores redujeron la complejidad del ataque de colisión de prefijo elegido contra SHA-1 a 2 63,4 . [11]

Escenarios de ataque [ editar ]

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.

Firmas digitales [ editar ]

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 registrarse a un tamaño constante. Los esquemas de firma digital suelen ser vulnerables a las colisiones de hash, a menos que se utilicen técnicas como el hash aleatorio. [13]

El escenario de ataque habitual es el siguiente:

  1. Mallory crea dos documentos A y B diferentes que tienen un valor hash idéntico, es decir, una colisión. Mallory busca engañar a Bob para que acepte el documento B, aparentemente de Alice.
  2. Mallory envía el documento A a Alice , quien acepta lo que dice el documento, firma su hash y envía la firma a Mallory.
  3. Mallory adjunta la firma del documento A al documento B.
  4. Mallory luego envía la firma y el documento B a Bob , alegando que Alice firmó B. Debido a que la firma digital coincide con el hash del documento B, el software de Bob no puede detectar la sustitución.

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 no autorizado . 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 de 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 autoridad legítima para emitir otros certificados arbitrarios. [14]

Uso en ataques DoS [ editar ]

En 2003, se describió un ataque de denegación de servicio (DoS) que utilizaba colisiones hash para explotar el tiempo de ejecución del peor de los casos de búsquedas en tablas hash. [15] Este problema afectó a la mayoría de los principales lenguajes de programación, ya que utilizaban funciones hash más débiles.

Referencias [ editar ]

  1. ^ a b Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu: Collisions for Hash Functions MD4, MD5, HAVAL-128 y RIPEMD , Cryptology ePrint Archive Report 2004/199, 16 de agosto de 2004, revisado el 17 de agosto de 2004. Obtenido el 27 de julio de 2008.
  2. ^ MMJ Stevens (junio de 2007). "Sobre colisiones para MD5" (PDF) . [...] podemos encontrar colisiones para MD5 en aproximadamente 2 compresiones 24.1 para IHV recomendados que toman aprox. 6 segundos en un Pentium 4 de 2.6GHz. Cite journal requiere |journal=( ayuda )
  3. ^ Magnus Daum; Stefan Lucks . "Hash Collisions (El ataque de mensaje envenenado)" . Eurocrypt 2005 sesión de grupa . Archivado desde el original el 27 de marzo de 2010.
  4. ^ a b c Max Gebhardt; Georg Illies; Werner Schindler. "Una nota sobre el valor práctico de las colisiones de hash único para formatos de archivo especiales" (PDF) . Cite journal requiere |journal=( ayuda )
  5. ^ Marc Stevens; Arjen Lenstra; Benne de Weger (30 de noviembre de 2007). "Colisiones de prefijo elegido para certificados MD5 y X.509 en colisión para diferentes identidades" . Cite journal requiere |journal=( ayuda )
  6. ^ Alexander Sotirov; et al. (30 de diciembre de 2008). "Creación de un certificado de CA falso" . Archivado desde el original el 18 de abril de 2012 . Consultado el 7 de octubre de 2009 .
  7. ^ "Microsoft publica el aviso de seguridad 2718704" . Microsoft . 3 de junio de 2012. Archivado desde el original el 7 de junio de 2012 . Consultado el 4 de junio de 2012 .
  8. ^ Marc Stevens (7 de junio de 2012). "Criptoanalista CWI descubre nueva variante de ataque criptográfico en Flame Spy Malware" . Centrum Wiskunde e Informatica . Consultado el 9 de junio de 2012 .
  9. ↑ Catalin Cimpanu (13 de mayo de 2019). "Los ataques de colisión SHA-1 son ahora realmente prácticos y un peligro inminente" . ZDNet .
  10. ^ Gaëtan Leurent; Thomas Peyrin (6 de mayo de 2019). "De las colisiones a la aplicación de colisiones de prefijo elegido a SHA-1 completo" (PDF) .
  11. ^ Gaëtan Leurent; Thomas Peyrin (5 de enero de 2020). "SHA-1 es un desastre: primera colisión de prefijo elegido en SHA-1 y aplicación a PGP Web of Trust" (PDF) .
  12. ^ "Preguntas y respuestas de Hash Collision" . Cryptography Research Inc. 2005-02-15. Archivado desde el original el 17 de julio de 2008. 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
  13. ^ Shai Halevi y Hugo Krawczyk, Hashing aleatorio y firmas digitales
  14. ^ Alexander Sotirov; Marc Stevens; Jacob Appelbaum; Arjen Lenstra; David Molnar; Dag Arne Osvik; Benne de Weger (30 de diciembre de 2008). MD5 considerado dañino hoy . Congreso de Comunicación del Caos 2008.
  15. ^ "Ataque Hash DoS en la Wayback Machine" . Crossmatch, parte de HID Global . Archivado desde el original el 17 de agosto de 2019 . Consultado el 17 de agosto de 2019 .

Enlaces externos [ editar ]

  • "Colisiones significativas", escenarios de ataque para aprovechar las colisiones de hash criptográficas
  • Generadores de colisión rápidos MD5 y MD4 - Bishop Fox (anteriormente Stach & Liu). Cree colisiones hash MD4 y MD5 utilizando un código nuevo e innovador que mejora las técnicas desarrolladas originalmente por Xiaoyun Wang. Con un Pentium 4 de 1,6 GHz, las colisiones MD5 se pueden generar en un promedio de 45 minutos y las colisiones MD4 se pueden generar en un promedio de 5 segundos. Publicado originalmente el 22 de junio de 2006.