Khi nghiên cứu vấn đề như vậy, các nhà mật mã học đồng hóa một hàm băm mật mã $H$ đến một chức năng ngẫu nhiên hoặc tiên tri ngẫu nhiên (hoặc ánh xạ ngẫu nhiên mặc dù đó là một chút ngày) lặp đi lặp lại. Xác suất được tính trên tập hợp tất cả các giá trị băm có thể. Đó là một phép tính gần đúng, nhưng nếu kết quả thực tế khác biệt rõ rệt, thì đó sẽ là một cách để phân biệt hàm băm với một hàm ngẫu nhiên, do đó phá vỡ hàm băm theo các định nghĩa hiện đại. Do đó, phép tính gần đúng đã nói là thỏa đáng và càng có thể có một hàm băm mật mã không bị phá vỡ càng tốt.
Sẽ có chu kỳ ngắn?
Rất có thể, và càng nhiều hơn khi chúng ta nới lỏng định nghĩa về ngắn hạn. Nhưng (ngoại trừ các giá trị băm rất nhỏ), không có khả năng đạt được một chu kỳ ngắn từ một điểm bắt đầu ngẫu nhiên $A$; và (đối với các hàm băm mật mã tiêu chuẩn có đầu ra đủ lớn để chúng có khả năng chống va chạm), chúng tôi không thể thể hiện bất kỳ chu kỳ nào, bất kể kích thước của nó.
Có giá trị của $A$ như vậy mà $H(A)=A$ (chu kỳ 1)
Nếu tập đích của hàm băm có kích thước $n$ (ở đâu $n=2^b$ cho một $b$-bit băm, ví dụ: $n=2^{256}$ đối với SHA-256), thì xác suất có một chu kỳ có kích thước 1 được tính toán dễ dàng như phần bù của xác suất không có chu kỳ nào trong số $n$ chỉ băm vào chính nó, đó là $p_1(n)=1-(1-1/n)^n$. Điều này bắt đầu từ $p_1(1)=1$, $p_1(2)=3/4=0,75$, $p_1(3)=19/27\approx0,7037$, và $p_1$ nhanh chóng hội tụ về $1-1/e\approx0,6321$.
Do đó, có >63,2% xác suất tồn tại một chu kỳ có kích thước 1 trong hàm băm mật mã nhất định như SHA-256, SHA-384 hoặc SHA-512. Và chúng tôi không thể nói tốt hơn cho bất kỳ giá trị băm nào trong số này.
Tôi không biết làm thế nào để làm điều tương tự cho các chu kỳ có kích thước 2, nhưng không nghi ngờ gì về điều đó là khả thi và xác suất là khá lớn đối với $n\ge2$.
Có thể tính toán giá trị dự kiến của nhiều đặc điểm của chu kỳ cho một hàm/hàm băm ngẫu nhiên được lặp lại. Đặc biệt, đối với diện tích lớn $n$, số bước dự kiến trước khi chạm vào giá trị trước đó bắt đầu từ một điểm ngẫu nhiên là $\approx\sqrt{\pi\,n/2}$, và độ dài dự kiến của chu kỳ đạt được là một nửa. Một tài liệu tham khảo cổ điển là Philippe Flajolet và Andrew M. Odlyzko, Thống kê ánh xạ ngẫu nhiên, Trong thủ tục tố tụng của Eurocrypt 1989, và Báo cáo Nghiên cứu RR-1114, INRIA, 1989.
Có cách nào để chứng minh rằng không có chu kỳ nào như vậy tồn tại đối với một hàm băm nhất định hoặc đặt giới hạn dưới cho chu kỳ ngắn nhất.
Không, đối với hàm băm mật mã không bị phá vỡ có kích thước đầu ra đủ lớn để nó có khả năng chống va chạm (nghĩa là $\sqrt n$ lớn đến mức không thể tính được số lượng băm này); giả sử, bất kỳ hàm băm không bị gián đoạn nào 256-bit trở lên. Đối với một phần của câu hỏi là có thể chứng minh rằng không có chu trình nào như vậy tồn tại hay không, chúng ta thậm chí cần phải tính toán $n$ băm (cho đến lần cuối cùng chúng tôi không thể chắc chắn không có chu kỳ kích thước 1), do đó, bất kỳ hàm băm 128 bit không bị phá vỡ nào hoặc rộng hơn sẽ làm được.
Vậy làm thế nào để (cấu trúc lặp đi lặp lại của Douglas Hofstadter) kết nối với mật mã?
Một kỹ thuật tương tự được sử dụng để tấn công một số hệ thống mật mã. Chúng tôi xây dựng một hàm, lặp lại nó cho đến khi tìm thấy một chu trình (do đó ngắn, nếu không thì chúng tôi không thể tìm thấy nó) và điểm vào trong chu trình tạo ra xung đột và xung đột giải quyết vấn đề vì hàm được xây dựng với điều đó rõ ràng mục đích. Đó là trái tim của Pollard's rho phương pháp để giải Bài toán logarit rời rạc, đây là cách tấn công lý thuyết tốt nhất mà chúng tôi có cho bài toán này trong một số nhóm được sử dụng trong mật mã.
Lưu ý rằng cả hàm ở trên và hàm do Douglas Hofstadter xây dựng đều không tạo thành hàm băm mật mã an toàn. Đó là bởi vì chúng không phải là chúng ta có thể tìm thấy một chu kỳ và giải quyết vấn đề trong tầm tay.
