Este compoziția funcțiilor rezistente la coliziune H' = h1(h2()) rezistentă la coliziune?

Să presupunem că există două funcții hash rezistente la coliziuni $h_1$ și $h_2$ cu dimensiuni de ieșire de $n_1$ și $n_2$ respectiv.

Este $H'(x) = h_1(h_2(x))$ rezistent la coliziune pentru diferitele relații dintre $n_1$ și $n_2$?

Acest lucru m-a uluit pe mine și pe colegii mei în ultimele zile, deoarece două abordări diferite se contrazic:

Prima abordare:

Pe baza definiției rezistenței la coliziune $H'$ are o ieșire de $n_1$ lungime şi deci dacă putem găsi un atac cu mai puţină complexitate decât $\mathcal O(2^{n_1/2})$ nu este rezistent la ciocniri.

Noi vrem $$\mathcal O(2^{n_2/2}) < \mathcal O(2^{n_1/2}) \implies \ldots \implies n_2 < n_1$$

Astfel, dacă $n_2 < n_1, H'$ nu este rezistent la coliziune și în alte cazuri este

A doua abordare:

Să presupunem $H'$ nu este rezistent la coliziune.

Apoi există diferite $x_1$ și $x_2$ astfel încât $H'(x_1) = H'(x_2)$ adică $h_1(h_2(x_1)) = h_1(h_2(x_2))$

Asta se poate întâmpla dacă $h_2(x_1) = h_2(x_2)$, dar $h_2$ este rezistent la coliziune

Se poate întâmpla și dacă $h_1(A) = h_1(B)$ Unde $A = h_2(x_1)$ și $B = h_2(x_2)$ dar $h_1$ este rezistent la coliziune.

Noi am dovedit asta $H'$ este rezistent la ciocniri și relația de $n_1$ și $n_2$ nu contează.

Acest lucru m-a uluit pe mine și pe colegii mei în ultimele zile, deoarece două abordări diferite se contrazic

Motivul este că aceste două abordări presupun definiții diferite pentru „rezistent la coliziune”; aceste două definiții nu sunt echivalente; adică putem găsi funcții care îndeplinesc o definiție și nu cealaltă.

Prima încercare folosește definiția „nu există un atașament de găsire a coliziunii care să ia mai puțin $\mathcal{O}(2^{n/2})$ operațiuni; deoarece $n$ este fixată, folosim aceasta ca prescurtare pentru „un atac luat $c2^{n/2}$ operațiuni, pentru unii $c$ nu drastic departe de 1 și o definiție rezonabilă a operațiunii (în acest caz, evaluarea funcției hash).

Problema cu această definiție este că duce la niște concluzii absurde, de exemplu, SHA-256 trunchiat la 8 biți este „rezistent la coliziune” prin această definiție. În cealaltă direcție, ieșirea de 1 kbyte de la SHAKE-256 nu este „rezistentă la coliziuni”, deoarece puteți găsi coliziuni cu mult mai puține decât $2^{8192/2}$ evaluări hash.

În schimb, abordarea 2 folosește definiția „o funcție hash este rezistentă la coliziune dacă nu putem găsi o coliziune”. Exprimarea formală a acestui lucru este puțin dificilă (pentru că, atâta timp cât intrarea este permisă să fie mai lungă decât ieșirea, trebuie să existe coliziuni, pur și simplu nu știm care sunt acestea) și, de asemenea, pentru că acest lucru este relativ la resursele de calcul avem (în acest moment, SHA-256 trunchiat la 200 de biți este rezistent la coliziuni; s-ar putea să nu mai fie peste 20 de ani, deoarece câștigăm mai multă putere de calcul); pe de altă parte, este mai aproape de noțiunea intuitivă de „rezistent la coliziune” pe care o avem.

Cu această definiție, abordarea 2 ar putea fi reformulată ca „dacă presupunem $H'$ nu este rezistent la coliziuni, atunci știm $x \ne y$ cu $H'(x) = H'(y)$. Atunci fie $h_2(x) = h_2(y)$ (și, prin urmare $h_2$ nu este rezistent la coliziune, așa cum cunoaștem o coliziune), sau $h_2(x) \ne h_2(y)$, caz în care avem $h_1(u) = h_1(v)$ pentru $u = h_2(x), v = h_2(y), u \ne v$ (și, prin urmare $h_1$ nu este rezistent la coliziune, așa cum cunoaștem o coliziune).