Atacul de coliziune

Un atac de coliziune în criptografie  este căutarea a două blocuri de intrare diferite ale unei funcții hash criptografice care produc aceeași valoare hash, adică o coliziune hash . Spre deosebire de atacul preimagine , valoarea hash nu este aleasă în mod deliberat.

Aproximativ[ clarifica ] Există două tipuri diferite de atacuri de coliziune:

Atacul clasic de coliziune

Atacul de coliziune găsește două mesaje diferite m1 și m2 astfel încât . În cazul clasic al unui atac, atacatorul nu are control asupra conținutului mesajelor, dar acestea sunt alese aleatoriu de algoritm. Multe criptosisteme simetrice sunt vulnerabile la atacuri de forță brută , orice funcție hash criptografică este, prin definiție, vulnerabilă la un atac de naștere . Datorită paradoxului zilei de naștere, această din urmă metodă de atac poate fi mult mai rapidă decât metoda forței brute. Un hash de N biți poate fi rupt de 2n /2 ori (prin calculul unei funcții hash). Cele mai eficiente atacuri sunt posibile atunci când se utilizează criptoanaliza pe o anumită funcție hash. Atunci când un atac de coliziune este mai rapid decât un atac de „zi de naștere”, funcțiile hash sunt adesea denunțate ca fiind „rupte”. Crearea funcției hash SHA-3 (concurs) a fost în mare măsură determinată de necesitatea înlocuirii vechilor funcții MD5 [1] și SHA-1 . Atacurile de coliziune împotriva algoritmului MD5 s-au îmbunătățit atât de mult încât pe un computer normal durează doar câteva secunde. [2] Coliziunile hash generate în acest mod sunt, în general, de lungime constantă și în mare măsură nestructurate, deci nu pot fi aplicate direct pentru a ataca formate de documente sau protocoale comune. Cu toate acestea, sunt posibile soluții prin abuzarea constructelor dinamice prezente în multe formate. Astfel, se vor crea două documente identice între ele astfel încât să aibă aceeași valoare hash. Dacă un document este semnat de o persoană de încredere, semnătura acestuia poate fi copiată într-un alt fișier. Un astfel de document rău intenționat va conține două mesaje diferite în același document, dar va putea afișa oricare dintre ele prin mici modificări ale fișierului:

Atacul de coliziune cu un prefix dat

Rezultatul îmbunătățirii atacului de coliziune a fost atacul de coliziune cu un prefix dat, proiectat pentru structura Merkle-Damgard . În acest caz, un atacator poate alege 2 documente diferite aleatoriu și apoi le poate completa cu 2 valori calculate diferite, astfel încât cele 2 documente să ajungă cu aceeași valoare hash. Acest atac este mai grav decât versiunea sa clasică.

Matematic vorbind, există 2 prefixe diferite p1, p2 , cele 2 complemente ale acestora m1 și m2 sunt calculate astfel încât hash(p1 ∥ m1) = hash(p2 ∥ m2) (unde ∥ este operația de concatenare ).

În 2007, a fost creat un atac de coliziune hash MD5 cu prefix, necesitând aproximativ 250 de calcule ale funcției MD5 . Nota a prezentat două certificate X.509 pentru nume de domenii diferite care au aceeași funcție hash. Aceasta înseamnă că certificatul unui domeniu de încredere poate fi folosit de un alt domeniu necunoscut. [5]

Un adevărat atac de coliziune a fost publicat în decembrie 2008, când un grup de cercetători în securitate a publicat un certificat de semnare X.509 fals care poate fi folosit pentru a autoriza anonim un certificat prin utilizarea unui atac de coliziune cu un prefix hash MD5 dat. Acest lucru însemna că un atacator ar putea falsifica orice site web securizat prin TLS ca intermediar , încălcând astfel validarea certificatului încorporat în fiecare browser web pentru a securiza comerțul electronic . Un certificat fals nu poate fi revocat de către părți de încredere, poate avea, de asemenea, o perioadă arbitrară de timp pentru a expira. În ciuda punctelor slabe ale MD5 găsite în 2004, [1] în decembrie 2008 a devenit clar că mulți oameni încă mai folosesc certificate cu această funcție hash, [6] și cel puțin Microsoft încă îl folosea în mai 2012.

În Flame , malware-ul a folosit cu succes o nouă variantă a atacului de coliziune prefixat pentru a falsifica componentele de semnare a codului folosind certificate rădăcină Microsoft, care încă foloseau algoritmul MD5 compromis. [7] [8]

