Hãy xem xét ý nghĩa của tuyên bố "nghịch lý sinh nhật":
chắc chắn: Giả sử độ dài của một bản tóm tắt là N. Bên tấn công cần tạo bao nhiêu bản tin và bản tóm tắt có liên quan để tìm hai bản tin có bản tóm tắt bằng nhau (xảy ra xung đột) với xác suất tìm thấy hai bản tin này cao hơn 50%. ?
Câu trả lời là $ c*\sqrt{N} $. Điều này có nghĩa là kẻ tấn công nên thu thập ít nhất $ c*\sqrt{N} $ số lượng tin nhắn trong số N tin nhắn để tìm hai bản tóm tắt giống hệt nhau và tìm xung đột. Rõ ràng hơn, trong $ c*\sqrt{N} $ số lượng tin nhắn, nên có hai tin nhắn m và $ \acute{m} $ rằng H(m) = H($ \acute{m}$) trong đó khả năng tìm thấy hai thông báo này là khoảng 50% (là xác suất có thể chấp nhận được). Trong công thức này, $c$ là một hằng số và nó xấp xỉ bằng 1,2 và bị bỏ qua trong hầu hết các bài báo và phép tính. Hơn nữa, thống kê này chỉ đúng đối với các hàm băm lý thuyết được thiết kế chính xác và hoàn hảo. Trong trường hợp này, chúng tôi chỉ tìm thấy hai thông báo này bằng vũ lực chứ không phải bất kỳ cuộc tấn công nào khác, vì hàm băm hoàn hảo và được thiết kế dựa trên toán học lý thuyết thuần túy.
Nếu chúng ta muốn đưa ra một ví dụ đơn giản để làm rõ điều này, giả sử U = {0,1} 128 là độ dài của bản tóm tắt, sau đó số lượng thông báo mà kẻ tấn công nên chọn từ U, để tìm hai bản tóm tắt giống hệt nhau và tìm ra xung đột (sự cố này có xác suất gần 50%), phải là:
$$ 1,2 * \sqrt{2^{128}} \cong 1,2 * (2^{64} ) \cong 2^{64} $$
Đây là giới hạn trên của khả năng chống va chạm dựa trên nghịch lý xác suất toán học đã được chứng minh và nó chỉ đúng nếu hàm băm được thiết kế đúng về mặt lý thuyết và toán học. Nếu chúng ta muốn tìm va chạm với số lượng thấp hơn $2^{64}$ tin nhắn, dựa trên lý thuyết này, xác suất giảm xuống dưới 50%, nói cách khác, ít có khả năng tìm thấy hai tin nhắn có bản tóm tắt giống hệt nhau.
Bây giờ nếu tôi muốn trả lời câu hỏi liên quan đến " phương pháp dễ dàng hơn tấn công vũ phu ", điều này sẽ xảy ra nếu chúng ta có thể tìm thấy một lỗ hổng trong thiết kế của hàm băm mà kẻ tấn công khai thác để tìm hai thông báo mà chúng có bản tóm tắt giống hệt nhau ở số thấp hơn $ c*\sqrt{N} $ tin nhắn. Như tôi đã đề cập ở trên, dựa trên nghịch lý ngày sinh nhật, ít nhất chúng ta nên kiểm tra $ c*\sqrt{N} $ số lượng tin nhắn tìm va chạm ( trong số lần kiểm tra này, xác suất tìm va chạm xấp xỉ bằng 50%). Tuy nhiên, nếu có một lỗ hổng trong thiết kế của hàm băm, kẻ tấn công sẽ khai thác lỗ hổng đó và không bao giờ sử dụng vũ lực để tìm ra xung đột. Hơn nữa, ở đây "phương pháp dễ dàng hơn" là một kiểu tấn công có thể được áp dụng cho các hàm băm hơn là tấn công vũ phu.
Các nhà mật mã, thiết kế các kế hoạch của họ dựa trên bảo mật tính toán hơn là bảo mật hoàn hảo; nghĩa là, họ chứng minh tính bảo mật của sơ đồ của họ dựa trên sức mạnh tính toán. Mặt khác, các sơ đồ được thiết kế mà không có nền tảng toán học vững chắc, không thể chống lại các cuộc tấn công lý thuyết thông thường thì hoàn toàn không được chấp nhận. Ngày nay, các hàm băm an toàn, có khả năng chống lại các cuộc tấn công máy tính phổ biến cũng như được chứng minh về mặt toán học là mạnh mẽ. Về mặt lý thuyết, có thể thiết kế một hàm băm an toàn, nhưng trên thực tế, có nhiều yếu tố như việc triển khai ảnh hưởng đến sơ đồ được thiết kế.
