Hispanopedia Wiki
Articulo de referencia

Ataque por colisión

En criptografía , un ataque de colisión a una función hash criptográfica busca dos entradas que produzcan el mismo valor hash, es decir, una colisión de hash . Esto contrasta co...

Hispanopedia WikiContenido en espanolLectura gratuita

En criptografía , un ataque de colisión a una función hash criptográfica busca dos entradas que produzcan el mismo valor hash, es decir, una colisión de hash . Esto contrasta con un ataque de preimagen, donde se especifica un valor hash objetivo concreto.

Existen aproximadamente dos tipos de ataques de colisión:

Ataque de colisión clásico
Encuentra dos mensajes diferentes m 1 y m 2 tales que hash ( m 1 ) = hash ( m 2 ).

En términos más generales:

ataque de colisión de prefijo elegido
Dados dos prefijos diferentes p 1 y p 2 , encuentre dos sufijos s 1 y s 2 tales que hash ( p 1 ∥ s 1 ) = hash ( p 2 ∥ s 2 ), donde ∥ denota la operación de concatenación .

Ataque de colisión clásico

Al igual 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 puede romperse en 2n / 2 pasos de tiempo (evaluaciones de la función hash).

En términos matemáticos, un ataque de colisión encuentra dos mensajes diferentes .metro1{\displaystyle m_{1}}y​​metro2{\displaystyle m_{2}}⁠ , de tal manera quehash(metro1)=hash(metro2){\displaystyle hash(m_{1})=hash(m_{2})}En un ataque de colisión clásico, el atacante no tiene control sobre el contenido de ninguno de los mensajes, sino que estos son elegidos arbitrariamente por el algoritmo.

Es posible realizar ataques más eficientes empleando criptoanálisis en funciones hash específicas. Cuando se descubre un ataque de colisión y se comprueba que es más rápido que un ataque de cumpleaños, a menudo se denuncia una función hash como "rota". La competición de funciones hash del NIST fue impulsada 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 tardan unos segundos en un ordenador normal. [ 2 ] Las colisiones de hash creadas de esta manera suelen tener una longitud constante y son en gran medida no estructuradas, por lo que no se pueden aplicar directamente para atacar formatos o protocolos de documentos generalizados.

Sin embargo, es posible encontrar soluciones alternativas aprovechando las estructuras dinámicas presentes en muchos formatos. De esta forma, se crearían dos documentos lo más similares posible para que tuvieran el mismo valor hash. Un documento se presentaría a una autoridad para su firma, y ​​luego la firma se copiaría al otro archivo. Dicho documento malicioso contendría dos mensajes diferentes, pero mostraría uno u otro de forma condicional mediante sutiles modificaciones en el archivo.

  • Algunos formatos de documentos como PostScript o las macros en Microsoft Word tienen construcciones condicionales [ 3 ] [ 4 ] (si-entonces-si no) que permiten comprobar 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, donde se muestra una parte diferente de la imagen sin afectar el valor hash. [ 4 ]
  • Los archivos PDF son vulnerables a ataques de colisión mediante el uso de valores de color (de modo 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 alterar para cambiar el contenido del documento firmado. [ 4 ]

ataque de colisión de prefijo elegido

Una extensión del ataque de colisión es el ataque de colisión de prefijo elegido, específico de las funciones hash de Merkle-Damgård . En este caso, el atacante puede elegir dos documentos arbitrariamente diferentes y luego añadir valores calculados distintos que den como resultado que ambos documentos tengan el mismo valor hash. Este ataque suele ser más difícil (un hash de n bits puede romperse en 2 (n/2)+1 pasos de tiempo), pero es mucho más potente que un ataque de colisión clásico.

Enunciado 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 criptoanálisis en funciones hash específicas. En 2007, se descubrió un ataque de colisión de prefijo elegido contra MD5, que requería aproximadamente 2⁵⁰ evaluaciones de la función MD5. El artículo también muestra dos certificados X.509 para diferentes nombres de dominio, con valores hash que colisionan. Esto significa que se podría solicitar 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 fraudulento que suplante la identidad de otro dominio. [ 5 ]

En diciembre de 2008 se publicó un ataque de colisión real cuando un grupo de investigadores de seguridad publicó un certificado de firma X.509 falsificado que podía usarse para suplantar a una autoridad de certificación , aprovechando un ataque de colisión de prefijos contra la función hash MD5. Esto significaba que un atacante podía suplantar cualquier sitio web protegido con SSL como un intermediario , subvirtiendo así la validación de certificados integrada en todos los navegadores web para proteger el comercio electrónico . El certificado malicioso podría 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 con 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 aún 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 entre 2 66,9 y 2 69,4 y un costo inferior a 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 ]

