Hârtia spartă de la Google (prima coliziune pentru SHA-1 complet) înseamnă crearea unui fișier nou cu același hash ca fișierul original?

Am o sursă de date A și un hash H(A) al acestui A. Este posibil, prin documentele sparte de la Google, să creez o nouă date B care scoate acest H(A)?

++ Am înțeles că conținutul lucrării este să completeze două blocuri de mesaje, astfel încât CV-ul final să fie același. Metoda la care m-am gândit este dacă M2(2) din „Fișier inactiv” poate fi găsit corect, astfel încât CV2 din „Fișier original” și „Fișier inactiv” să fie scos la fel ca în Metoda 1 din fotografie sau să facă doar CV2 la fel ca în Metoda 2 prin găsirea noului M1(2), M2(2).

Un bloc de mesaje de 64 de octeți este date fără sens. Prin urmare, fișierul nu trebuie să se deschidă normal.

Formatul fișierului nu se limitează la PDF.

Nu. Ceea ce ai descris ar fi a al doilea atac pre-imagine, în timp ce echipa Google a produs un atac de coliziune. În Shattered „Prima coliziune completă pe SHA1” de Mark Stevens și colab. acolo unde acele state sunt citate în metoda dvs. 1, autorii au putut mai întâi să selecteze simultan $M_1^{(1)}$ și $M_1^{(2)}$ făcând uşoare perturbări la una sau la alta până la o pereche apropiată de valori $CV_1^{(1)}$ și $CV_1^{(2)}$ au fost produse. În scenariul tău $M_1^{(1)}$ ar fi fix și numai $M_1^{(2)}$ ar putea fi ajustat, făcând mult mai greu de găsit aproape $CV_1$ valorile. De asemenea, în al doilea pas, cercetătorii au putut să le perturbe pe ambele $M_2^{(1)}$ și $M_2^{(2)}$ pentru a găsi coliziunea completă, dar în scenariul dvs. un atacator ar putea doar să se adapteze $M_2^{(2)}$.

Diferența de dificultate a acestor provocări este de așa natură încât găsirea unei a doua imagini prealabile pentru SHA1 este probabil să dureze aproximativ $2^{160}$ evaluări ale funcției hash. Este asemănător cu diferența dintre probabilitatea de a găsi două persoane în cameră cu aceeași zi de naștere si probabilitatea de a găsi pe cineva într-o cameră cu aceeași zi de naștere ca tine.

Lucrări mai recente („SHA1 este un dezastru” de Leurent și Peyrin) arată că este posibil ca un atacator să ia un fișier arbitrar și să adauge date pe care le controlează atât în ​​fișierul dvs., cât și în al lor, astfel încât să producă aceeași valoare SHA1 pentru ambele fișiere. Aceasta este cunoscută ca a prefix-coliziune ales și este încă o dovadă mai puternică că SHA1 trebuie să fie depreciat.

NB: Tabelul dvs. de valori ale octeților etichetează atât stânga cât și dreapta ca $M_1^{(2)}$ și am revenit la notarea hârtiei SHAttered. Nu sunt sigur de sursa celui de-al doilea tabel al tău.

Atacul Shattered găsește un fișier/mesaj B diferit care are același hash SHA-1 ca un fișier/mesaj A, dar numai dacă o secțiune a datelor din A are o caracteristică care nu se va întâmpla întâmplător. Pentru majoritatea formatelor de fișiere/semantice de date, aceasta permite încă atacul adversarilor care nu pot modifica semnificația/aspectul/efectul lui A, dar pot influența ușor conținutul binar al lui A.

Am o sursă de date A și un hash H(A) al acestui A. Este posibil, prin documentele sparte de la Google, să creez o nouă date B care scoate acest H(A)?

Răspunsul depinde de datele A, care în sine depind de modul în care a fost obținut sau produs A, pe care întrebarea nu le precizează sau nu permite să le ghicească.

