Tôi đang tạo một ứng dụng lưu trữ tài liệu và cung cấp cho từng người một UID dựa trên thông báo SHA1 về một số thứ bao gồm dấu thời gian. Thông báo có nhiều ký tự và tôi muốn cho phép người dùng xác định tài liệu bằng cách sử dụng ký tự x đầu tiên của thông báo đầy đủ. Giá trị tốt cho x nếu số lượng tài liệu là khoảng 10K - 100K?Có bao nhiêu bạn có thể cắt bớt mã băm SHA1 và chắc chắn có một ID duy nhất?
Điều chỉnh các công thức trên wikipedia for the Birthday problem, bạn có thể ước tính xác suất va chạm là e^(-n^2/(2^(b+1))), trong đó n là số tài liệu và b là số bit. Graphing this formula with n=100,000, có vẻ như bạn sẽ muốn b> 45 ít nhất. Tôi muốn có xu hướng đi với 64 để làm cho nó một số đẹp và tròn. Điều đó nói rằng, có một kế hoạch để đối phó với va chạm nếu chúng xảy ra (có thể thay đổi dấu thời gian một chút, hoặc thêm một nonce?)
Đối với vấn đề đó, nếu sha1 dựa trên nhiều hơn nội dung của tài liệu, tại sao không chỉ đơn giản là làm cho nó một ID ngẫu nhiên? Trong trường hợp này, các va chạm ít có vấn đề hơn, vì bạn luôn có thể tạo ra một số ngẫu nhiên mới và thử lại (xác suất va chạm với một lần thử duy nhất là như nhau, tuy nhiên).
Có thực sự không phải là một giá trị cho việc này; một phần của những gì làm cho SHA là một thuật toán băm có mục đích chung tốt là dữ liệu tương tự không nhất thiết tạo ra các giá trị băm tương tự. Đặt cược tốt nhất của bạn (không biết bất kỳ điều gì khác về hệ thống của bạn) sẽ chỉ là tìm kiếm danh sách tài liệu có băm bắt đầu bằng giá trị do người dùng cung cấp, sau đó trình bày chúng với danh sách tài liệu để chọn hoặc chuyển trực tiếp đến tài liệu nếu chỉ có một.
là những gì git làm với vòng quay? – dan
@dan Nó là, và nó thường là một cách tiếp cận khá tốt. –
Vâng, đây là một thể quá đơn giản của một câu trả lời ..
Nếu với sha1 đầy đủ, bạn nhận được khoảng 1 trong 2^160 cơ hội va chạm, sau đó bằng cách cắt xén một ký tự bạn tăng nguy cơ va chạm bằng 16 (tất cả các giá trị có thể có của nhân vật cắt ngắn) ... là 2^4 .. Vì vậy, nếu bạn cắt x ký tự, bạn sẽ nhận được 1 trong 2^(160 - 4 * x) cơ hội va chạm .. phải không?
Đối với một tài liệu duy nhất điều này là đúng, nhưng xác suất của bất kỳ va chạm xảy ra cho bất kỳ cặp tài liệu tăng nhanh hơn nhiều – bdonlan
Biham/Chen cung cấp các ví dụ về gần va chạm; và Knudsen chứng minh sự khác biệt bị cắt ngắn. Cả hai đều là vấn đề cho băm bị cắt ngắn; không phải là trường hợp nghịch lý sinh nhật. – jww
Đây là generalization trong số the birthday problem. Trong trường hợp của bạn n là số tài liệu và thay vì hằng số 365, bạn sẽ có số khả năng mà phần cắt cung cấp cho bạn (vì vậy đối với số bit k là 2 k).
Tất nhiên, tính toán chính xác không nằm trong câu hỏi, nhưng bạn có thể sử dụng approximation.
Biham/Chen cung cấp các ví dụ về các va chạm gần; và Knudsen chứng minh sự khác biệt bị cắt ngắn.Cả hai đều là vấn đề cho băm bị cắt ngắn; không phải là trường hợp nghịch lý sinh nhật. – jww
Hãy cẩn thận cắt ngắn vì không có bằng chứng giảm nào cho thấy băm nhỏ hơn được bảo mật. Xem số http://csrc.nist.gov/groups/ST/hash/documents/Kelsey_Truncation.pdf của Kelsey. Kelsey đưa ra các đối số heuristic cho biết như vậy ("Hash Outputs" và "Near Collisions"). Biham/Chen cung cấp các ví dụ về các va chạm gần; và Knudsen chứng minh sự khác biệt bị cắt ngắn.
Cuối cùng, bạn có thể muốn cung cấp dữ liệu của bạn thành một HMAC với kích thước cắt ngắn (kích thước được tiêu hóa bởi HMAC, quá) và sau đó sử dụng HMAC cắt ngắn.
Xin chào JWW, về NIST-PDF, cách bạn diễn giải nó? Công thức của @ bdonlan, 'e^(- n^2/(2^(b + 1)))', là một xấp xỉ tốt để ước tính cắt ngắn hay không? Nếu không, công thức hoặc thuật toán để kiểm tra * số bit tối thiểu * (_bmin_) cho việc cắt ngắn SHA1 là gì? –
Nhỏ nit - Không phải là formuala e^(- n^2/(2^(b + 1)))? Nó thay đổi trả lời một chút để b> 40. – Fakrudeen
@ Fakrudeen, thực sự - tôi đã thực hiện một lỗi khi sao chép nó vào câu trả lời. Các đồ thị là chính xác mặc dù ..... mặc dù tôi chỉ bây giờ nhận ra stackoverflow đã không thực hiện một liên kết cho nó: | – bdonlan
Tôi đã cập nhật câu trả lời để có công thức chính xác như đã thỏa thuận trong các nhận xét. –