Cơ hội của một băm trùng lặp khi sử dụng 8 ký tự đầu tiên của SHA1

Question

Nếu tôi có chỉ mục URL và xác định chúng bằng 8 ký tự đầu tiên của hàm băm SHA1, xác suất của hai URL khác nhau có ID giống nhau là bao nhiêu?

Answer 1

@Teepeemm đã trả lời chính xác câu hỏi có liên quan 'với một chuỗi 8 số thập phân cụ thể, cơ hội của một mã băm SHA-1 khác xuất hiện với số cùng một số?' Đó là một số rất nhỏ.

Câu hỏi này có nghĩa là câu hỏi khác nhau: 'được cung cấp một số lượng lớn các chuỗi gồm 8 chữ số, cơ hội của hai số này giống nhau như thế nào?' cho câu hỏi chỉ ra, điều này có liên quan đến birthday paradox, đó không phải là 'cơ hội của một người nào đó trong phòng có sinh nhật giống như tôi là gì?', nhưng thay vào đó 'cơ hội của bất kỳ số nào hai người trong phòng này cùng một ngày sinh nhật? 'Như được biết một cách hợp lý, cơ hội đó là 50% chỉ với 23 người.

Vấn đề băm va chạm về cơ bản là cùng một vấn đề, nhưng khái quát hóa từ N = 365 ngày để N = 16^8 chuỗi 8-byte, đó là khoảng 4.30e9. Đó là số ‘generalised birthday problem’. Sử dụng biểu thức được trích dẫn ở đó (n = sqrt (2 * d * ln (1/(1-p))), với d = 4.30e9 và p = 0.5, chúng tôi tìm thấy 50% cơ hội va chạm với chỉ 77000 thử nghiệm. Nếu bạn vẽ hàm tương ứng, bạn sẽ thấy xác suất tăng khá nhanh khi số lượng thử nghiệm tăng.

Ngay cả với 16 byte băm (vì vậy d = 16^16) có 50 % cơ hội xảy ra xung đột chỉ sau 5 tỷ thử nghiệm.

Chúc mừng sinh nhật!

Answer 2

Hàm băm SHA-1 có 40 chữ số cơ bản-16. Nếu bạn chỉ xem 8 người đầu tiên trong số họ, thì cơ hội mà url thứ hai có 8 chữ số giống nhau là (1/16)^8 ~ 2.32e-10. Trên thực tế, điều này không phụ thuộc vào việc có 40 chữ số để bắt đầu, hoặc thậm chí đó là SHA-1. Giả thiết duy nhất bạn cần là SHA-1 có 8 số đầu tiên độc lập và phân phối giống nhau.