Có md5 có bảo đảm duy nhất cho các chuỗi ngắn (số chuỗi hữu hạn) không?

Question

Vì vậy, tôi hiểu rằng có bằng chứng cho thấy MD5 không thể đảm bảo tính duy nhất vì có nhiều chuỗi trong vũ trụ hơn là chuỗi băm MD5, nhưng có bằng chứng ngược cho số chuỗi hữu hạn không?

Về cơ bản, nếu tôi có chuỗi có độ dài tối đa của X, có một X mà MD5 được đảm bảo là duy nhất không? nếu có, thì X là gì? và nếu có nhiều hơn một giá trị cho X, giá trị tối đa của X là bao nhiêu?

hoặc có X như vậy cho bất kỳ thuật toán băm khác, SHA-1, v.v ... không?

Answer 1

Câu trả lời cho câu hỏi của bạn là có. Đối với bất kỳ hàm băm nào, có độ dài tối đa X mà bạn sẽ lấy lại các chuỗi duy nhất. Tuy nhiên, việc tìm kiếm X có thể rất khó. Ý tưởng là chạy chương trình này:

X= 0; 
For i = 0 onward 
    For all strings of length i 
     Compute the hash code of that string. 
     If a collision is found, return X. 
    X = i 

Ý tưởng là chỉ liệt kê các chuỗi dài hơn và dài hơn cho đến khi bạn tìm thấy va chạm băm. Cuối cùng bạn sẽ phải, vì cuối cùng bạn sẽ tạo ra nhiều chuỗi hơn so với các đầu ra băm có thể có. Theo dự kiến, giả sử rằng hàm băm thực sự là khá ngẫu nhiên, bạn sẽ cần tạo các chuỗi khác nhau O (√ U) trước khi bạn tìm thấy xung đột, trong đó U là kích thước của không gian mà hàm băm ánh xạ . Đối với băm 256 bit, đây là 2 . Điều này có nghĩa rằng trong thực tế chương trình trên sẽ không bao giờ thực sự chấm dứt trừ khi hàm băm bị hỏng, nhưng về lý thuyết nó có nghĩa là số X của bạn tồn tại.

Hy vọng điều này sẽ hữu ích!

Answer 2

Khái quát những câu trả lời xuất sắc ở đây: What's the shortest pair of strings that causes an MD5 collision?

Vụ tấn công được biết đến ngắn nhất trên MD5 yêu cầu 2 khối đầu vào, tức là 128 byte hoặc 1024 bit.

Đối với bất kỳ thuật toán băm nào xuất ra N bit, giả sử nó phân phối đầu vào khoảng ngẫu nhiên, bạn có thể cho rằng xung đột có nhiều hơn 50% khả năng trong khoảng sqrt(2^N) đầu vào. Ví dụ, MD5 băm đến 128 bit, vì vậy bạn có thể mong đợi một xung đột giữa tất cả các đầu vào 64 bit. Điều này giả định một băm ngẫu nhiên thống nhất. Bất kỳ điểm yếu nào cũng sẽ làm giảm số lượng đầu vào trước khi xảy ra va chạm.