Raspunsul nu este usor, insa, un bun punct de plecare este Lucrarea lui Florent Chabaud și Antoine Joux despre SHA-0 și SHA-1
Introducere simplă
În MD4, SHA-0, SHA-1 și SHA-2 există o funcție de compresie. $$C:\{0,1\}^\ell \to :\{0,1\}^n$$ Unde $n$ este dimensiunea de ieșire și $\ell$ este lungimea blocului de procesat.
Funcția de compresie $C$ poate fi privit ca un cifru bloc în care cheia este mesajul, acest lucru este semnificativ deoarece singura parte este intrarea.Și, SHACAL este numit cifrul bloc al SHA-1 și, în mod similar, SHACAL-2 pentru SHA-2.
Acum, avem un cifru bloc și avem intrarea (valorile inițiale $H_i$s și valoarea de ieșire (hash - digest). Trebuie să găsim cheia. Dacă putem găsi cheia, avem atacuri și coliziuni pre-imagine. Acest lucru ar putea conduce să considerăm că atacăm ca în atacurile diferențiale, nu tocmai, ci într-un mod similar.
Autorii au început mai întâi cu SHA-1 slăbit (SHI1) în care expansiunea de intrare nu este luată în considerare și ADD este convertit în X-sau astfel încât să nu existe o parte neliniară. Cu perturbații pe un singur bit și corecții la intrări, ei au arătat că găsesc coliziuni cu o mască.
Mai târziu, singurul ADD convertit la X-sau (SHI2) pentru a extinde atacul. Ei găsesc o masca diferentiala $\mathcal{M}$ care poate fi aplicat textului simplu (input) pentru a găsi coliziuni.
lookRandomCollision(h, bloc):
m = ramdom_message(1-bloc).
h = Hash(m)
m' = masca (m)
h' = Hash(m')
Dacă h=h':
întoarcere (m)
altceva:
întoarce -1
în timp ce (1):
aspect de succesRandomCollision(SHA-1, 512)
dacă seccess != -1:
print("Perechea de coliziune este - ", m, mask(m))
Succesul atacului este probabilitatea de succes a măștii $\mathcal{M}$ a introduce coliziuni. Dacă probabilitatea de succes a măștii este $1/t$ apoi în jur $c\cdot t$ perechi aleatoare se vor găsi ciocnirea.
După acestea, se uită la SHA-0 și SHA-1 real pentru a găsi o astfel de mască. Găsesc unul pentru SHA-0 cu $2^{61}$-timp de complexitate. Masca pe care au găsit-o pentru SHA-1 nu are o complexitate bună decât coliziunea generică, adică are complexitate $> 2^{80}$.
Articolul este bine scris din înțelegerea atacului de la funcția de compresie de nivel scăzut (fără parte neliniară) la funcția de nivel superior care include neliniaritatea.
Și, cu mare probabilitate, NSA era conștientă de acest lucru, așa că au modificat extinderea intrării lui SHA-0 pe SHA-1 cu o introducere a rotației.
De ce este periculos
Luați în considerare cazul în care SHA-1 este rupt, avem un(e) bloc(e) de prefix $P$ și blocuri de sufix $S$ și căutăm o coliziune
$$Hash(P\mathbin\| m \mathbin\|S) = Hash(P\mathbin\| m' \mathbin\|S)$$
Dacă putem găsi o mască diferențială bună $\mathcal{M}$ cu probabilitate bună atunci putem executa atacul asupra blocului $m$. Dacă o parte a fișierului face parte din redundanță ca în fișierele PDF, atunci se pot crea două PDF-uri diferite care au aceleași valori hash. Un pericol real, desigur, necesită mai mult decât atât. Schimbarea în $m'$ are un avantaj pentru semnatar. Acest lucru poate fi, de asemenea, realizabil.
