Công cụ dành cho nhà phát triển · Trình tạo UUID
Một v4 UUID có bao nhiêu bit ngẫu nhiên? 122, Không phải 128
· Cách thức hoạt động
uuid mật mã browser-apis
Sáu trong số 128 bits trong UUID ngẫu nhiên được cố định theo tiêu chuẩn, chỉ còn lại 122 là ngẫu nhiên. Bài đăng này cho thấy cách ước tính tỷ lệ va chạm một cách trung thực và tại sao các vụ va chạm thực sự lại đến từ máy phát điện bị hỏng chứ không phải từ toán học.
Câu hỏi của kiến trúc sư: liệu chúng ta có bao giờ có được một bản sao không? — nỗi lo lắng đến từ đâu và tại sao câu trả lời lại phụ thuộc vào người tạo ra
Kiến trúc sư hỏi: nếu chúng tôi tạo 10 triệu UUID mỗi ngày trong mười năm, liệu chúng tôi có bao giờ nhận được một bản sao không? Câu trả lời trung thực là: gần như chắc chắn là không, nếu trình tạo được bảo mật bằng mật mã; gần như chắc chắn là có, nếu trình tạo bị hỏng. Phép toán RFC 9562 là đúng: a v4 UUID với 122 bit ngẫu nhiên có xác suất xung đột khoảng n² / 2 lũy thừa thứ 123, trong đó n là số lượng giá trị nhận dạng được tạo ra. Đối với hầu hết các hệ thống thực, xác suất này là không đáng kể. Điều đáng chú ý là công thức này giả định mọi bit đều thực sự ngẫu nhiên. Nếu trình tạo bị rò rỉ hoặc lặp lại hoặc được gieo hạt theo dự đoán thì công thức sẽ sai và việc trùng lặp là không thể tránh khỏi. Bố cục 128-bit bao gồm bốn bit phiên bản (0100 cho v4) và hai bit biến thể (10 cho RFC 9562), được cố định và đặt theo tiêu chuẩn.
Sáu bit nào được dùng để chỉ - bốn bit phiên bản và hai bit biến thể, và tại sao chúng được đặt thay vì ngẫu nhiên
Điều đó để lại 122 bits tính ngẫu nhiên. Công thức đôi khi được gọi là 2 cho các bit ngẫu nhiên 122, tạo ra các giá trị duy nhất. Sử dụng phép tính gần đúng nghịch lý ngày sinh, xác suất xảy ra ít nhất một vụ va chạm giữa n giá trị được tạo ngẫu nhiên là khoảng n² / 2 đến bậc 123. Với n = 1 triệu, đây là (10^6)² / 2^123 = 10^12 / 9. 3 × 10^36, tức là khoảng 10^-25. Với n = 10 tỷ thì vẫn là khoảng 10^-16. Đây không phải là "số 0 một cách hiệu quả"; chúng là "bạn sẽ không bao giờ quan sát được điều này." Phép tính gần đúng ngày sinh đưa ra một cách cụ thể để tính toán rủi ro: đếm số UUID bạn dự định tạo, bình phương số đó, chia cho 2 lũy thừa thứ 123. Nếu trình tạo là crypto.getRandomValues của trình duyệt thì mọi bit đều được hỗ trợ bởi entropy của hệ điều hành. Nếu đó là môn Toán.
Ngày sinh gần đúng theo thuật ngữ đơn giản — xác suất xảy ra ít nhất một xung đột giữa n số nhận dạng gần bằng n bình phương chia cho 2 cho 123
Đối với UUID được tạo bởi trình tạo trạng thái lặp lại hoặc không phù hợp, mô hình toán học bị hỏng vì giả định tính độc lập của nó là sai. Hạt giống thử nghiệm cố định, bản cố định được sao chép hoặc ảnh chụp nhanh quy trình có thể phát lại các giá trị ngay cả khi văn bản vẫn mang phiên bản-4 nibble. Đó là những lỗi triển khai chứ không phải bằng chứng cho thấy phép tính trường 122 sai. Một nguồn thông thường khác là sao chép cùng một mã định danh theo nghĩa đen vào một số thiết bị cố định và sau đó hợp nhất dữ liệu của chúng. Khi điều tra một bản sao, hãy bảo quản trình tạo, chính sách hạt giống, vòng đời quy trình và lịch sử nhập. Không chuyển từ một giá trị lặp lại sang xác nhận rằng đầu ra CSPRNG độc lập đã cạn kiệt khoảng trống UUID.
Ví dụ đã hoạt động - đưa tốc độ tạo và khoảng thời gian đã nêu vào giá trị gần đúng, với mỗi bước được hiển thị để bạn có thể thay thế số liệu của riêng mình
Quá trình phân nhánh mà không cần đồng bộ lại trạng thái ngẫu nhiên. Lỗi trong đó Math.random được sử dụng thay vì crypto.getRandomValues. Một vật cố định thử nghiệm được làm thủ công với cùng UUID ở nhiều hàng và vô tình được sử dụng trong sản xuất. Phiên bản cũ của thư viện UUID có giới hạn phạm vi hoặc lỗi trạng thái. Không có kịch bản nào trong số này liên quan đến toán học gần đúng ngày sinh; chúng liên quan đến việc triển khai bị hỏng hoặc sai sót trong vận hành. Tính toán rủi ro va chạm một cách trung thực cho hệ thống của bạn: đếm tốc độ tạo UUID (mỗi giây, mỗi ngày, mỗi năm), dự đoán nó theo thời gian hệ thống sẽ chạy và cắm tổng số đó vào công thức ngày sinh. Nếu hệ thống của bạn tạo 100,000 UUID mỗi ngày trong 5 năm (tổng cộng 182 triệu), thì xác suất xung đột là (1. 82 × 10^8)² / 2^123 ≈ 3. 3 × 10^-22, không đáng kể.
Nơi các bản sao thực sự đến từ — Math.random hạt giống, máy ảo nhân bản, quy trình phân nhánh với trạng thái được sao chép và sao chép-dán trong thiết bị cố định
Nếu bạn tạo 10 triệu mỗi giây trong một năm (tổng cộng 315 nghìn tỷ), xác suất là (3. 15 × 10^14)² / 2^123 ≈ 10^-10, vẫn còn rất nhỏ. Những ước tính này giả định rằng mọi bit đều độc lập và ngẫu nhiên. Trình tạo ToolAcre sử dụng crypto.getRandomValues, mang đến cho bạn tính ngẫu nhiên được hỗ trợ bởi CSPRNG; hoạt động là phần duy nhất bạn cần tin tưởng. Không bao giờ dựa vào xác suất va chạm như một cái cớ để bỏ qua việc kiểm tra ủy quyền thích hợp. UUID không phải là mật khẩu, không phải mã thông báo truy cập và không phải bí mật ngay cả khi đó là 122 bit ngẫu nhiên. Sự độc đáo là lợi ích; tính không thể đoán trước là một thuộc tính riêng biệt (và quan trọng hơn) ngăn cản việc đoán. Toán học ngày sinh xử lý tính duy nhất; nó không giải quyết vấn đề trọn đời (UUID này có hết hạn không? ), bí mật (nó có cần được băm trước khi lưu trữ không?) hoặc ủy quyền (việc sở hữu UUID này có chứng minh được điều gì về người gọi không?). Trình tạo ToolAcre cung cấp cho bạn UUID được hỗ trợ CSPRNG với 122 bit ngẫu nhiên, có nghĩa là tính duy nhất của toán học và khả năng không thể đoán trước là hợp lý. Mọi thứ khác—xác thực mã thông báo, hết hạn, kiểm soát truy cập—là trách nhiệm của ứng dụng của bạn. Công thức xác suất giả định tính độc lập của mỗi UUID được tạo ra từ các thế hệ trước. Nếu hệ thống của bạn tạo số nhận dạng từ một phiên bản CSPRNG duy nhất và mỗi lệnh gọi lấy tính ngẫu nhiên mới từ HĐH thì giả định về tính độc lập sẽ được giữ nguyên. Nếu hệ thống của bạn sử dụng trạng thái CSPRNG được lưu trong bộ nhớ đệm hoặc trình tạo hạt giống mà không cần gieo mầm lại hệ điều hành thì giả định sẽ không thành công. Rủi ro xung đột tăng lên đáng kể nếu nguồn entropy cạn kiệt (xảy ra trên một số hệ thống nhúng hoặc máy ảo đang tải) hoặc nếu trạng thái ngẫu nhiên không bao giờ được đặt lại giữa các quy trình (rẽ nhánh quy trình mà không gieo lại CSPRNG).
Điều này không bao gồm - tính duy nhất của v1 và v7, dựa trên dấu thời gian và chuỗi đồng hồ thay vì chỉ tính ngẫu nhiên
Dự phòng ToolAcre gọi crypto.getRandomValues cho mỗi mảng byte và không giữ trạng thái PRNG cấp ứng dụng. Nội bộ nền tảng vẫn là trách nhiệm của trình duyệt và hệ điều hành. Mô phỏng va chạm với trình tạo thực tế cho thấy sự khác biệt giữa lý thuyết và thực hành chưa đúng. Trình tạo được tạo bằng Math.random bắt đầu từ cùng một hạt giống sẽ tạo ra các chuỗi giống hệt nhau; bạn sẽ thấy xung đột UUID đầu tiên trong vòng từ vài trăm đến vài nghìn giá trị được tạo, không phải sau các giá trị 2^60 (căn bậc hai của 2^122) như dự đoán về ngày sinh gần đúng. Trình tạo sử dụng crypto.getRandomValues từ entropy hệ điều hành âm thanh sẽ chỉ tạo ra xung đột khi xác suất lý thuyết trở nên không thể tránh khỏi (khoảng 2^60 UUID), một con số lớn đến mức bạn sẽ không bao giờ đạt được. Trình tạo sử dụng nguồn entropy yếu hoặc được sử dụng lại (phổ biến trong các thư viện hoặc khung kiểm tra UUID được triển khai kém) sẽ tạo ra xung đột ở đâu đó ở giữa.
Bài học rút ra: tin tưởng vào phép toán, kiểm tra trình tạo — trình tạo ToolAcre sử dụng CSPRNG của trình duyệt, đây là phần không được giả mạo
Kiểm thử hàng loạt có thể phát hiện việc triển khai trả về một hằng số hoặc phát lại một chuỗi rõ ràng, nhưng một mẫu đạt được không thể chứng minh tính duy nhất trong tương lai. Hệ thống sản xuất vẫn phải thực thi một ràng buộc duy nhất ở những nơi mà số nhận dạng trùng lặp có thể làm hỏng dữ liệu. Việc nhập đáng được chú ý đặc biệt vì hai hệ thống nguồn hợp lệ có thể đã chứa cùng một mã định danh theo nghĩa đen và các thiết bị cố định có thể được sao chép trên các môi trường. Kiểm tra của ToolAcre kiểm tra xem lô 500 có chứa 500 giá trị riêng biệt hay không; đó là kiểm tra hồi quy cho việc triển khai này, không phải là sự đảm bảo về mặt thống kê. Nếu xuất hiện một bản sao, hãy lưu giữ bằng chứng và kiểm tra các đường dẫn tạo, nhập, cố định và lưu trữ trước khi xác định nguyên nhân.