Ataque de colisión

Un ataque de colisión en criptografía  es la búsqueda de dos bloques de entrada diferentes de una función hash criptográfica que produzcan el mismo valor hash, es decir, una colisión hash . A diferencia del ataque de preimagen , el valor hash no se elige deliberadamente.

Aproximadamente[ aclarar ] Hay dos tipos diferentes de ataques de colisión:

Ataque de colisión clásico

El ataque de colisión encuentra dos mensajes diferentes m1 y m2 tales que . En el caso clásico de un ataque, el atacante no tiene control sobre el contenido de los mensajes, sino que son elegidos aleatoriamente por el algoritmo. Muchos criptosistemas simétricos son vulnerables a los ataques de fuerza bruta , cualquier función hash criptográfica es, por definición, vulnerable a un ataque de cumpleaños . Debido a la paradoja del cumpleaños, este último método de ataque puede ser mucho más rápido que el método de fuerza bruta. Un hash de N bits se puede dividir 2n /2 veces (mediante el cálculo de una función hash). Los ataques más efectivos son posibles cuando se utiliza el criptoanálisis en una función hash específica. Cuando un ataque de colisión es más rápido que un ataque de "cumpleaños", las funciones hash a menudo se denuncian como "rotas". La creación de la función hash SHA-3 (concurso) fue impulsada en gran medida por la necesidad de reemplazar las antiguas funciones MD5 [1] y SHA-1 . Los ataques de colisión contra el algoritmo MD5 han mejorado tanto que en un ordenador normal tardan solo unos segundos. [2] Las colisiones hash generadas de esta manera son generalmente de longitud constante y en gran parte no estructuradas, por lo que no se pueden aplicar directamente para atacar protocolos o formatos de documentos comunes. Sin embargo, las soluciones alternativas son posibles al abusar de las construcciones dinámicas presentes en muchos formatos. Así, se crearán dos documentos idénticos entre sí para que tengan el mismo valor hash. Si un documento está firmado por una persona de confianza, su firma se puede copiar en otro archivo. Dicho documento malicioso contendría dos mensajes diferentes en el mismo documento, pero aún podría mostrar cualquiera de ellos a través de pequeños cambios en el archivo:

Ataque de colisión con un prefijo dado

El resultado de la mejora del ataque de colisión fue el ataque de colisión con un prefijo dado, diseñado para la estructura Merkle-Damgard . En este caso, un atacante puede elegir 2 documentos aleatorios diferentes y luego rellenarlos con 2 valores computados diferentes para que los 2 documentos terminen con el mismo valor hash. Este ataque es más grave que su versión clásica.

Matemáticamente hablando, hay 2 prefijos diferentes p1, p2 , sus 2 complementos m1 y m2 se calculan de tal manera que hash(p1 ∥ m1) = hash(p2 ∥ m2) (donde ∥ es la operación de concatenación ).

En 2007, se creó un ataque de colisión de hash MD5 prefijado, que requirió aproximadamente 250 cálculos de función MD5 . La nota presentaba dos certificados X.509 para diferentes nombres de dominio que tienen la misma función hash. Esto significa que el certificado de un dominio de confianza puede ser utilizado por otro dominio desconocido. [5]

Un ataque de colisión real se publicó en diciembre de 2008 cuando un grupo de investigadores de seguridad publicó un certificado de firma X.509 falso que se puede usar para autorizar un certificado de forma anónima mediante un ataque de colisión con un prefijo hash MD5 determinado. Esto significaba que un atacante podía falsificar cualquier sitio web protegido por TLS como intermediario , violando así la validación del certificado integrado en cada navegador web para proteger el comercio electrónico . Un certificado falso no puede ser revocado por partes confiables, también puede tener una cantidad arbitraria de tiempo para caducar. A pesar de las debilidades de MD5 encontradas en 2004, [1] en diciembre de 2008 quedó claro que mucha gente todavía usa certificados con esta función hash, [6] y al menos Microsoft todavía la usaba en mayo de 2012.

En Flame , el malware usó con éxito una nueva variante del ataque de colisión prefijado para falsificar componentes de firma de código usando certificados raíz de Microsoft, que todavía usaban el algoritmo MD5 comprometido. [7] [8]

