Ataque de colisión

En el campo de la criptografía, se denomina ataque de colisión a aquel ataque hacia una función hash criptográfica que tiene el objetivo de hallar dos cadenas que generen el mismo resultado (es decir, una colisión). Esto entra en contraste con un ataque de preimage, en el cual se especifica un resultado específico de la función.

Funciones hash criptográficas

Esta sección es un extracto de Función hash criptográfica.[editar]

Una función hash criptográfica (específicamente SHA-1) en ejecución. Un pequeño cambio en la entrada (en la palabra "over") cambia drásticamente la salida (resumen). Este es el llamado efecto avalancha.

Funciones hash criptográficas (CHF) son aquellas que cifran una entrada y actúan de forma parecida a las funciones hash, ya que comprimen la entrada a una salida de menor longitud y son fáciles de calcular.

Se llaman funciones hash criptográficas a aquellas funciones hash que se utilizan en el área de la criptografía. Este tipo de funciones se caracterizan por cumplir propiedades que las hacen idóneas para su uso en sistemas que confían en la criptografía para dotarse de seguridad. Estas propiedades las hacen resistentes frente ataques maliciosos que intentan romper esa seguridad.

Ataque de colisión clásico

Los algoritmos de cifrado simétrico son vulnerables a ataques de fuerza bruta. De la misma manera, todas las funcionas hash criptográficas son, inherentemente, capaces de ser atacadas con un ataque de cumpleaños. Como consecuencia de la paradoja del cumpleaños, estos ataques son considerablemente más rápidos que la fuerza bruta. Un hash de n bits puede ser roto en 2^n/2 pasos de tiempo (es decir, el número de veces que se calcula el resultado de la función).

En términos matemáticos, un ataque de colisión busca encontrar dos mensajes, m1 y m2, tal que hash(m1) = hash(m2). En un ataque de colisión clásico, el atacante no puede controlar el contenido de ninguno de los dos mensajes; estos son generados arbitrariamente por un algoritmo.

Es posible lograr ataques más eficientes si se aplica el criptoanálisis a ciertas funciones hash específicas. Cuando es descubierto un ataque de colisión y se verifica que es más rápido que un ataque de cumpleaños, llega a ser frecuente que se mencione que está «rota» la función hash. La NIST hash function competition fue, en gran parte, organizada gracias a que se publicaron ataques de colisión hacia funciones hash muy comúnmente utilizadas: MD5^[1]​ y SHA-1. Los ataques contra MD5 han mejorado hasta el punto que, para 2007, toma pocos segundos efectuar un ataque en una computadora normal.^[2]​ Las colisiones generadas de esta manera son usualmente de longitud constante y, en gran parte, no tienen estructura alguna, por lo que no pueden ser directamente aplicadas para atacar formatos o protocolos que sean comunes.

Sin embargo, es posible encontrar formas de sobrellevar estas limitaciones empleando construcciones dinámicas, presentes en muchos formatos. Usando esta técnica, se crearían dos documentos distintos de forma que sean lo más similares como sea posible, pero con el mismo hash. Se mostraría uno de los documentos a una autoridad (para que sea firmado), para luego copiar la firma hacia el otro documento. Dicho documento contendría dos mensajes distintos en el mismo documento, pero mostraría uno u otro dependiendo de ciertos cambios sutiles en el archivo:

• Algunos formatos, como PostScript o los macros de Microsoft Word, tienen construcciones condicionales.^[3]​^[4]​ (if-then-else) que permiten probar si una ubicación en el archivo tiene uno u otro valor, esto para controlar el contenido mostrado.
• Los archivos TIFF pueden contener imágenes recortadas, lo cual permite mostrar una parte distinta de la imagen sin afectar el valor de la función hash.^[4]​
• Los archivos PDF son vulnerables a ataques de colisión si se utilizan valores de color (por ejemplo, para que el texto de cierto mensaje sea blanco, combinándose con el fondo, y que el texto del otro mensaje esté en un color oscuro), los cuales pueden ser alterados para cambiar el contenido del documento.^[4]​

Ataque de colisión de prefijo determinado

Una forma extendida del ataque de colisión es el ataque de colisión de prefijo predeterminado, el cual afecta en específico a las funciones hash que utilizan el esquema Merkle–Damgård. En este escenario el atacante es capaz de elegir dos documentos arbitariamente distintos, para luego incluir ciertos valores generados al final de los documentos, con el resultado de que ambos documentos tengan el mismo valor de su función hash. Usualmente, este ataque es más difícil de efectuar, ya que un hash de n bits puede ser vulnerado en 2^(n/2)+1 pasos de tiempo, pero es mucho más potente que un ataque clásico.

