Cât de ușor este să falsificați un fișier hashing cu trei funcții, CRC32, MD5 și SHA-1?

Fișierul-A este hashing cu CRC32, MD5 și SHA-1.

Cât de ușor este să creezi un fișier-B fals care are aceleași hashe-uri ca fișierul-A? CRC32, MD5 și SHA-1?

Poate un computer mediu cu un GPU să calculeze o triplă coliziune hash a fișierului-A? Și cât timp ar dura?

Cât de ușor este să creezi un fișier-b fals care are aceleași hashe-uri ca fișierul-a? crc32, md5 și sha1?

Aceasta este cunoscută în cercurile criptografice ca problema „a doua preimagine”.

Cu CRC32, este ușor; luați doar mesajul original și adăugați (adică xor) câteva copii deplasate ale polinomului CRC și asta nu va schimba hash-ul. Dacă nu aveți fișierul original-a (aveți doar hash), atunci construirea fișierului-b ar implica rezolvarea a 32 de ecuații booleene simultane - doar puțin mai dificilă.

Cu MD5 și SHA-1, nu există nicio modalitate practică cunoscută. În ambele cazuri, cea mai bună abordare pe care o avem este să încercăm un număr mare de fișiere-b arbitrare până când ne împiedicăm de unul cu hash-ul așteptat - aceasta este o cantitate de muncă imposibilă în ambele cazuri.

Acum, ceea ce se știe cu MD5 și SHA-1 este cum să construiți două fișiere diferite cu același hash. Cu toate acestea, aceste metode necesită posibilitatea de a specifica ambele fișiere și nu se aplică dacă unul dintre fișiere este deja dat.

Poate computerul mediu cu un GPU să calculeze coliziunea hash triplă a fișierului-a?

Nu există nicio modalitate cunoscută de a face acest lucru (în timp practic, de exemplu, înainte ca soarele să se transforme într-un Gigant Roșu...)

După cum scrie Poncho, nu știm cum să găsim practic o a doua preimagine pentru SHA1 sau MD5, cu atât mai puțin una care să se potrivească cu ambele.

Cu toate acestea, știm cum să găsim coliziuni. Datorită naturii construcției MD, putem converti cu ușurință coliziunile în coliziuni multiple. Ceea ce înseamnă că putem crea multe mesaje care se vor ciocni atât de multe încât să putem construi multe coliziuni de SHA-1 (hash-ul mai larg) și să obținem restul printr-un atac de naștere. asa cum este descris aici: Cât de greu este să generezi o coliziune simultană MD5 și SHA1?

Așa că o a doua preimagine a acestor 3 pare să ne depășească cu mult. Dar o coliziune dintre SHA-1 și MD5 va costa $2^{67}$ operațiuni. Putem face acest lucru din nou de 16 ori pentru a construi o coliziune multiplă asupra ambelor. și găsiți o coliziune și pentru CRC32 (sau orice hash de 32 de biți chiar și unul puternic). Acest lucru va face costul total $2^{71}$ pentru a construi două mesaje care se ciocnesc în toate cele 3 hashe-uri. Dar aceasta va fi atunci când atacatorul alege ambele mesaje, nu atunci când este furnizat unul. Acest lucru depășește cu mult ceea ce poate face un singur computer puternic, dar nu dincolo de mijloacele unui stat național sau al unui megacorp.