Nu, ruperea proprietății de coliziune a lui SHA-256 nu necesită aproape $2^{128}$ spaţiu. Știm cum să arătăm coliziunea în orice $n$-bit hash $H$ cu $\mathcal O(2^{n/2})$ evaluări hash și $\mathcal O(n)$ spaţiu.
Cea mai simplă metodă potrivită este Descoperirea ciclului lui Floyd, care va prezenta cu probabilitate nedisparatoare două distincte $n$-bit șiruri de biți $r$ și $s$ cu $H(r)=H(s)$, pe orbită un punct inițial dat $t$ la iterare $H$
- $m\gets\lceil\,2^{n/2+1}\,\rceil$ (crescând $+1$ reduce eșecurile).
- $u\obține H(t)$ .
- $r\obține u$A ; $s\obține H(u)$ .
- in timp ce $r\ne s$ :Â (găsește ciclu)
- dacă $m=0$ apoi opriți în eșec (orbita lungă, rar).
- $m\obține m-1$ .
- $r\obține H(r)$A ; $s\ obține H(H(s))$ .
- dacă $t=s$ apoi opriți-vă în eșec ($t$ în ciclu, dispărut de rar).
- $s\obține H(s)$ .
- in timp ce $r\ne s$ :Â (offset $u$ cu un ciclu)
- in timp ce $t\ne u$:Â (găsește coliziune)
- $r\ obține t$A ; $s\obține u$ .
- $t\obține H(t)$A ; $u\obține H(u)$ .
- ieșire $(r,s)$ și opriți-vă în succes.
Încearcă online! pentru coliziunea unui hash pe 24 de biți (primul $k=3$ octeți ai lui SHA-256). Vă rugăm să fiți destul de amabil să rulați acest cod Python pe computer dacă crește $k$.
Metoda folosește că orbita de $t$, definit ca fiind $u$ atins prin iterare $u\obține H(u)$ începând de la $u=t$, tinde să circule în interior $\mathcal \Theta(2^{n/2})$ trepte. Algoritmul detectează un ciclu atins, găsiți $u$ dupa tot atatia pasi de la $t$ ca lungimea ciclului, apoi unde este introdus ciclul, ceea ce produce o coliziune. Se poate arăta că pentru funcția aleatoare $H:\{0,1\}^*\mapsto\{0,1\}^n$ și cu excepția celor foarte mici $n$, probabilitatea de succes a acestui algoritm din orice punct de plecare $t$ este cel puțin $3/4$ (Eșecurile sunt pentru o orbită prea lungă de $t$, sau când $t$ aparține unui ciclu).
În caz de eșec, este adesea suficient să reporniți din alt punct aleatoriu.De obicei, funcționează bine pentru hashurile criptografice comune $H$, dar chiar și pentru acestea se poate întâmpla ca majoritatea punctelor de plecare să ducă la un ciclu prea mare pentru a fi găsit. Într-un caz general, dorim să trecem la utilizarea algoritmului cu $H'$ definit de $H'(x)=H(F(x))$ pentru o injecție randomizată, calculabilă eficient și inversabilă $F$ ales la începutul algoritmului. Asta e atât de afișat o coliziune pentru $H'$ folosind algoritmul prezintă o coliziune pentru $H$, dar $H'$ poate avea o structură de ciclu diferită. Pentru cele mai multe $n$-bit hash $H$ potrivit pentru utilizare criptografică, $F$ poate fi XOR cu un fix $n$-bit șir de biți sau adăugarea unui prefix fix sau/și sufix. Acest lucru nu este ilustrat în pseudocodul de mai sus și codul Python legat.
Este posibil să distribuiți munca pe multe mașini care rulează în paralel, fiecare cu puțină memorie, comunicare moderată și muncă suplimentară moderată. Vezi Paul C. van Oorschot și Michael J. Wiener, Căutare de coliziuni paralele cu aplicații criptoanalitice, în Journal of Criptology, 1999.
