Alat pengembang · generator UUID
Berapa Banyak Bit Acak yang Dimiliki v4 UUID? 122, Bukan 128
· Cara kerjanya
uuid kriptografi browser-apis
Enam dari 128 bits dalam UUID acak ditetapkan oleh standar, menyisakan 122 untuk keacakan. Posting ini menunjukkan bagaimana memperkirakan peluang tabrakan dengan jujur dan mengapa tabrakan sebenarnya berasal dari generator yang rusak, bukan dari matematika.
Pertanyaan sang arsitek: apakah kita akan mendapatkan duplikatnya? — dari mana kekhawatiran itu berasal dan mengapa jawabannya bergantung pada generatornya
Arsitek bertanya: jika kita menghasilkan 10 juta UUID per hari selama sepuluh tahun, apakah kita akan mendapatkan duplikatnya? Jawaban jujurnya adalah: hampir pasti tidak, jika generatornya aman secara kriptografis; hampir pasti iya, kalau gensetnya rusak. Matematika RFC 9562 bagus: v4 UUID dengan 122 bit acak memiliki kemungkinan tabrakan kira-kira n² / 2 pangkat 123, di mana n adalah jumlah pengidentifikasi yang dihasilkan. Untuk sebagian besar sistem nyata, kemungkinan ini dapat diabaikan. Tangkapannya adalah rumus ini mengasumsikan setiap bit benar-benar acak. Jika generator bocor atau berulang atau diunggulkan seperti yang diduga, rumusnya salah, dan duplikasi menjadi tidak bisa dihindari. Tata letak 128-bit mencakup empat bit versi (0100 untuk v4) dan dua bit varian (10 untuk RFC 9562), yang ditetapkan dan ditetapkan oleh standar.
Enam bit mana yang digunakan — empat bit versi dan dua bit varian, dan mengapa bit tersebut disetel, bukan acak
Itu menyisakan 122 bits untuk keacakan. Formulasinya kadang-kadang disebut 2 ke bit acak 122, menghasilkan nilai unik. Dengan menggunakan perkiraan paradoks ulang tahun, probabilitas setidaknya satu tabrakan di antara n nilai yang dihasilkan secara acak kira-kira n² / 2 hingga ke-123. Untuk n = 1 juta, ini adalah (10^6)² / 2^123 = 10^12 / 9. 3 × 10^36, yaitu sekitar 10^-25. Untuk n = 10 miliar, masih sekitar 10^-16. Ini bukan "secara efektif nol"; mereka adalah "Anda tidak akan pernah mengamati ini." Perkiraan ulang tahun memberikan cara konkret untuk menghitung risiko: hitung UUID yang ingin Anda buat, kuadratkan angka tersebut, bagi dengan 2 pangkat 123. Jika generatornya adalah crypto.getRandomValues browser, setiap bit didukung oleh entropi sistem operasi. Jika itu adalah Matematika.
Perkiraan ulang tahun secara sederhana — probabilitas setidaknya satu tabrakan di antara n pengidentifikasi kira-kira n kuadrat dibagi 2 dengan 123
Untuk UUID yang dihasilkan oleh generator keadaan yang tidak sesuai atau berulang, model matematikanya rusak karena asumsi independensinya salah. Benih pengujian tetap, perlengkapan yang disalin, atau cuplikan proses dapat memutar ulang nilai meskipun teks masih membawa camilan versi-4. Itu adalah cacat implementasi, bukan bukti bahwa penghitungan kolom 122 salah. Sumber biasa lainnya adalah menyalin pengidentifikasi literal yang sama ke beberapa perlengkapan dan kemudian menggabungkan datanya. Saat menyelidiki duplikat, pertahankan generator, kebijakan seed, siklus hidup proses, dan riwayat impor. Jangan melompat dari satu nilai berulang ke klaim bahwa keluaran CSPRNG independen menghabiskan ruang UUID.
Contoh praktis - memasukkan laju pembangkitan dan rentang waktu yang dinyatakan ke dalam perkiraan, dengan setiap langkah ditampilkan sehingga Anda dapat mengganti angka Anda sendiri
Proses forking tanpa sinkronisasi ulang keadaan acak. Bug di mana Math.random digunakan sebagai gantinya crypto.getRandomValues. Perlengkapan uji yang dibuat dengan tangan dengan bahan yang sama UUID dalam beberapa baris dan secara tidak sengaja digunakan dalam produksi. Versi lama dari a UUID perpustakaan yang memiliki batasan jangkauan atau bug negara. Tak satu pun dari skenario ini melibatkan matematika perkiraan ulang tahun; mereka melibatkan implementasi yang rusak atau kesalahan operasional. Hitung risiko tabrakan dengan jujur untuk sistem Anda: hitung lajunya UUID generasi (per detik, per hari, per tahun), proyeksikan sepanjang waktu sistem akan berjalan, dan masukkan totalnya ke dalam rumus ulang tahun. Jika sistem Anda menghasilkan 100,000 UUID per hari selama lima tahun (182 total juta), probabilitas tumbukan adalah (1. 82 × 10^8)² / 2^123 ≈ 3. 3 × 10^-22, yang dapat diabaikan.
Dari mana sebenarnya duplikat berasal — Math.random seed, mesin virtual yang dikloning, proses bercabang dengan status yang disalin, dan salin-tempel di perlengkapan
Jika Anda menghasilkan 10 juta per detik selama setahun (total 315 triliun), kemungkinannya adalah (3.15 × 10^14)² / 2^123 ≈ 10^-10, yang jumlahnya masih semakin kecil. Perkiraan ini mengasumsikan bahwa setiap bit bersifat independen dan acak. Generator ToolAcre menggunakan crypto.getRandomValues, yang memberi Anda keacakan yang didukung CSPRNG; operasi adalah satu-satunya bagian yang perlu Anda percayai. Jangan pernah mengandalkan kemungkinan tabrakan sebagai alasan untuk melewatkan pemeriksaan otorisasi yang tepat. UUID bukanlah kata sandi, bukan token akses, dan bukan rahasia meskipun itu adalah 122 bit acak. Keunikan adalah manfaatnya; ketidakpastian adalah properti terpisah (dan lebih penting) yang mencegah tebakan. Matematika ulang tahun menangani keunikan; itu tidak membahas seumur hidup (haruskah UUID ini kedaluwarsa? ), kerahasiaan (apakah perlu di-hash sebelum disimpan?), atau otorisasi (apakah memiliki UUID ini membuktikan sesuatu tentang penelepon?). Generator ToolAcre memberi Anda UUID yang didukung CSPRNG dengan 122 bit acak, yang berarti keunikan yang dimiliki matematika dan ketidakpastiannya masuk akal. Segala sesuatu yang lain—validasi token, masa berlaku, kontrol akses—adalah tanggung jawab aplikasi Anda. Rumus probabilitas mengasumsikan independensi setiap UUID yang dihasilkan dari generasi sebelumnya. Jika sistem Anda menghasilkan pengidentifikasi dari satu instance CSPRNG, dan setiap panggilan mengambil keacakan baru dari OS, asumsi independensi berlaku. Jika sistem Anda menggunakan status CSPRNG yang di-cache atau generator yang diunggulkan tanpa penyemaian ulang OS, asumsi tersebut akan gagal. Risiko tabrakan meningkat secara dramatis jika sumber entropi habis (terjadi pada beberapa sistem tertanam atau mesin virtual yang sedang dimuat) atau jika keadaan acak tidak pernah disetel ulang di antara proses (proses forking tanpa melakukan seeding ulang CSPRNG).
Apa yang tidak tercakup dalam hal ini — keunikan v1 dan v7, yang bertumpu pada stempel waktu dan urutan jam, bukan pada keacakan saja
Fallback ToolAcre memanggil crypto.getRandomValues untuk setiap array byte dan tidak memiliki status PRNG tingkat aplikasi. Internal platform tetap menjadi tanggung jawab browser dan sistem operasi. Mensimulasikan tabrakan dengan generator nyata menunjukkan perbedaan antara teori dan praktik yang rusak. Generator yang dibuat dengan Math.random yang dimulai dari benih yang sama akan menghasilkan urutan yang identik; Anda akan melihat tabrakan UUID pertama dalam beberapa ratus hingga beberapa ribu nilai yang dihasilkan, bukan setelah nilai 2^60 (akar kuadrat dari 2^122) seperti perkiraan perkiraan ulang tahun. Generator yang menggunakan crypto.getRandomValues dari entropi OS suara akan menghasilkan tabrakan hanya ketika probabilitas teoretis menjadi tidak dapat dihindari (sekitar 2^60 UUID), jumlah yang sangat besar sehingga Anda tidak akan pernah mencapainya. Generator yang menggunakan sumber entropi yang lemah atau digunakan kembali (umumnya terjadi pada pustaka UUID atau kerangka pengujian yang diimplementasikan dengan buruk) akan menghasilkan tabrakan di antara keduanya.
Kesimpulan: percayalah pada matematika, audit generatornya — generator ToolAcre menggunakan CSPRNG browser, yang merupakan bagian yang tidak boleh dipalsukan
Tes batch dapat menangkap implementasi yang mengembalikan konstanta atau memutar ulang urutan yang jelas, namun sampel yang lewat tidak dapat membuktikan keunikan di masa depan. Sistem produksi harus tetap menerapkan batasan unik jika pengidentifikasi duplikat akan merusak data. Impor memerlukan perhatian khusus karena dua sistem sumber yang valid mungkin sudah berisi pengidentifikasi literal yang sama, dan perlengkapan dapat disalin di seluruh lingkungan. Pengujian ToolAcre memeriksa bahwa kumpulan 500 berisi 500 nilai berbeda; itu adalah pemeriksaan regresi untuk penerapan ini, bukan jaminan statistik. Jika muncul duplikat, simpan bukti dan periksa jalur pembuatan, impor, perlengkapan, dan penyimpanan sebelum menyebutkan penyebabnya.