Escenarios de ataque

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 efectivo, el atacante debe controlar la entrada a la función hash.

firmas digitales

Debido a que los algoritmos de firma digital no pueden firmar grandes cantidades 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 hasta un tamaño constante. Los esquemas de firma digital suelen volverse vulnerables a colisiones de hash tan pronto como la función hash subyacente se ve comprometida; técnicas como el hash aleatorio (con sal) permiten ganar tiempo adicional al requerir un ataque de preimagen más difícil . [ 13 ]

El escenario de ataque habitual es el siguiente:

  1. Mallory crea dos documentos diferentes, A y B, que tienen el mismo valor hash, es decir, una colisión. Mallory intenta engañar a Bob para que acepte el documento B, supuestamente de Alice.
  2. Mallory envía el documento A a Alice , quien está de acuerdo con lo que dice el documento, firma con su hash y envía la firma a Mallory.
  3. Mallory adjunta la firma del documento A al documento B.
  4. A continuación, Mallory envía la firma y el documento B a Bob , afirmando que Alice firmó B. Dado que la firma digital coincide con el hash del documento B, el software de Bob no puede detectar la sustitución.

En 2008, investigadores utilizaron un ataque de colisión de prefijo elegido contra MD5 , empleando 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 señalaban a los navegadores web para que la aceptaran como una autoridad legítima para emitir otros certificados arbitrarios. [ 14 ]

inundación de hash

El ataque de inundación de hash (también conocido 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 ] Fue descrito originalmente en 2003 como un ejemplo de un ataque de complejidad algorítmica. [ 17 ] Para ejecutar dicho ataque, el atacante envía al servidor múltiples piezas de datos que dan como resultado el mismo valor hash y luego intenta que el servidor realice búsquedas lentas. Dado que 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 lenguajes de programación importantes se vieron afectados, [ 17 ] y siguen apareciendo nuevas vulnerabilidades de esta clase una década después de la presentación original. [ 16 ]

Para evitar la inundación de hash sin que la función hash se vuelva excesivamente compleja, se introducen nuevas funciones hash con clave , con el objetivo de seguridad de que las colisiones sean difíciles de detectar mientras se desconozca la clave. Si bien pueden ser más lentas que las funciones hash anteriores, siguen siendo mucho más fáciles de calcular que las funciones hash criptográficas. En 2021, SipHash (2012), de Jean-Philippe Aumasson y Daniel J. Bernstein, era la función hash más utilizada en esta clase. [ 18 ] (Las funciones hash "simples" sin clave siguen siendo seguras siempre que la tabla hash de la aplicación no sea controlable desde el exterior).

Es posible realizar un ataque análogo para llenar filtros de Bloom utilizando un ataque de preimagen (parcial). [ 19 ]

Véase también

