Textul citat pare să vorbească despre găsirea unei coliziuni a unei funcții hash de 128 de biți cu atacul Birthday. Într-un atac de naștere, cineva creează în jur $\sqrt{2^{128}} = 2^{64}$ mesaje astfel încât se așteaptă să găsească o pereche de ciocnire cu 1/2 probabilitate.
În atacul descris, Oscar vrea să creeze două mesaje specifice care au aceeași valoare hash.
$x_1$= Transferați $10 în contul Oscar
$x_2$= Transferați 10.000 USD în contul lui Oscar
Pentru a crea $2^{64}$ mesaje, se pot folosi caractere invizibile precum spaţiu
și fila
. Dacă adăugați 64 de caractere la $x_1$ sau $x_2$ acestea sunt fie tab sau spațiu, atunci puteți obține 64 de locații. Asta face $2^{64}$ mesaje care au aceeași semnificație cu hashuri mari, probabil diferite.
Această modificare invizibilă se aplică pe ambele $x_1$ și $x_2$.
Creat $2^{64}$ corzi diferite pentru $x_1$ și $x_2$ și combinați-le într-un set. În acest set, ne așteptăm la o coliziune. Rețineți că, în acest fel, este posibil să avem o coliziune în cadrul variantei de $x_1$ (sau $x_2$).
Acum, Oscar caută o modalitate de a te înșela. Oscar îți trimite mesajul $x_1$ cu paradigma hash și semn și o verifici. Ulterior, Oscar susține că te-au trimis $x_2$. Îți arată că semnăturile sunt aceleași cu cele precedente și aici avem conflictul de rezolvat.
Pentru alte exemple de utilizare a coliziunii hash în atacuri realiste, consultați această întrebare;
Atacul de coliziune vs al doilea atac pre-imagine
În atac de coliziune căutăm două mesaje $m_1$ și $m_2$ cu $m_1 \neq m_2$ astfel de $h(m_1) = h(m_2)$. Într-un atac de coliziune, atacatorul nu are posibilitatea de a alege valoarea hash, ei caută doar două mesaje care au aceeași valoare hash. Această libertate reduce costul atacului. Costul generic al coliziunii este $\mathcal{O}(\sqrt{2^{n/2}})$-timpul pentru $n$-bit funcție hash de ieșire.
În unele alte scenarii, atacatorul are nevoie al doilea atac pre-imagine; dat un mesaj $m$ și este valoarea hash $x=h(m)$, găsiți alt mesaj $m' \neq m$ astfel încât $h(m)=h(m')$. Acesta este scenariul în care atacatorul creează o falsificare a unei semnături digitale (hash și semn). Având în vedere semnătura, ei încearcă să găsească un alt mesaj $m'$ astfel încât semnătura să fie aceeași cu cea dată.
Două costuri generice ale atacului secundar pre-imagine este $\mathcal{O}(\sqrt{2^n})$-timpul pentru $n$-biți funcție hash.
Definițiile formale pot fi găsite în