Dicho de forma matemática, dados dos prefijos distintos p₁ y p₂, el ataque genera dos sufijos s₁ and s₂ tal que hash(p₁ ∥ s₁) = hash(p₂ ∥ s₂) (∥ es la operación de concatenación).

También existen ataques más eficientes si se aplica el criptoanálisis a ciertas funciones hash específicas. En 2007 se encontró un ataque de colisión de prefijo elegido contra MD5, el cual requería aproximadamente 2⁵⁰ evaluaciones de la funcíón MD5. El artículo también muestra dos certificados X.509 de nombres de dominio distintos con el mismo valor de la función hash. Esto significa que sería posible solicitar a una autoridad de certificación que firme un certificado para un dominio, y luego utilizar dicho certificado (en específico su firma digital) para crear un certificado malicioso que falsifique el de otro dominio.^[5]​

En diciembre de 2008, se publicó un ataque de colisión en la vida real, en el cual un grupo de investigadores de ciberseguridad publicaron un certificado X.509 falso que podría ser utilizado para suplantar a una autoridad de certificación. El ataque aprovechó un ataque de colisión de prefijo contra la función hash MD5. Esto implicaba que un atacante podría suplantar a cualquier sitio web que utilizara SSL] (mediante un ataque de intermediario), logrando así evadir la validación de certificados implementada en todos los navegadores web, que busca proteger el comercio electrónico. El certificado falsificado puede no ser revocable por autoridades de certificado genuinas, y podría incluir una fecha de vencimiento falsificada. A pesar de que era sabido que MD5 era una función muy débil en 2004,^[1]​ las autoridades de certificados seguían dispuestas a emitir certificados con verificación de MD5 en diciembre de 2008.^[6]​ Al menos un certificado de Microsoft, el cual era utilizado para firmar código de computadora digitalmente, seguía utilizando MD5 en mayo de 2012.

El malware Flame usó, de manera exitosa, una modificación de un ataque de prefijo determinado, para suplantar el firmado del código de los componentes de este malware, de parte un certificado de raíz de Microsoft (el cual todavía utilizaba MD5).

En 2019, un grupo de investigadores encontró un ataque de prefijo determinado contra la función SHA-1, el cual tenía una complejidad computacional de entre 2^66.9 y 2^69.4 y costó menos de 100 000 dólares estadounidenses. ^[7]​^[8]​ En 2020, un grupo de investigadores logró reducir la complejidad computacional de un ataque de prefijo determinado contra SHA-1 a 2^63.4. ^[9]​

Posibles ataques

Muchas aplicaciones de funciones hash criptográficas no dependen de la resistencia a colisiones de dichas funciones, y por lo tanto no son afectadas por ataques de colisión. Por ejemplo, los HMACs no son vulnerables.^[10]​ Para que sirva el ataque, el atacante debe poder controlar el mensaje que es ingresado a la función.

Firmas digitales

Dado que los algoritmos de firma digital no pueden firmar mensajes muy grandes de forma eficiente, la mayor parte de las implementaciones utilizan funciones hash para reducir («comprimir») la cantidad de datos que tiene que ser firmada a un valor de longitud constante. Es frecuente que estos esquemas se tornen vulnerables a las colisiones tan pronto que exista una forma práctica de vulnerar la función hash; existen técnicas, como un hash con un valor aleatorio («salted»), que prolongan el tiempo requerido para efectuar un ataque, ya que en dicho caso se ocuparía un ataque de preimage.^[11]​

En 2008, un grupo de investigadores utilizó un ataque de colisión de prefijo determinado contra la función MD5, haciendo uso del caso ya descrito, para generar un certificado de autoridad de certificación que fuera falso. Crearon dos versiones de un certificado de clave pública de TLS, en donde una versión parecía ser legítima y fue enviada a la autoridad RapidSSL para su firmado. La segunda versión, la cual producía el mismo hash MD5, contenía configuraciones que indicaban a los navegadores web que lo aceptaran como autoridad legítima para emitir cualquier certificado deseado.^[12]​

Hash flooding

El Hash flooding (también conocido como HashDoS^[13]​) es un ataque de denegación de servicio que se aprovecha del peor caso posible (en cuanto a rapidez) de una búsqueda dentro de una tabla hash: un linear probe.^[14]​ El ataque fue descrito por primera vez en 2003. Para ejecutar dicho ataque, se debe enviar a un servidor varios fragmentos de datos cuyo valor hash sea idéntico, para luego intentar hacer que el servidor haga una búsqueda lenta. Ya que el principal enfoque de las funciones hash utilizadas en estas tablas era la rapidez (y no la seguridad), se vieron afectados la mayoría de los lenguajes de programación.^[15]​ Se han presentado nuevas vulnerabilidades de esta misma clase una década después de la presentación original.^[14]​