Referencias

  1. 1 2 Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu: Colisiones para las funciones hash MD4, MD5, HAVAL-128 y RIPEMD , Cryptology ePrint Archive Report 2004/199, 16 de agosto de 2004, revisado el 17 de agosto de 2004. Recuperado el 27 de julio de 2008.
  2. ↑ Stevens, MMJ (junio de 2007). Sobre colisiones para MD5 (PDF) (Máster). Universidad Tecnológica de Eindhoven. [...] 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.
  3. ↑ Magnus Daum; Stefan Lucks . "Colisiones de hash (El ataque del mensaje envenenado)" . Sesión residual de Eurocrypt 2005. Archivado del original el 27 de marzo de 2010.
  4. 1 2 3 Gebhardt, Max; Illies, Georg; Schindler, Werner (31 de octubre de 2005), Nota sobre el valor práctico de las colisiones hash únicas para formatos de archivos especiales (PDF) , Bundesamt für Sicherheit in der Informationstechnik, archivado desde el original (PDF) el 17 de septiembre de 2008.
  5. ↑ Marc Stevens; Arjen Lenstra; Benne de Weger (30 de noviembre de 2007). "Colisiones de prefijos elegidos para MD5 y colisiones de certificados X.509 para identidades diferentes" . Avances en criptología - EUROCRYPT 2007. Notas de clase en informática. Vol. 4515. pág. 1. Bibcode : 2007LNCS.4515....1S . doi : 10.1007/978-3-540-72540-4_1 . ISBN   978-3-540-72539-8.
  6. ↑ Alexander Sotirov; et al. (30-12-2008). "Creación de un certificado CA fraudulento" . Archivado del original el 18-04-2012 . Recuperado el 07-10-2009 . 
  7. ↑ "Microsoft publica el aviso de seguridad 2718704" . Microsoft . 3 de junio de 2012. Archivado del original el 7 de junio de 2012. Consultado el 4 de junio de 2012 .
  8. ↑ Marc Stevens (7 de junio de 2012). "Criptólogo del CWI descubre una nueva variante de ataque criptográfico en el malware Flame Spy" . Centrum Wiskunde & 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 representan un peligro inminente" . ZDNet .
  10. ↑ Gaëtan Leurent; Thomas Peyrin (2019-05-06). "De las colisiones a las colisiones de prefijo elegido: Aplicación a SHA-1 completo" (PDF) .
  11. ↑ Gaëtan Leurent; Thomas Peyrin (05-01-2020). "SHA-1 es un desastre: primera colisión de prefijos elegidos en SHA-1 y su aplicación a la red de confianza PGP" (PDF) .
  12. ↑ "Preguntas y respuestas sobre colisiones de hash" . Cryptography Research Inc. 15 de febrero de 2005. Archivado del 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. Archivado el 20 de junio de 2009 en la Wayback Machine.
  14. ↑ Alejandro Sotirov; Marc Stevens; Jacob Appelbaum; Arjen Lenstra; David Molnar; Dag Arne Osvik; Benne de Weger (30 de diciembre de 2008). MD5 se considera nocivo hoy en día . Congreso Comunicación del Caos 2008.
  15. ↑ Falkenberg, Andreas; Mainka, Christian; Somorovsky, Juraj; Schwenk, Jörg (2013). "Un nuevo enfoque para las pruebas de penetración DoS en servicios web". 2013 IEEE 20th International Conference on Web Services . pp. 491–498 . doi : 10.1109/ICWS.2013.72 . ISBN  978-0-7695-5025-1. S2CID 17805370 . 
  16. 1 2 "Acerca de esa vulnerabilidad de inundación de hash en Node.js... · V8" . v8.dev .
  17. 1 2 Scott A. Crosby y Dan S. Wallach. 2003. Denegación de servicio mediante ataques de complejidad algorítmica. En Actas de la 12.ª conferencia sobre el Simposio de Seguridad USENIX - Volumen 12 (SSYM'03), Vol. 12. Asociación USENIX, Berkeley, CA, EE. UU., 3-3.
  18. ↑ Jean-Philippe Aumasson y Daniel J. Bernstein (18 de septiembre de 2012). "SipHash: un PRF rápido de entrada corta" (PDF) .
  19. ↑ Gerbet, Thomas; Kumar, Amrit; Lauradoux, Cédric (12 de noviembre de 2014). El poder de las malas decisiones en los filtros Bloom (informe). INRIA Grenoble.
  • "Colisiones significativas": escenarios de ataque para explotar colisiones de hash criptográfico.
  • Generadores rápidos de colisiones MD5 y MD4 - Bishop Fox (anteriormente Stach & Liu). Crea colisiones de hash MD4 y MD5 con un innovador código que mejora las técnicas desarrolladas originalmente por Xiaoyun Wang. Con un procesador  Pentium 4 de 1,6 GHz, las colisiones MD5 se generan en un promedio de 45 minutos y las colisiones MD4 en un promedio de 5 segundos. Publicado originalmente el 22 de junio de 2006.