Nhiều va chạm gần nhưng không va chạm hoàn toàn

Bổ sung quan trọng muộn: Bây giờ tôi nhận ra mã cố gắng tìm xung đột cho 64-bit $\operatorname{hash}$ chấp nhận tin nhắn 64-bit. Nếu đó $\operatorname{hash}$ là một bijection, nó sẽ không va chạm. Có một sự liên tục giữa một phép loại bỏ và một hàm ngẫu nhiên, và không có bảo hiểm nào $\operatorname{hash}$ hành xử chủ yếu giống như sau này. Ngược lại, đó là chức năng bên trong $f(x)=C\,x\oplus D\,x\bmod2^{64}$ không có khuếch tán phải. Đó là, $x\equiv x'\pmod{2^i}\ngụ ý f(x)\equiv f(x')\pmod{2^i}$, do đó $f$ là một hàm băm vòng kém. Điều này có thể giải thích ít nhất một phần khó khăn trong việc tìm ra xung đột bằng các phương pháp được thiết kế cho các hàm ngẫu nhiên. Sau này tôi giả sử một trong số:

• không gian tin nhắn cho $x$ Là $b$-bit với $b$ lớn hơn đáng kể so với (đầu ra 64-bit)
• chúng tôi cố gắng tìm va chạm $x,x'$ như vậy mà $\operatorname{hash}(p\mathbin\|x)=\operatorname{hash}(p'\mathbin\|x')$ ở đâu $p$ và $p'$ là các tiền tố riêng biệt cố định, $x,x'$ là $b=64$-chút, $x\ne x'$.

Tôi nghi ngờ một vấn đề quan trọng khác là trong

Tôi điền (các mảng) bằng cách băm các giá trị Int

nó được băm gia tăng Giá trị int. Hoàn toàn khả thi để tạo một hàm sao cho các giá trị gia tăng trong một khoảng thời gian lớn không xung đột và hoàn toàn có thể là hàm $\operatorname{hash}$ tìm kiếm xung đột hoạt động như vậy, do đó mọi nỗ lực tìm xung đột giữa các giá trị liên tiếp đều thất bại.

Như một ví dụ về hàm không có xung đột cho đầu vào trong một khoảng thời gian nhỏ, hãy xem xét $H(x)=\left(263x+\left(\operatorname{MD5}(x)\bmod256\right)\right)\bmod2^{64}$. Nó giữ $H(x)-H(x')\equiv263(x-x')+(r-r')\pmod{2^{64}}$, với $r,r'\in[0,255]$ vì chúng được lấy dưới dạng byte cuối cùng của MD5; do đó $\lvert r-r'\rvert<256$. Do đó nếu $x\ne x'$, cách duy nhất để có được $H(x)=H(x')$ đó là $\lvert x-x'\rvert$ lớn, ít nhất $\ltầng 2^{64}/263\rtầng$, đó sẽ không phải là trường hợp liên tiếp $x$ trong một khoảng nhỏ.

Khi cố gắng tìm xung đột cho hàm băm ngẫu nhiên không đầy đủ như vậy $H$, một cách khắc phục dễ dàng là tìm xung đột cho hàm ngẫu nhiên hơn $x\mapsto H(G(x))$, được xây dựng bằng cách sử dụng một số phép chiếu phụ trợ giả ngẫu nhiên $G$, ví dụ. $G(x)=G_2(G_1(G_0(x)))$ với $G_i(x)=k_i(x\oplus(x\gg\lceil b/3+1\rceil))\bmod2^b$ vì $k_i$ ngẫu nhiên $b$hằng số -bit [trong đó $\gg$ là dịch chuyển phải, và $b$ là kích thước bit của $x$]. Một lần va chạm $x,x'$ được tìm thấy với $H(G(x))=H(G(x'))$ nhưng $x\ne x'$, va chạm cho $H$ Là $G(x),G(x')$.

Một lợi thế của việc tìm kiếm các va chạm với Pollard's rho với các điểm phân biệt (chứ không phải phương pháp trong mã của câu hỏi) là bản chất lặp đi lặp lại của nó thường giải quyết vấn đề về một hàm không đủ ngẫu nhiên được tìm kiếm cho các va chạm mà không cần một phụ trợ. $G$; hoặc, tương đối đơn giản $G$ sẽ làm (ở đây tôi nghĩ rằng một vòng quay 1 bit trong phản hồi của rho của Pollard nên làm, bù cho việc thiếu khuếch tán bên phải). Ngoài ra, Pollard's rho sử dụng ít bộ nhớ hơn, do đó hoạt động với các giá trị băm lớn hơn; và đối với các hàm băm nhanh, nó nhanh hơn vì nó thân thiện với bộ đệm.