Schema de atac

Multe aplicații cu funcții hash criptografice nu necesită protecție împotriva coliziunilor atacurile de coliziune nu pot ocoli protecția lor De exemplu, HMAC -urile nu sunt supuse acestui tip de atac. [9] Pentru un atac de succes, atacatorul trebuie să aibă control asupra intrării.

Semnături electronice

Deoarece algoritmii de semnătură electronică nu pot semna eficient cantități mari de date, multe suplimente folosesc funcții de comprimare a datelor pentru a le semna într-o dimensiune fixă. Schemele de semnătură electronică sunt adesea predispuse la coliziuni, în ciuda faptului că folosesc o tehnică de hashing aleatoriu. [zece]

De obicei, atacul decurge astfel:

  1. Eve creează 2 documente diferite A și B cu aceleași valori hash. Eve încearcă să-l înșele pe Bob trecând documentul ei drept al lui Alice.
  2. Eve îi trimite documentul A lui Alice , care are încredere în conținutul documentului, îi semnează hash și îi trimite semnătura lui Eve.
  3. Eve atașează semnătura documentului A la documentul B.
  4. Eve îi trimite apoi semnătura și documentul B lui Bob , pretinzând că Alice a semnat documentul. Deoarece semnătura electronică verifică doar valoarea hash a documentului B, Bob nu știe despre înlocuire.

În 2008, cercetătorii au atacat prefixul MD5 folosind scriptul de mai sus pentru a crea un certificat fals. Au creat 2 versiuni ale certificatului de cheie publică TLS , dintre care una a fost autentificată pentru autorizarea RapidSSL. O altă versiune, care are aceeași valoare hash MD5, conținea steaguri care semnalau browserului încrederea și dreptul de a acorda încredere altor certificate [11] .

Note

  1. ↑ 1 2 Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu: Collisions for Hash Functions MD4, MD5, HAVAL-128 și RIPEMD Arhivat 23 august 2011. , Cryptology ePrint Archive Report 2004/199, 16 august 2004, revizuit la 17 august 2004. Consultat la 27 iulie 2008.
  2. ↑ MJ Stevens. Despre coliziuni pentru MD5  (neopr.) . - 2007. - Iunie.
  3. ↑ Magnus Daum, Stefan Lucks. Coliziuni Hash (Atacul cu mesaje otrăvite) . Eurocrypt 2005 sesiune rump . Arhivat din original pe 27 martie 2010.
  4. ↑ 1 2 3 Max Gebhardt, Georg Illies, Werner Schindler. O notă despre valoarea practică a coliziunilor unice hash pentru formate speciale de fișiere  (engleză)  : jurnal.
  5. ↑ Marc Stevens, Arjen Lenstra, Benne de Weger. Chosen-prefix Collisions for MD5 and Colliding X.509 Certificate for Different Identities  (engleză)  : jurnal. - 2007. - 30 noiembrie.
  6. ↑ Alexandru Sotirov. Crearea unui certificat CA necinstite (link indisponibil) (30 decembrie 2008). Data accesului: 15 decembrie 2015. Arhivat din original la 18 aprilie 2012. 
  7. ↑ Microsoft lansează Avizul de securitate 2718704 . Microsoft (3 iunie 2012). Consultat la 4 iunie 2012. Arhivat din original pe 7 iunie 2012.
  8. ↑ Marc Stevens. CWI Cryptanalist descoperă o nouă variantă de atac criptografic în programul malware Flame Spy . Centrum Wiskunde & Informatica (7 iunie 2012). Consultat la 9 iunie 2012. Arhivat din original pe 28 februarie 2017.
  9. ↑ Întrebări și răspunsuri Hash Collision . Cryptography Research Inc (15 februarie 2005). „Din cauza modului în care funcțiile hash sunt utilizate în construcția HMAC, tehnicile utilizate în aceste atacuri recente nu se aplică.” Arhivat din original pe 17 iulie 2008.
  10. ↑ Shai Halevi și Hugo Krawczyk, Randomized Hashing and Digital Signatures Arhivat 20 iunie 2009 la Wayback Machine
  11. ↑ Alexander Sotirov, Marc Stevens, Jacob Appelbaum, Arjen Lenstra, David Molnar, Dag Arne Osvik, Benne de Weger (30 decembrie 2008). MD5 este considerat dăunător astăzi . Chaos Communication Congress 2008. Arhivat din original pe 2017-03-25 . Accesat 2015-12-15 . Parametrul depreciat folosit |deadlink=( ajutor )

Link -uri