Para prevenir este ataque sin aumentar considerablemente la complejidad de la función, se han introducido funciones hash con llave, con el objetivo de que sea difícil encontrar colisiones sin conocer ésta. Este tipo de funciones pueden ser más lentas que otras publicadas anteriormente, sin embargo son considerablemente más fáciles de calcular que las funciones hash criptográficas. Hacia 2021, la función SipHash, diseñada por Jean-Philippe Aumasson y Daniel J. Bernstein en 2012, es la más usada de su clase.^[16]​

De forma análoga, es posible formular un ataque en el que se llenen filtros de Bloom mediante un ataque de preimage parcial.^[17]​

Véase también

• HMAC
• Firma electrónica

Referencias

1. Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu: Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD, Cryptology ePrint Archive Report 2004/199, 16 Aug 2004, revised 17 Aug 2004. Consultado el 27 de julio de 2008.
2. M.M.J. Stevens (junio de 2007). On Collisions for MD5. «[...] we are able to find collisions for MD5 in about 2^24.1 compressions for recommended IHVs which takes approx. 6 seconds on a 2.6GHz Pentium 4.» 
3. Magnus Daum; Stefan Lucks. «Hash Collisions (The Poisoned Message Attack)». Eurocrypt 2005 rump session (en inglés). Archivado desde el original el 27 de marzo de 2010. 
4. Max Gebhardt; Georg Illies; Werner Schindler (4 de enero de 2017). A Note on the Practical Value of Single Hash Collisions for Special File Formats (en inglés). 
5. Marc Stevens; Arjen Lenstra; Benne de Weger (30 de noviembre de 2007). «Chosen-Prefix Collisions for MD5 and Colliding X.509 Certificates for Different Identities». Advances in Cryptology - EUROCRYPT 2007. Lecture Notes in Computer Science 4515. p. 1. Bibcode:2007LNCS.4515....1S. ISBN 978-3-540-72539-8. doi:10.1007/978-3-540-72540-4_1. 
6. Alexander Sotirov (30 de diciembre de 2008). «Creating a rogue CA certificate». Archivado desde el original el 18 de abril de 2012. Consultado el 7 de octubre de 2009. 
7. Catalin Cimpanu (13 de mayo de 2019). «SHA-1 collision attacks are now actually practical and a looming danger». ZDNet (en inglés). 
8. Gaëtan Leurent; Thomas Peyrin (6 de mayo de 2019). «From Collisions to Chosen-Prefix Collisions Application to Full SHA-1». 
9. Gaëtan Leurent; Thomas Peyrin (5 de enero de 2020). «SHA-1 is a Shambles - First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust». 
10. «Hash Collision Q&A». Cryptography Research Inc. 15 de febrero de 2005. Archivado desde el original el 17 de julio de 2008. «Because of the way hash functions are used in the HMAC construction, the techniques used in these recent attacks do not apply». 
11. Shai Halevi and Hugo Krawczyk, Randomized Hashing and Digital Signatures (enlace roto disponible en este archivo).
12. Alexander Sotirov; Marc Stevens; Jacob Appelbaum; Arjen Lenstra; David Molnar; Dag Arne Osvik; Benne de Weger (30 de diciembre de 2008). MD5 considered harmful today. Chaos Communication Congress 2008. 
13. Falkenberg, Andreas; Mainka, Christian; Somorovsky, Juraj; Schwenk, Jörg (2013). «A New Approach towards DoS Penetration Testing on Web Services». 2013 IEEE 20th International Conference on Web Services. pp. 491-498. ISBN 978-0-7695-5025-1. S2CID 17805370. doi:10.1109/ICWS.2013.72. 
14. «About that hash flooding vulnerability in Node.js... · V8». v8.dev. 
15. Scott A. Crosby and Dan S. Wallach. 2003. Denial of service via algorithmic complexity attacks. In Proceedings of the 12th conference on USENIX Security Symposium - Volume 12 (SSYM'03), Vol. 12. USENIX Association, Berkeley, CA, USA, 3-3.
16. Jean-Philippe Aumasson; Daniel J. Bernstein (18 de septiembre de 2012). «SipHash: a fast short-input PRF». 
17. Gerbet, Thomas; Kumar, Amrit; Lauradoux, Cédric (12 de noviembre de 2014). The Power of Evil Choices in Bloom Filters (reporte) (en inglés). INRIA Grenoble. 

Enlaces externos

• "Meaningful Collisions", attack scenarios for exploiting cryptographic hash collisions
• Esta obra contiene una traducción parcial derivada de «Collision attack» de Wikipedia en inglés, concretamente de esta versión del 28 de febrero de 2024, publicada por sus editores bajo la Licencia de documentación libre de GNU y la Licencia Creative Commons Atribución-CompartirIgual 4.0 Internacional.