Importanța coliziunii funcției hash

Să presupunem că a fost găsită o coliziune într-o anumită funcție hash, astfel încât H(x1) = H(x2)

Cu toate acestea, x1 și x2 sunt ambele o colecție aparent „aleatorie” de biți care nu transmit un mesaj coerent și nu pot fi interpretate într-un mod coerent.

Această coliziune face ca funcția hash H să nu fie sigură? dacă da, cum poate fi exploatat, chiar dacă coliziunea cunoscută nu transmite un mesaj coerent? Mulțumiri

Prefer să mă gândesc la criptografie ca la infrastructură. Ar trebui să ne străduim să dezvoltăm o infrastructură care să minimizeze numărul de avertismente de utilizare.Nu este sarcina criptografiei să definească mesajele „semnificative” din aplicația dumneavoastră. Poți să te uiți la o anumită coliziune $m_1, m_2$ si spune cu certitudine ca Nu aplicarea unei funcții hash va vreodată atribuie acestora un sens $m_1$ și $m_2$?

Ce funcție hash ai folosi mai degrabă, una cu garanția „e greu de găsit orice coliziuni" sau unul cu garanție "este greu să găsești o coliziune, cu excepția uneori printre șiruri care sunt JPG-uri de gerbili și fișiere gzip ale lui Shakespeare"? Nu aș dori să conduc o mașină cu un autocolant de avertizare pe care scrie „mașina poate exploda dacă conduci 88.1 mph cu semnalul de viraj stânga pornit și radioul reglat la 88.1 FM”, chiar dacă avertismentul a fost corect îngust și nu aș face niciodată acele 3 lucruri în același timp.

De aceea, definițiile de securitate criptografică consideră o coliziune orice două mesaje care satisfac $H(x_1) = H(x_2)$, un fals de semnătură pe orice mesajul este un atac, criptări ale orice textul simplu ar trebui să arate imposibil de distins etc. Dacă doriți ca criptografie să fie utilizată, asigurați-vă că depuneți eforturi pentru o garanție de securitate care să pună toata lumea în largul lor.

Un al doilea motiv practic pentru a fi îngrijorat de o coliziune „nestructurată” în $H$, este că atunci când se găsește unul, este adesea o chestiune de timp înainte ca tehnicile să fie extinse pentru a găsi coliziuni „structurate”. De exemplu, găsirea coliziunilor structurate într-o funcție aleatorie (folosind atacul clasic de coliziune Yuval) este aproximativ aceeași dificultate ca și găsirea coliziunilor nestructurate (folosind forța brută standard și limitarea zilei de naștere).

Chiar dacă coliziunea este complet nestructurată și a apărut din două evaluări complet independente, ar fi totuși o preocupare semnificativă pentru o funcție hash modernă. În construcțiile criptografice, presupunem în mod regulat că ieșirea unei funcții hash este distribuită uniform la întâmplare. Pentru funcții hash, cum ar fi SHA256 nu există nicio dovadă pentru acest lucru și nu știm, de exemplu, chiar dacă toate ieșirile sunt posibile.

Acum luați în considerare că, chiar și pentru SHA256 (probabil cea mai evaluată funcție hash din toate timpurile), tot aș estima că mai puțin de $2^{90}$ iesiri au fost calculate (și majoritatea acestor valori au fost aruncate). Pentru o funcție hash care produce ieșiri de 256 de biți uniform la întâmplare pentru a produce o coliziune în $2^{90}$ iesiri este despre o $2^{-77}$ eveniment. Ar trebui să concluzionam că fie SHA256 nu se comportă așa cum am sperat, fie că suntem incredibil de ghinionoși (și nimeni nu este atât de ghinionist).

Un astfel de eveniment, dacă s-a produs, ar trebui luat ca dovadă că SHA256 are mult mai puțin entropia de coliziune decât am presupus noi și că, cu o putere de calcul semnificativ mai mică decât am presupus noi, oamenii ar fi capabili să ciocnească valori de date interesante prin simpla adăugare de blocuri aleatorii. Într-un astfel de eveniment ipotetic, ar trebui să fie luat ca un semn că ceva este în neregulă cu funcția hash, dar că nu știm de ce.

H ar fi nesigur dacă, atunci când este dat x1, ar fi posibil să se obțină algoritmic un x2 diferit cu același hash. Deoarece spațiul hash este mult mai mic decât spațiul de date, vor exista întotdeauna potențiale coliziuni, întrebarea este dacă le putem găsi.