Tôi thấy kỹ thuật này được đề xuất ở nhiều nơi (bao gồm cả ngăn xếp), và tôi không thể thoát ra khỏi đầu của tôi rằng điều này sẽ làm giảm entropy! Sau khi tất cả, bạn đang băm một cái gì đó một lần nữa, mà đã được băm và có một cơ hội va chạm. Sẽ không va chạm cơ hội trên cơ hội va chạm kết quả trong cơ hội va chạm nhiều hơn? Sau khi nghiên cứu, có vẻ như tôi sai, nhưng tại sao?nhiều lần lặp trên băm: nó có làm giảm entropy không?
Vì bạn đã gắn thẻ md5, tôi sẽ sử dụng làm ví dụ. Từ wikipedia:
nếu hai tiền tố có cùng một băm có thể được tạo, một hậu tố chung có thể được thêm vào để làm cho va chạm có nhiều khả năng được chấp nhận là dữ liệu hợp lệ của ứng dụng sử dụng nó. Hơn nữa, các kỹ thuật tìm kiếm va chạm hiện tại cho phép chỉ định một tiền tố tùy ý: kẻ tấn công có thể tạo hai tệp va chạm mà cả hai bắt đầu bằng cùng một nội dung. Tất cả kẻ tấn công cần tạo ra hai tệp tin va chạm là một tệp mẫu với khối dữ liệu 128 byte, được căn chỉnh trên một ranh giới 64 byte có thể được thay đổi một cách tự do bằng thuật toán tìm va chạm. Ví dụ về một vụ va chạm MD5, với hai thông điệp khác nhau trong 6 bit, là:
Và sau đó các mẫu thô mà chúng cung cấp dài 256 byte. Vì cuộc tấn công va chạm dựa vào khối dữ liệu byte 128 byte và thông báo băm chỉ 128 bit, thực sự không có nguy cơ bị tấn công va chạm thành công vượt quá vòng lặp đầu tiên - nghĩa là bạn không thực sự ảnh hưởng đến khả năng xảy ra xung đột vượt quá băm đầu tiên.
Cũng xem xét rằng entropy của băm là 128 bit nói trên. Thậm chí xem xét rằng tổng số va chạm cơ hội chỉ là 2^20,96 (một lần nữa từ wikipedia), nó sẽ mất một số lượng lớn các lần lặp lại để gây ra hai đầu vào va chạm. Lý do đầu tiên khiến tôi nghĩ rằng bạn đang rơi vào nạn nhân là:
Điều này có thể được disproven bởi counterexample khá dễ dàng. Xem xét lại MD5:
MD5 bất kỳ hai đầu vào nào 128 lần liên tiếp và bạn sẽ thấy điều này không đúng. Bạn có thể sẽ không tìm thấy một băm lặp đi lặp lại duy nhất giữa chúng - sau khi tất cả, bạn đã chỉ tạo ra 256 trong số có thể 2^128 giá trị băm, để lại 2^120 khả năng. Xác suất va chạm giữa mỗi vòng là independent của tất cả các vòng khác.
Có hai cách tiếp cận để hiểu tại sao điều này lại như vậy. Đầu tiên là mỗi lần lặp lại chủ yếu cố gắng để đạt được mục tiêu di động.Tôi nghĩ bạn có thể xây dựng một bằng chứng dựa trên nghịch lý sinh nhật rằng có một số lần lặp lại băm nhỏ đáng ngạc nhiên khi bạn có thể thấy một hàm băm tiêu hóa từ một đầu vào khớp với thông báo băm của một đầu vào khác. Nhưng họ gần như chắc chắn đã xảy ra tại khác nhau các bước lặp lại. Và một khi điều đó xảy ra, chúng có thể không bao giờ có cùng một đầu ra trên cùng một lần lặp bởi vì thuật toán băm chính nó là xác định.
Cách tiếp cận khác là nhận ra rằng hàm băm thực sự thêm entropy trong khi nó chạy. Hãy xem xét rằng một chuỗi rỗng có một tiêu hóa 128 bit giống như bất kỳ đầu vào nào khác; mà không thể xảy ra mà không có entropy được thêm vào trong các bước thuật toán. Điều này thực sự là một phần nhất định của một hàm băm mật mã: dữ liệu phải bị hủy hoặc đầu vào khác có thể được phục hồi từ thông báo. Đối với các đầu vào dài hơn tiêu hóa, có, entropy bị mất trên toàn bộ; nó phải là để phù hợp với chiều dài tiêu hóa. Nhưng một số entropy cũng được thêm vào.
Tôi không có số chính xác cho các thuật toán băm khác, nhưng tôi nghĩ tất cả các điểm tôi đã khái quát hóa với hàm băm khác và hàm một chiều/ánh xạ.
Nó làm giảm entropy.
Trong một bài báo có tên Random Mapping Statistics bởi Flajolet và Odlyzko, một định lý (Định lý 2) cho thấy:
"Nếu một n -bit chức năng ngẫu nhiên được lặp k lần, số lượng dự kiến của các điểm ảnh là (1 - t_k) * 2^n (đối lớn n), nơi t_k đáp ứng mối quan hệ tái phát t_0 = 0 và t_ {k + 1} = e^{- 1 + t_k}. Từ đó, nó có thể được chỉ ra rằng số lượng dự kiến của các điểm ảnh là 2^{n-i + 1} khi một hàm ngẫu nhiên được lặp k = 2^i lần."
tài liệu tham khảo thêm như sau:...
Gligoroski, D. và Klima, V., 2010, September hậu quả thực tiễn của quang sai thiết kế băm hẹp ống từ chức năng ngẫu nhiên lý tưởng trong Hội nghị quốc tế về sáng kiến ICT (pp 81- 93) Springer Berlin Heidelberg
Bhaum ik, R., Dutta, A., Quách, J., Jean, J., Mouha, N. và Nikolić, I., 2015. More Rounds, Less Security?
Dinur, I. và Leurent, G., 2014, Tháng Tám. Cải thiện các cuộc tấn công chung chống lại các máy chủ dựa trên băm và HAIFA. Trong Hội nghị Mật mã Quốc tế (trang 149-168). Springer Berlin Heidelberg.
Từ tài liệu tham khảo cuối cùng, người ta sẽ tìm thấy hai ngữ cảnh sau: Two lemmas on entropy loss. Do đó, quan sát về sự mất entropy cũng giữ nếu k chức năng ngẫu nhiên độc lập được sử dụng, thay vì một hàm ngẫu nhiên được lặp lại k lần.