Esquema de ataque

Muchas aplicaciones con funciones hash criptográficas no requieren protección colisión no pueden pasar por alto su protección Por ejemplo, los HMAC no están sujetos a este tipo de ataque. [9] Para un ataque exitoso, el atacante debe tener control sobre la entrada.

Firmas electrónicas

Dado que los algoritmos de firma electrónica no pueden firmar grandes cantidades de datos de manera eficiente, muchos complementos utilizan funciones de compresión de datos para firmarlos en un tamaño fijo. Los esquemas de firma electrónica a menudo son propensos a colisiones a pesar de que utilizan una técnica aleatoria de hash. [diez]

Por lo general, el ataque es así:

  1. Eve crea 2 documentos diferentes A y B con los mismos valores hash. Eve busca engañar a Bob haciendo pasar su documento por el de Alice.
  2. Eve envía el documento A a Alice , quien confía en el contenido del documento, firma su hash y envía la firma a Eve.
  3. Eve adjunta la firma del documento A al documento B.
  4. Luego, Eve envía la firma y el documento B a Bob , alegando que Alice firmó el documento. Dado que la firma electrónica solo verifica el valor hash del documento B, Bob no sabe acerca de la sustitución.

En 2008, los investigadores atacaron el prefijo MD5 utilizando el script anterior para crear un certificado falso. Crearon 2 versiones del certificado de clave pública TLS , una de las cuales fue autenticada para la autorización RapidSSL. Otra versión, que tiene el mismo valor hash MD5, contenía indicadores que indicaban al navegador la confianza y el derecho a emitir confianza en otros certificados [11] .

Notas

  1. ↑ 1 2 Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu: colisiones para funciones hash MD4, MD5, HAVAL-128 y RIPEMD Archivado el 23 de agosto de 2011. , Cryptology ePrint Archive Report 2004/199, 16 de agosto de 2004, revisado el 17 de agosto de 2004. Consultado el 27 de julio de 2008.
  2. ↑ MJ Stevens. Sobre Colisiones para MD5  (neopr.) . - 2007. - Junio.
  3. ↑ Magnus Daum, Stefan Lucks. Hash Collisions (El ataque del mensaje envenenado) . Sesión de culo de Eurocrypt 2005 . Archivado desde el original el 27 de marzo de 2010.
  4. ↑ 1 2 3 Max Gebhardt, Georg Illies, Werner Schindler. Una nota sobre el valor práctico de las colisiones de hash único para formatos de archivo especiales  (inglés)  : diario.
  5. ↑ Marc Stevens, Arjen Lenstra, Benne de Weger. Chosen-prefix Collisions for MD5 and Colliding X.509 Certificates for Different Identities  (inglés)  : revista. - 2007. - 30 de noviembre.
  6. ↑ Alexander Sotirov. Creación de un certificado de CA falso (enlace no disponible) (30 de diciembre de 2008). Fecha de acceso: 15 de diciembre de 2015. Archivado desde el original el 18 de abril de 2012. 
  7. ↑ Microsoft publica el aviso de seguridad 2718704 . Microsoft (3 de junio de 2012). Consultado el 4 de junio de 2012. Archivado desde el original el 7 de junio de 2012.
  8. ↑ Marc Stevens. El criptoanalista del CWI descubre una nueva variante de ataque criptográfico en el malware Flame Spy . Centrum Wiskunde & Informatica (7 de junio de 2012). Consultado el 9 de junio de 2012. Archivado desde el original el 28 de febrero de 2017.
  9. ↑ Preguntas y respuestas sobre la colisión de hash . Cryptography Research Inc (15 de febrero de 2005). "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". Archivado desde el original el 17 de julio de 2008.
  10. ↑ Shai Halevi y Hugo Krawczyk, Randomized Hashing and Digital Signatures Archivado el 20 de junio de 2009 en Wayback Machine .
  11. ↑ Alexander 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 . Chaos Communication Congress 2008. Archivado desde el original el 25 de marzo de 2017 . Consultado el 15 de diciembre de 2015 . Parámetro obsoleto utilizado |deadlink=( ayuda )

Enlaces