Rezistența la coliziune

Rezistența coliziune este o proprietate de funcții hash criptografice : o funcție hash criptografice H este rezistent la coliziune , dacă este dificil de a găsi două intrări , care produc aceeași valoare hash ; adică două intrări A și B astfel încât :, și A ≠ B. ${\ displaystyle H (A) {=} H (B)}$

O funcție hash cu mai multe intrări decât ieșiri trebuie să genereze în mod necesar coliziuni. Luați în considerare o funcție hash, cum ar fi SHA-256, care produce ieșire pe 256 de biți dintr-o intrare de lungime arbitrară. Deoarece funcția trebuie să genereze una din cele 2.256 de ieșiri pentru fiecare membru al unui set mult mai mare de intrări, principiul sertarului asigură că unele intrări vor avea aceeași valoare hash. Rezistența la coliziune nu înseamnă că nu există coliziuni, ci doar că coliziile sunt greu de găsit.

Zilele de naștere paradox ilustrează limita superioară a rezistenței la coliziune: dacă o funcție hash produce N biți de ieșire, un atacator care testează 2 N / 2 (sau operații hash) asupra intrărilor aleatorii este probabil să se găsească două ieșiri identice.. Dacă există o metodă mai ușoară decât acest atac de forță brută pentru a găsi două ieșiri identice, funcția hash este considerată inadecvată pentru a servi ca funcție hash criptografică. ${\ displaystyle \ scriptstyle {\ sqrt {2 ^ {N}}}}$

Funcțiile hash criptografice sunt, în general, concepute pentru a fi rezistente la coliziuni. Cu toate acestea, multe funcții hash despre care se credea că sunt rezistente la accidente au fost rupte. De exemplu, tehnici mai eficiente decât forța brută sunt acum cunoscute pentru a găsi coliziuni pentru funcțiile de hash MD5 și SHA-1 . Pe de altă parte, există dovezi matematice că, pentru unele funcții hash, găsirea coliziunilor este cel puțin la fel de dificilă ca unele probleme matematice dificile, cum ar fi factorizarea sau logaritmul discret . Se spune că aceste funcții s-au dovedit a fi sigure.

utilizare

Rezistența la coliziune este de dorit în mai multe situații:

în unele sisteme de semnături digitale , o autoritate certifică autenticitatea unui document prin publicarea unei semnături cu cheie publică pe o valoare hash a documentului; dacă este posibil să se producă două documente cu aceeași valoare hash, un atacator ar putea obține o atestare de autenticitate pe un document de la o autoritate și apoi să susțină că autoritatea a atestat autenticitatea unui alt document;
în unele dovezi ale muncii , utilizatorii furnizează coliziuni hash ca dovadă că au efectuat o cantitate semnificativă de calcul; dacă există o modalitate mai ușoară de a găsi coliziuni decât forța brută , utilizatorii pot găsi coliziuni fără a efectua o cantitate semnificativă de calcule;
în unele sisteme de fișiere distribuite , părțile compară valorile hash ale fișierelor pentru a se asigura că au aceeași versiune a unui fișier; un atacator care ar putea produce două fișiere cu aceeași valoare hash ar putea păcăli utilizatorii să creadă că au aceeași versiune a unui fișier atunci când, de fapt, au fișiere diferite.

Note și referințe

(fr) Acest articol este preluat parțial sau în întregime din articolul Wikipedia din limba engleză intitulat „ Rezistență la coliziune ” ( vezi lista autorilor ) .

Goldwasser și Bellare 2008 , p. 136.
Goldwasser și Bellare 2008 , p. 143.
Pass, R. „Lectura 21: Funcții Hash rezistente la coliziune și Schema generală de semnătură digitală” . Curs de criptografie, Universitatea Cornell, 2009.
Xiaoyun Wang și Hongbo Yu, „ How to Break MD5 and Other Hash Functions ” (accesat la 21 decembrie 2009 )
Xiaoyun Wang, Yiquin Lisa Yin, Hongobo Yu, „ Găsirea coliziunilor în SHA-1 complet ” .
Galbraith 2012 .

Anexe

Bibliografie

(ro) Shafi Goldwasser și Mihir Bellare , „ Note de curs despre criptografie ” [PDF] ,iulie 2008(accesat la 6 februarie 2016 ) .
[Galbraith 2012] (ro) Steven Galbraith, Mathematics of Public Key Cryptography , Cambridge University Press,2012( citiți online [PDF] ) , „3.5 Funcții hash teoretice ale numerelor”