Thành phần của các hàm chống va chạm H' = h1(h2()) có chống va chạm không?

Giả sử có hai hàm băm chống va chạm $h_1$ và $h_2$ với kích thước đầu ra của $n_1$ và $n_2$ tương ứng.

Là $H'(x) = h_1(h_2(x))$ chống va chạm cho các mối quan hệ khác nhau giữa $n_1$ và $n_2$?

Điều này đã khiến tôi và các đồng nghiệp của tôi bối rối trong vài ngày qua vì hai cách tiếp cận khác nhau mâu thuẫn với nhau:

Cách tiếp cận thứ nhất:

Dựa trên định nghĩa về khả năng chống va chạm $H'$ có một đầu ra của $n_1$ chiều dài và vì vậy nếu chúng ta có thể tìm thấy một cuộc tấn công ít phức tạp hơn $\mathcal O(2^{n_1/2})$ nó không chống va chạm.

Chúng tôi muốn $$\mathcal O(2^{n_2/2}) < \mathcal O(2^{n_1/2}) \implies \ldots \implies n_2 < n_1$$

Vì thế nếu $n_2 < n_1, H'$ không có khả năng chống va chạm và trong các trường hợp khác, nó là

cách tiếp cận thứ 2:

Giả sử $H'$ không có khả năng chống va chạm.

Sau đó, có tồn tại khác nhau $x_1$ và $x_2$ để có thể $H'(x_1) = H'(x_2)$ I E. $h_1(h_2(x_1)) = h_1(h_2(x_2))$

Điều đó có thể xảy ra nếu $h_2(x_1) = h_2(x_2)$, nhưng $h_2$ có khả năng chống va chạm

Nó cũng có thể xảy ra nếu $h_1(A) = h_1(B)$ ở đâu $A = h_2(x_1)$ và $B = h_2(x_2)$ nhưng $h_1$ có khả năng chống va chạm.

Chúng tôi đã chứng minh rằng $H'$ có khả năng chống va chạm và mối quan hệ của $n_1$ và $n_2$ không thành vấn đề.

Điều này đã khiến tôi và các đồng nghiệp của tôi bối rối trong vài ngày qua vì hai cách tiếp cận khác nhau mâu thuẫn với nhau

Lý do là hai cách tiếp cận này giả định các định nghĩa khác nhau về 'chống va chạm'; hai định nghĩa này không tương đương nhau; nghĩa là, chúng ta có thể tìm thấy các hàm thỏa mãn một định nghĩa chứ không phải định nghĩa kia.

Lần thử đầu tiên sử dụng định nghĩa 'không có va chạm tìm thấy tệp đính kèm mất ít thời gian hơn $\mathcal{O}(2^{n/2})$ hoạt động; bởi vì $n$ đã được khắc phục, chúng tôi sử dụng điều này làm tốc ký cho 'một cuộc tấn công diễn ra $c2^{n/2}$ hoạt động, đối với một số $c$ không xa lắm so với 1 và một số định nghĩa hợp lý về hoạt động (trong trường hợp này là đánh giá hàm băm).

Vấn đề với định nghĩa này là nó dẫn đến một số kết luận ngớ ngẩn, ví dụ, SHA-256 bị cắt bớt thành 8 bit là 'chống va chạm' theo định nghĩa này. Theo hướng khác, đầu ra 1kbyte từ SHAKE-256 không phải là 'chống va chạm', bởi vì bạn có thể tìm thấy các xung đột với ít hơn nhiều so với $2^{8192/2}$ đánh giá băm.

Ngược lại, cách tiếp cận 2 sử dụng định nghĩa 'hàm băm có khả năng chống va chạm nếu chúng ta không thể tìm thấy xung đột'. Thể hiện điều này một cách chính thức hơi phức tạp (bởi vì, miễn là đầu vào được phép dài hơn đầu ra, thì phải có xung đột, chúng tôi chỉ không biết chúng là gì) và cũng bởi vì điều này liên quan đến tài nguyên tính toán chúng tôi có (hiện tại, SHA-256 được cắt bớt thành 200 bit có khả năng chống va chạm; có thể không phải 20 năm nữa kể từ bây giờ khi chúng tôi có thêm sức mạnh tính toán); mặt khác, nó gần với khái niệm trực quan về 'khả năng chống va chạm' mà chúng ta có.

Với định nghĩa này, cách tiếp cận 2 có thể được viết lại thành 'nếu chúng ta giả sử $H'$ không chống va chạm, thì chúng ta biết $x \ne y$ với $H'(x) = H'(y)$. Sau đó, một trong hai $h_2(x) = h_2(y)$ (và do đó $h_2$ không chống va chạm, như chúng ta biết là va chạm), hoặc $h_2(x) \ne h_2(y)$, trong trường hợp đó chúng ta có $h_1(u) = h_1(v)$ vì $u = h_2(x), v = h_2(y), u \ne v$ (và do đó $h_1$ không chống va chạm, như chúng ta biết là va chạm).