Multe aproape coliziuni, dar nicio coliziune completă

Adăugare importantă târziu: Acum îmi dau seama că codul încearcă să găsească coliziuni pentru un 64 de biți $\operatorname{hash}$ acceptând mesaje pe 64 de biți. Daca asta $\operatorname{hash}$ a fost o bijecție, nu s-ar ciocni. Există un continuum între o bijecție și o funcție aleatoare și nicio asigurare $\operatorname{hash}$ se comportă mai ales ca mai târziu. Dimpotrivă, este o funcție internă $f(x)=C\,x\oplus D\,x\bmod2^{64}$ nu are drept-difuzie. Acesta este, $x\equiv x'\pmod{2^i}\implies f(x)\equiv f(x')\pmod{2^i}$, prin urmare $f$ este o funcție de rundă hash slabă. Acest lucru ar putea explica cel puțin parțial dificultatea de a găsi coliziuni prin metode concepute pentru funcții aleatorii. În cele din urmă presupun unul dintre:

• spațiul de mesaje pentru $x$ este $b$-bit cu $b$ considerabil mai mare decât (ieșire pe 64 de biți)
• încercăm să găsim ciocniri $x,x'$ astfel încât $\operatorname{hash}(p\mathbin\|x)=\operatorname{hash}(p'\mathbin\|x')$ Unde $p$ și $p'$ sunt prefixe distincte fixe, $x,x'$ sunt $b=64$-pic, $x\ne x'$.

Bănuiesc că o altă problemă importantă este aceea în

Am populat (matricele) prin hashing valorile Int

este hashed incrementale Valori int. Este destul de fezabil să faci o funcție astfel încât valorile incrementale într-un interval mare să nu se ciocnească și este foarte posibil ca funcția $\operatorname{hash}$ căutat pentru coliziuni se comportă astfel, astfel încât orice încercare de a găsi coliziuni între valori consecutive eșuează.

Ca exemplu de funcție fără coliziuni pentru intrare într-un interval mic, luați în considerare $H(x)=\left(263x+\left(\operatorname{MD5}(x)\bmod256\right)\right)\bmod2^{64}$. Tine $H(x)-H(x')\equiv263(x-x')+(r-r')\pmod{2^{64}}$, cu $r,r'\in[0,255]$ deoarece acestea sunt obținute ca ultimul octet al unui MD5; prin urmare $\lvert r-r'\rvert<256$. Prin urmare, dacă $x\ne x'$, singura modalitate de a obține $H(x)=H(x')$ este asta $\lvert x-x'\rvert$ este mare, cel putin $\letaj 2^{64}/263\retaj$, ceea ce nu va fi cazul consecutiv $x$ într-un interval mic.

Când încercați să găsiți coliziuni pentru o astfel de funcție hash insuficient aleatorie $H$, o soluție ușoară este să găsiți coliziuni pentru o funcție mai aleatorie $x\mapsto H(G(x))$, construit folosind o bijecție auxiliară pseudo-aleatorie $G$, de exemplu. $G(x)=G_2(G_1(G_0(x)))$ cu $G_i(x)=k_i(x\oplus(x\gg\lceil b/3+1\rceil))\bmod2^b$ pentru $k_i$ ciudat întâmplător $b$-constante de biți [unde $\gg$ este schimbarea dreapta și $b$ este dimensiunea biților a $x$]. Odată o coliziune $x,x'$ se gaseste cu $H(G(x))=H(G(x'))$ dar $x\ne x'$, o coliziune pentru $H$ este $G(x),G(x')$.

Un avantaj al căutării coliziunilor cu rho lui Pollard cu puncte distincte (mai degrabă decât metoda din codul întrebării) este că natura sa iterativă rezolvă adesea problema unei funcții insuficient aleatorii căutate pentru coliziuni, fără un auxiliar. $G$; sau, un relativ simplu $G$ va face (aici cred că ar trebui să facă o rotație de 1 bit în feedback-ul lui Pollard rho, compensând lipsa difuziei corecte). De asemenea, rho-ul lui Pollard folosește mai puțină memorie, astfel funcționează pentru hashe-uri mai mari; iar pentru funcțiile de hash rapid, este mai rapid, deoarece este prietenos cu memoria cache.