1. da, fără efort de calcul, dacă A începe cu una dintre cele două valori particulare de 320 de octeți pe care le-a dat atacul Shattered. Putem înlocui doar unul cu celălalt pentru a forma B cu același hash SHA-1. Acest lucru poate fi folosit (printre altele) pentru a crea fără efort două fișiere PDF valide diferite, cu conținut de octeți ușor diferit și aspect vizual complet diferit.
2. Nu, dacă A este mai mic de aproximativ 125 de octeți, atunci când rămâneți la metoda din lucrarea Shattered, chiar și cu efortul lor de calcul. Dar trebuie să coborâm această limită la aproximativ 19 octeți dacă schimbăm metoda și acceptăm o creștere a efortului de calcul cu un factor modest (aproximativ 250 de mii) la aproximativ $2^{81}$ Hash-uri SHA-1.
3. da, cu efortul de calcul al lui Shattered, dacă un adversar poate alege primii 128 de octeți ai lui A. Acesta este încă atacul Shattered, dar necesită o muncă considerabilă. Putem reduce această limită la 64 de octeți dacă acceptăm creșterea efortului de calcul din punctul anterior.
4. da, ca prelungire a lui 3, dacă adversarul îl cunoaște pe primul $n$ octeți de A și poate alege următorul $128+(-n\bmod 64)$ octeți. Și trebuie să coborâm asta la $64+(-n\bmod 64)$ octeți cu efortul de calcul crescut. Acest lucru poate fi extins și mai mult la adversarul care alege aproximativ 20 de octeți de informații în primul $64\,f$ octeți de A cu cunoașterea acelei secțiuni a lui A și o creștere suplimentară a muncii cu un factor nu mai mare de $f$.
5. da, ca o consecință a lui 4, dacă A este pregătit într-un mod sub controlul unui adversar, de ex. dacă A este un document PDF, imagine PNG, imagine „ISO” CD/DVD, poate un fișier executabil pregătit folosind instrumente create de un adversar. Pentru certificate digitale, vezi această întrebare.
6. Nu, dacă A trece testul oferit de autorii Shattered și rămânem la metoda lor de atac. Dar testul lor nu poate proteja împotriva altor atacuri cu costuri comparabile și niciun test nu poate proteja împotriva atacurilor cu costuri modeste crescute.
7. Nu, dacă există cel puțin 64 de biți de entropie în primii 64 de octeți ai lui A care sunt necunoscute unui adversar într-un moment în care adversarul îl poate influența pe A, pentru orice efort de calcul fezabil. Acestea includ certificate aleatorii A și digitale emise de autoritățile de certificare care iau simpla precauție de a utiliza numere de serie aleatorii la începutul certificatului.

Vreau să mă asigur că formatul fișierului nu este limitat la PDF.

Atacul și extensia Shattered nu se limitează la PDF, vezi 3/4/5. Poate fi transportat (cu ceva lucru) cu orice format de fișier fără vreo verificare internă a redundanței; adică majoritatea. Mai mult, analogii de prefixe la 1 (care este specializat pentru falsificarea ieftină a PDF-ului) pot fi concepute pentru multe formate, inclusiv JPEG, PNG, GIF, MP4, JPEG2000, formatul Portable Excutable și multe altele, cu o muncă considerabilă, dar fezabilă, care trebuie făcută numai o singura data. Prefixele lui 1 funcționează chiar și cu unele formate de fișiere existente, de ex. audio și video pentru jucătorii care sărit peste ceea ce nu recunosc (din moment ce întrebarea nu cere că diferiții A și B se comportă diferit; asta ar fi greu de realizat cu prefixele de 1 pentru ceva care nu este PDF și un player standard nu concepute în acest scop).

Dacă aveți îndoieli: mai bine să vă protejați decât să vă pare rău, presupuneți că da, atacul este posibil și utilizați un hash neîntrerupt și semnificativ mai larg decât SHA-1

(principiul) lucrării este de a completa două blocuri de mesaje

Nu chiar. Este completat câteva bucăți înăuntru Două consecutiv blocuri de mesaje (64 octeți fiecare), care conținut este ales (cu o muncă considerabilă, dar fezabilă) în funcție de starea hash înainte de procesarea acestor două blocuri de mesaje. Prin urmare, conținutul acestor două blocuri de mesaje din A nu este arbitrar, trebuie să se potrivească cu acești 128 de octeți calculați cu durere. O astfel de potrivire nu se va întâmpla accidental (de exemplu, pentru A aleatoriu), necesită un anumit control asupra lui A și cunoașterea stării hash-ului înainte de hashing aceste două blocuri. O astfel de cunoaștere poate fi obținută prin cunoașterea părții mesajului A dinaintea acestor două blocuri de A trebuie să aleagă pentru ca atacul să funcționeze.

Un atac care funcționează pentru A arbitrar ar fi un (al doilea) atac preimagine. Un astfel de atac nu este cunoscut pentru SHA-1.