Xác suất của các va chạm SHA1

Question

Cho một tập hợp 100 chuỗi khác nhau có chiều dài bằng nhau, làm thế nào bạn có thể định lượng xác suất mà xung đột tiêu hóa SHA1 đối với các chuỗi là khó xảy ra ...?

Answer 1

Are các giá trị băm 160 bit được tạo ra bởi SHA-1 đủ lớn để đảm bảo dấu vân tay của mỗi khối là duy nhất? Giả sử giá trị hash ngẫu nhiên với một phân phối thống nhất, một bộ sưu tập của khối dữ liệu n khác nhau và một hash chức năng mà tạo ra bit b, xác suất p rằng sẽ có một hoặc nhiều va chạm giáp số các cặp các khối nhân với số bằng xác suất mà một cặp nhất định sẽ va chạm.

(nguồn: http://bitcache.org/faq/hash-collision-probabilities)

Answer 2

Đó là Birthday Problem - bài viết cung cấp các xấp xỉ tốt đẹp giúp dễ dàng ước tính xác suất. Xác suất thực tế sẽ rất rất rất thấp - xem this question để biết ví dụ.

Answer 3

Vâng, xác suất xảy ra xung đột sẽ là 1 - ((2^160 - 1)/2^160) * ((2^160 - 2)/2^160) * ... * ((2)^160 - 99)/2^160).

Hãy suy nghĩ về xác suất xảy ra xung đột 2 mục trong không gian 10. Mục đầu tiên là duy nhất với xác suất 100%. Thứ hai là duy nhất với xác suất 9/10. Vì vậy, xác suất của cả hai là duy nhất là 100% * 90%, và xác suất của một vụ va chạm là 1 - (100% * 90%), hoặc 1 - ((10 - 0)/10) * ((10 - 1)/10) hoặc 1 - ((10 - 1)/10).

Rất khó xảy ra. Bạn sẽ phải có nhiều chuỗi hơn để nó trở thành một khả năng từ xa.

Hãy xem bảng trên this page on Wikipedia; chỉ nội suy giữa các hàng cho 128 bit và 256 bit.