Să luăm în considerare ce înseamnă afirmația „paradoxul zilei de naștere”:
Def: Să presupunem că lungimea unui rezumat este N. Câte mesaje și rezumate relevante ar trebui produse din partea atacatorului, pentru a găsi două mesaje care au rezumate egale (se produce coliziune), cu probabilitatea de a găsi aceste două mesaje mai mare de 50% ?
Raspunsul este $ c*\sqrt{N} $. Aceasta înseamnă că atacatorul ar trebui să colecteze cel puțin $ c*\sqrt{N} $ numărul de mesaje dintre N mesaje pentru a găsi două rezumate identice și a găsi o coliziune. Mai clar, în $ c*\sqrt{N} $ numărul de mesaje, ar trebui să existe două mesaje m și $ \acute{m} $ că H(m) = H($ \acute{m}$) unde probabilitatea de a găsi aceste două mesaje este de aproximativ 50% (care este o probabilitate acceptabilă). În această formulă, $c$ este o constantă și este aproximativ egală cu 1,2 și ignorată în majoritatea lucrărilor și calculelor. În plus, această statistică este corectă doar pentru funcțiile hash teoretice care sunt proiectate corect și sunt impecabile. În acest caz, găsim aceste două mesaje doar prin forță brută și nu prin alte atacuri, deoarece funcția hash este impecabilă și proiectată pe baza matematicii teoretice pure.
Dacă vrem să dăm un exemplu simplu pentru a clarifica acest lucru, să presupunem U = {0,1} 128 este lungimea rezumatului, apoi numărul de mesaje pe care atacatorul ar trebui să le aleagă din U, pentru a găsi două rezumate identice și a găsi o coliziune (acest incident are o probabilitate de aproape 50%), ar trebui să fie:
$$ 1,2 * \sqrt{2^{128}} \cong 1,2 * (2^{64} ) \cong 2^{64} $$
Aceasta este o limită superioară a rezistenței la coliziune bazată pe un paradox al probabilității matematice dovedit și este corectă doar dacă funcția hash proiectată este corectă teoretic și matematic. Dacă vrem să găsim coliziuni în număr de mai mic decât $2^{64}$ mesaje, pe baza acestei teorii, probabilitatea se reduce la mai puțin de 50%, cu alte cuvinte, este mai puțin probabil să găsiți două mesaje cu rezumate identice.
Acum, dacă vreau să răspund la întrebarea despre „metoda mai ușoară decât atacul cu forță brută”, acest lucru s-ar întâmpla dacă am putea găsi o defecțiune în designul funcției hash pe care atacatorul o exploatează pentru a găsi două mesaje care au rezumate identice. în numărul mai mic de $ c*\sqrt{N} $ mesaje. După cum am menționat mai sus, pe baza paradoxului zilei de naștere, ar trebui cel puțin să testăm $ c*\sqrt{N} $ numărul de mesaje pentru a găsi o coliziune (în acest număr de teste, probabilitatea de a găsi o coliziune este aproximativ egală cu 50%). Cu toate acestea, dacă există un defect în designul funcției hash, atacatorul exploatează acel defect și nu folosește niciodată forța brută pentru a găsi o coliziune. Mai mult, aici „metoda mai ușoară” este un tip de atac care poate fi aplicat funcțiilor hash, mai degrabă decât atacului cu forță brută.
Criptografii își proiectează schemele mai degrabă bazate pe securitatea computațională decât pe securitatea perfectă; adică demonstrează securitatea schemei lor pe baza puterilor de calcul. Pe de altă parte, schemele concepute fără un fundal matematic robust care nu ar putea rezista atacurilor teoretice comune nu sunt deloc acceptabile. În zilele noastre, funcțiile hash securizate sunt rezistente din punct de vedere computațional împotriva atacurilor computaționale obișnuite și s-au dovedit matematic a fi robuste. Într-un mod teoretic, este posibil să se proiecteze o funcție hash sigură, dar în practică, există mulți factori, cum ar fi implementarea, care influențează schema proiectată.
