Atac de col·lisió

En criptografia, un atac de col·lisió a un hash criptogràfic intenta trobar dues entrades que produeixen el mateix valor hash, és a dir, una col·lisió hash. Això contrasta amb un atac de preimatge on s'especifica un valor hash objectiu específic.

Hi ha aproximadament dos tipus d'atacs de col·lisió:

Atac de col·lisió clàssic

Trobeu dos missatges diferents m₁ i m₂ tals que hash (m₁) = hash (m₂).

Més generalment:

Atac de col·lisió de prefix escollit

Donats dos prefixos diferents p₁ i p₂, trobeu dos sufixos s₁ i s₂ tals que hash (p₁∥s₁) = hash (p₂∥s₂), on ∥ denota l'operació de concatenació.

Atac de col·lisió clàssic

De la mateixa manera que els xifrats de clau simètrica són vulnerables als atacs de força bruta, cada funció hash criptogràfica és inherentment vulnerable a les col·lisions mitjançant un atac d'aniversari. A causa del problema de l'aniversari, aquests atacs són molt més ràpids del que seria una força bruta. Un hash de n bits es pot trencar en 2^n/2 passos de temps (avaluacions de la funció hash).

Dit matemàticament, un atac de col·lisió troba dos missatges diferents m1 i m2, de manera que hash(m1) = hash(m2). En un atac de col·lisió clàssic, l'atacant no té control sobre el contingut de cap missatge, però són triats arbitràriament per l'algorisme.

Es poden fer atacs més eficients mitjançant l'ús de criptoanàlisi per a funcions hash específiques. Quan es descobreix un atac de col·lisió i es considera que és més ràpid que un atac d'aniversari, sovint es denuncia una funció hash com a "trencada". La competència de la funció hash NIST va ser induïda en gran manera per atacs de col·lisió publicats contra dues funcions hash molt utilitzades, MD5 i SHA-1. Els atacs de col·lisió contra MD5 han millorat tant que, a partir del 2007, només triguen uns segons en un ordinador normal. Les col·lisions hash creades d'aquesta manera solen ser de durada constant i en gran part desestructurades, per la qual cosa no es poden aplicar directament per atacar formats de documents o protocols generalitzats.

Tanmateix, les solucions alternatives són possibles abusant de les construccions dinàmiques presents en molts formats. D'aquesta manera, es crearien dos documents el més semblants possibles per tal de tenir el mateix valor hash. Un document es mostraria a una autoritat per ser signat, i després la signatura es podria copiar a l'altre fitxer. Aquest document maliciós contindria dos missatges diferents en el mateix document, però de manera condicional mostraria un o l'altre mitjançant canvis subtils al fitxer:

• Alguns formats de document com PostScript o macros de Microsoft Word tenen construccions condicionals. (si-aleshores-else) que permeten comprovar si una ubicació del fitxer té un valor o un altre per controlar el que es mostra.
• Els fitxers TIFF poden contenir imatges retallades, amb una part diferent d'una imatge que es mostra sense afectar el valor hash.
• Els fitxers PDF són vulnerables als atacs de col·lisió mitjançant l'ús del valor del color (de manera que el text d'un missatge es mostra amb un color blanc que es barreja amb el fons i el text de l'altre missatge es mostra amb un color fosc) que es pot modificar per canviar. contingut del document signat.

Atac de col·lisió de prefix escollit

Una extensió de l'atac de col·lisió és l'atac de col·lisió de prefix escollit, que és específic de les funcions hash de Merkle–Damgård. En aquest cas, l'atacant pot triar dos documents arbitràriament diferents i, a continuació, afegir diferents valors calculats que donen com a resultat que tots els documents tinguin un valor hash igual. Aquest atac és normalment més difícil, un hash de n bits es pot trencar en 2^(n/2)+1 passos de temps, però és molt més potent que un atac de col·lisió clàssic.

Dit matemàticament, donats dos prefixos diferents p₁, p₂, l'atac troba dos sufixos s₁ i s₂ de tal manera que hash (p₁∥s₁) = hash (p₂∥s₂) (on ∥ és l'operació de concatenació).

També són possibles atacs més eficients mitjançant l'ús de criptoanàlisi per a funcions hash específiques. El 2007, es va trobar un atac de col·lisió de prefix escollit contra MD5, que va requerir aproximadament ²⁵⁰ avaluacions de la funció MD5. El document també mostra dos certificats X.509 per a diferents noms de domini, amb valors hash en col·lisió. Això vol dir que es podria demanar a una autoritat de certificació que signi un certificat per a un domini i, a continuació, aquest certificat (especialment la seva signatura) es podria utilitzar per crear un nou certificat sense error per suplantar la identitat d'un altre domini.

El desembre de 2008 es va publicar un atac de col·lisió del món real quan un grup d'investigadors de seguretat va publicar un certificat de signatura X.509 falsificat que es podia utilitzar per suplantar la identitat d'una autoritat de certificació, aprofitant un atac de col·lisió de prefix contra la funció hash MD5. Això significava que un atacant podria suplantar qualsevol lloc web assegurat amb SSL com a home-in-the-middle, subvertint així la validació del certificat integrada a cada navegador web per protegir el comerç electrònic. És possible que les autoritats reals no puguin revocar el certificat fraudulent i també podria tenir un termini de caducitat falsificat arbitrari. Tot i que se sabia que l'MD5 era molt feble el 2004, les autoritats de certificació encara estaven disposades a signar certificats verificats per MD5 el desembre de 2008, i almenys un certificat de signatura de codi de Microsoft encara utilitzava MD5 el maig de 2012.

El programari maliciós Flame va utilitzar amb èxit una nova variació d'un atac de col·lisió de prefix escollit per falsificar la signatura de codi dels seus components mitjançant un certificat arrel de Microsoft que encara utilitzava l'algorisme MD5 compromès.

El 2019, els investigadors van trobar un atac de col·lisió de prefix escollit contra SHA-1 amb una complexitat informàtica entre 2^66,9 i 2^69,4 i un cost inferior a 100.000 dòlars EUA. El 2020, els investigadors van reduir la complexitat d'un atac de col·lisió de prefix escollit contra SHA-1 a 2^63,4.