Không, việc phá vỡ thuộc tính va chạm của SHA-256 không yêu cầu bất kỳ $2^{128}$ khoảng trống. Chúng tôi biết làm thế nào để thể hiện sự va chạm trong bất kỳ $n$-bit băm $H$ với $\mathcal O(2^{n/2})$ đánh giá băm và $\mathcal O(n)$ khoảng trống.
Phương pháp phù hợp đơn giản nhất là Phát hiện chu kỳ của Floyd, sẽ thể hiện với xác suất không biến mất hai khác biệt $n$-bit chuỗi bit $r$ và $s$ với $H(r)=H(s)$, trên quỹ đạo một điểm ban đầu nhất định $t$ khi lặp lại $H$
- $m\gets\lceil\,2^{n/2+1}\,\rceil$ (tăng dần $+1$ giảm sự cố).
- $u\được H(t)$ .
- $r\được u$MỘT ; $s\được H(u)$ .
- trong khi $r\ne s$ :Â (tìm chu kỳ)
- nếu $m=0$ sau đó dừng lại trong thất bại (quỹ đạo dài, hiếm).
- $m\được m-1$ .
- $r\được H(r)$MỘT ; $s\được H(H(s))$ .
- nếu $t=s$ sau đó dừng lại trong thất bại ($t$ trong chu kỳ, biến mất rất hiếm).
- $s\được H(s)$ .
- trong khi $r\ne s$ :Â (bù $u$ theo một chu kỳ)
- trong khi $t\ne u$:Â (xác định vị trí va chạm)
- $r\được t$MỘT ; $s\được u$ .
- $t\được H(t)$MỘT ; $u\được H(u)$ .
- đầu ra $(r,s)$ và dừng lại trong thành công.
Hãy thử nó trực tuyến! đối với xung đột của hàm băm 24 bit (lần đầu tiên $k=3$ byte của SHA-256). Vui lòng chạy mã Python này trên máy của bạn nếu tăng $k$.
Phương pháp này sử dụng quỹ đạo của $t$, được định nghĩa là $u$ đạt được bằng cách lặp đi lặp lại $u\được H(u)$ bắt đầu từ $u=t$, có xu hướng quay vòng trong $\mathcal \Theta(2^{n/2})$ các bước. Thuật toán phát hiện một chu kỳ đã đạt, tìm $u$ sau bao nhiêu bước từ $t$ như độ dài của chu kỳ, sau đó chu kỳ được nhập vào đâu, dẫn đến va chạm. Có thể chỉ ra rằng đối với hàm ngẫu nhiên $H:\{0,1\}^*\mapsto\{0,1\}^n$ và ngoại trừ rất nhỏ $n$, xác suất thành công của thuật toán này từ bất kỳ điểm bắt đầu nào $t$ là ít nhất $3/4$ (thất bại là do quỹ đạo quá dài của $t$, Hoặc khi nào $t$ thuộc một chu kỳ).
Trong trường hợp không thành công, việc khởi động lại từ một điểm ngẫu nhiên khác là đủ.Điều đó thường hoạt động tốt đối với các hàm băm mật mã phổ biến $H$, nhưng ngay cả đối với những điều này, điều có thể xảy ra là hầu hết các điểm bắt đầu đều dẫn đến một chu trình quá lớn không thể tìm thấy. Trong trường hợp chung, chúng tôi muốn chuyển sang sử dụng thuật toán với $H'$ Được định nghĩa bởi $H'(x)=H(F(x))$ cho một lần tiêm ngẫu nhiên phù hợp có thể tính toán hiệu quả và có thể đảo ngược $F$ được chọn khi bắt đầu thuật toán. Điều đó thể hiện sự va chạm đối với $H'$ sử dụng thuật toán thể hiện một xung đột cho $H$, nhưng $H'$ có thể có cấu trúc chu trình khác. Cho hầu hết $n$-bit băm $H$ thích hợp cho việc sử dụng mật mã, $F$ có thể là XOR với một cố định $n$-bit chuỗi bit hoặc thêm tiền tố hoặc/và hậu tố cố định. Điều này không được minh họa trong mã giả ở trên và mã Python được liên kết.
Có thể phân phối công việc trên nhiều máy chạy song song, mỗi máy có ít bộ nhớ, giao tiếp vừa phải và công việc phụ vừa phải. Xem Paul C. van Oorschot và Michael J. Wiener, Tìm kiếm va chạm song song với các ứng dụng phân tích mật mã, Trong Tạp chí Mật mã học, 1999.
