De ce nu este sigură o funcție hash prea rapidă?

Înțeleg de ce avem nevoie ca funcțiile hash să fie suficient de rapide pentru procesare, dar suficient de lente pentru securitate. Dar nu înțeleg de ce o funcție hash foarte rapidă poate provoca o coliziune. Bănuiala mea este că o funcție hash foarte rapidă produce un număr mic de biți ca ieșire, astfel încât aceasta înseamnă o probabilitate mai mare de coliziune. M-ar putea corecta cineva?

Răspunsul acceptat în prezent este bun, dar aș dori să adaug ceva. „securitate” este un termen larg în acest context și ar trebui să vă întrebați de ce amenințare doriți să vă apărați. În majoritatea discuțiilor, „coliziunea” se referă la găsirea unei intrări diferite cu o ieșire identică.Dar pentru cazul parolei, „hash rapid” este problematic doar pentru forțarea brută. Cu un hash rapid, este ușor pentru un atacator să atace dicționarul multe intrări posibile, căutând o potrivire cu hash-ul.

Nu este un caz de „hash rapid == prea puțini biți de ieșire”, așa cum a cerut OP. Doar că, dacă hash-ul este prea rapid, este ușor să găsești și intrarea originală (nu o coliziune), ceea ce o face nesigură.

Având în vedere o funcție hash care este reglabilă pentru „viteză”, (iterații, poate), creșterea vitezei cu care se hash nu crea mai multe ciocniri. Problema de securitate cu un hash care este prea rapid este că, având în vedere o perioadă de timp X, un hash care este mai rapid va genera o cantitate mai mare de ieșiri, astfel încât un atacator are șanse mai mari de găsirea o coliziune.

OP a primit ideea de la a postare pe YouTube care argumentează în jurul MD5.

Iată argumentul simplu dacă se uită cineva la videoclip.

Viteza nu înseamnă că o funcție hash este nesigură, designul o face sigură.

De-a lungul anilor, cercetătorul a găsit slăbiciuni în designul MD5 și s-au îmbunătățit în timp. Odată ce MD5 a fost lansat, în 1992, au început atacurile, iar în 2010 Xie și Dengguo Feng au anunțat prima coliziune MD5 cu un singur bloc (512 biți) publicată. Desigur, îmbunătățirea procesorului și a ciclurilor acestora ajută la atacul mai rapid, cu toate acestea, principala contribuție o reprezintă metodologiile de atac. Luați în considerare că atacul de coliziune generic (atacul de ziua de naștere) necesită $2^{64}$ Hash-uri MD5 cu o probabilitate de succes de 1/2. Chiar și astăzi, niciun procesor obișnuit nu poate face $2^{64}$ în un timp rezonabil. Pe de altă parte, avem acum o coliziune instantanee pentru MD5, vezi corkami.

Pe de altă parte, Blake2 este un funcție hash foarte rapidă, mai rapid decât MD5 și SHA-1 și nu are atacul de extensie de lungime deoarece folosește Structura HAIFA, remedieri ale designului MD. Este mai rapid decât MD5 și sigur cel puțin într-o trăsătură previzibilă. Dimensiunea sa de ieșire este suficient de sigură pentru atacuri paralele masive sau chiar pentru Algoritmul de căutare cuantică al lui Grover. Seria Blake are acum BLAKE3, este un hash paralel și foarte rapid.

Ceea ce este important în legătură cu viteza și relația ei cu securitatea este dimensiunea rezumatului. Atacurile generice pentru atacul pre-imagine, atacul secundar pre-imagine și coliziunea generică sunt $2^n$,$2^n$, și $2^{n/2}$, respectiv. Dacă aveți ieșirea pe 256 sau 512 biți, sunteți bine în privința atacurilor generice. Ține minte că spațiul scurt de intrare este o problemă pentru atacurile pre-imagine și se recomandă HMAC.

PS: hashing parole (nu este necesară rezistența la coliziune), unde vrem viteză controlabilă, duritatea memoriei, și cantitatea de fir al funcției de hash a parolei. Ar trebui să citiți întrebarea canonică de pe venerabilul nostru site, securitatea informatiei.. De asemenea, Hartie Argon2, câștigătorul concursului de hashing a parolelor din 2015, este o alegere bună de citit.

Notă finală: Ar trebui să definiți cu atenție problema lor, astfel încât să poată realiza un design sigur. Nu există securitate reală dacă nu îți cunoști riscurile.

Să luăm în considerare utilizarea unui hash pentru a proteja o parolă și să luăm câteva exemple.

• Primul caz: avem o funcție hash care ia 1 secunda pentru a executa pe un computer obișnuit. Dacă atacatorul are acces la 1 milion de computere (de exemplu, printr-o rețea bot), poate face 1 milion de încercări pe secundă, 86 de miliarde de încercări pe zi. Dar o parolă de 8 caractere care utilizează cifrele superioare, inferioare și simboluri este de aproximativ 50 de biți de entropie, așa că la performanța actuală va dura în medie aproximativ 18 ani pentru a sparge acea parolă, chiar și cu acea rețea botnet masivă (desigur, în 18 ani lucrurile se vor accelera probabil destul de mult, așa că va fi mai scurt decât atât, dar totuși). În cel mai rău caz, va dura 36 de ani.

• Al doilea caz: avem o funcție hash care ia 1 microsecundă a executa. Același atacator care folosește același botnet de un milion de computere poate face acum un milion de încercări pe secundă. Acum durează 1125 de secunde (mai puțin de 20 de minute) pentru a încerca fiecare dintre cele aproximativ 2^50 de parole posibile de 8 caractere. Deci, în medie, aproximativ jumătate din timp.

Dacă crezi că o rețea bot cu un milion de computere este o fantezie, mai gandeste-te.

Deci nu este o chestiune de a genera mai multe coliziuni (pentru orice funcție hash decentă, aceasta este direct legată de dimensiunea ieșirii, nu de viteza hash-ului), ci de a putea găsi coliziuni (sau de fapt, originalul intrare, dar nu știți neapărat asta), înfrângând scopul hashului.