stringtranslate.com

Ataque de colisión

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:

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

De manera más general:

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

Ataque de colisión clásico

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:

Ataque de colisión con prefijo elegido

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 1s 1 ) = hash ( p 2s 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]

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 útil, el atacante debe tener el control de la entrada a la función hash.

Firmas digitales

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:

  1. Mallory crea dos documentos diferentes, A y B, que tienen un valor hash idéntico, es decir, una colisión. Mallory intenta 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. Luego Mallory envía la firma y el documento B a Bob , afirmando que Alice firmó a B. Debido a que la firma digital coincide con el hash del documento B, el software de Bob no puede detectar la sustitución. [ cita requerida ]

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]

Inundación de hash

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]

Véase también

Referencias

  1. ^ ab Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu: Colisiones para funciones hash MD4, MD5, HAVAL-128 y RIPEMD, Informe de archivo de Cryptology ePrint 2004/199, 16 de agosto de 2004, revisado el 17 de agosto de 2004. Recuperado 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 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 )
  3. ^ Magnus Daum; Stefan Lucks . «Colisiones de hash (el ataque del mensaje envenenado)». Sesión de Eurocrypt 2005. Archivado desde el original el 27 de marzo de 2010.
  4. ^ abc Max Gebhardt; Georg Illies; Werner Schindler (4 de enero de 2017). "Una nota sobre el valor práctico de las colisiones de hash único para formatos de archivos especiales" (PDF) . {{cite journal}}: Requiere citar revista |journal=( ayuda )
  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. Apuntes 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 de diciembre de 2008). "Creación de un certificado CA no autorizado". 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). "Cryptanalist de 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 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 prefijos elegidos en SHA-1 y aplicación a la red de confianza de PGP" (PDF) .
  12. ^ "Preguntas y respuestas sobre colisiones de hash". Cryptography Research Inc. 15 de febrero de 2005. 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 Archivado el 20 de junio de 2009 en 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 dañino 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 . págs. 491–498. doi :10.1109/ICWS.2013.72. ISBN 978-0-7695-5025-1.S2CID 17805370  .
  16. ^ ab "Acerca de esa vulnerabilidad de inundación de hash en Node.js... · V8". v8.dev .
  17. ^ 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 de 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: una PRF rápida de entrada corta" (PDF) .
  19. ^ Gerbet, Thomas; Kumar, Amrit; Lauradoux, Cédric (12 de noviembre de 2014). El poder de las malas decisiones en Bloom Filters (informe). INRIA Grenoble.

Enlaces externos