Tabrakan UUID [ditutup]

33

Adakah yang melakukan penelitian nyata tentang kemungkinan tabrakan UUID, terutama dengan UUID versi 4 (acak), mengingat bahwa generator angka acak yang kami gunakan tidak benar-benar acak dan bahwa kami mungkin memiliki lusinan atau ratusan mesin identik yang menjalankan kode yang sama menghasilkan UUID?

Rekan kerja saya menganggap pengujian tabrakan UUID sebagai pemborosan waktu, tetapi saya selalu memasukkan kode untuk menangkap pengecualian kunci duplikat dari database dan mencoba lagi dengan UUID baru. Tapi itu tidak akan menyelesaikan masalah jika UUID berasal dari proses lain dan merujuk ke objek nyata.

random uuid Paul Tomblin
sumber
4
Pertanyaan itu sudah dijawab di Stack Overflow: stackoverflow.com/questions/3038023/… , seperti yang menunjukkan pencarian dasar Google: google.com/search?q=uuid+collision
Arseni Mourzenko
3
Pertanyaan itu adalah tentang algoritma spesifik yang digunakan dalam SQL * Server, yang pasti BUKAN versi 4 (acak). Saya bertanya tentang versi 4 secara khusus.
Paul Tomblin
Apakah Anda mengatakan bahwa implementasi SQL Server NEWID()fungsi tidak acak? Jika demikian, apakah Anda memiliki sumber untuk mendukung klaim tersebut? Outputnya jelas terlihat seperti UU4 v4 bagi saya. NEWSEQUENTIALID()Jelas tidak sepenuhnya acak, tapi itu tujuannya : untuk menghasilkan UUID yang berfungsi dengan baik (serta UUID dapat, setidaknya) sebagai kunci indeks.
CVn
1
Saya akan menjawab pertanyaan terkait, yang menyatakan bahwa NEWID () berisi beberapa bit dari alamat mac, yang membuatnya menjadi UUID V1 atau V2, bukan V4.
Paul Tomblin
2
Pertanyaan ini tampaknya di luar topik karena ini adalah tentang sesuatu yang sudah dibahas ad-mual di internet, dalam buku-buku dan terutama tentang StackOverflow

Jawaban:

18

Wikipedia memiliki beberapa detail:

http://en.wikipedia.org/wiki/Universally_unique_identifier

http://en.wikipedia.org/wiki/Universally_unique_identifier#Random_UUID_probability_of_duplicates

Tetapi probabilitas hanya berlaku jika bitnya acak sempurna. Namun, RFC http://tools.ietf.org/html/rfc4122#halaman 14 yang ditautkan dalam jawaban lain mendefinisikan ini untuk versi 4:

"4.4. [...] Versi 4 UUID dimaksudkan untuk menghasilkan UUID dari angka yang benar-benar acak atau pseudo-acak. [...] Tetapkan semua bit lainnya ke nilai yang dipilih secara acak (atau pseudo-acak)."

Ini cukup banyak memungkinkan apa saja dari generator acak xkcd http://xkcd.com/221/ ke perangkat keras menggunakan kebisingan kuantum. Pertimbangan keamanan dalam RFC:

"6. Aplikasi terdistribusi menghasilkan UUID di berbagai host harus bersedia mengandalkan sumber nomor acak di semua host. Jika ini tidak layak, varian namespace harus digunakan."

Saya membaca ini sebagai: Anda sendirian. Anda bertanggung jawab untuk generator acak Anda dalam aplikasi Anda sendiri, tetapi ini dan yang lainnya didasarkan pada kepercayaan. Jika Anda tidak mempercayai kemampuan Anda sendiri untuk memahami dan menggunakan generator acak pilihan Anda dengan benar, maka memang ide yang bagus untuk memeriksa tabrakan. Jika Anda tidak mempercayai programmer dari proses lain, maka periksa tabrakan atau gunakan versi UUID yang berbeda.

Aman
sumber
11

Anda tentu harus mendeteksi jika terjadi tabrakan, dan aplikasi Anda harus mengeluarkan pengecualian jika itu terjadi. Misalnya jika UUID digunakan sebagai kunci utama dalam basis data, maka basis data tersebut akan menimbulkan kesalahan saat memasukkan ID yang bertabrakan.

Namun, saya akan percaya bahwa menulis kode untuk menghasilkan UUID baru dalam kasus tabrakan dan mencoba lagi menjadi buang-buang waktu. Peluang terjadinya tabrakan sangat kecil sehingga melemparkan pengecualian akan menjadi cara yang masuk akal untuk menghadapinya.

Ingat, ini tidak hanya membuang-buang waktu Anda sendiri menulis kode, tetapi juga membuat kode lebih kompleks, sehingga lebih sulit bagi orang berikutnya untuk membaca, karena hampir tidak ada keuntungan sama sekali.

Pete
sumber
2
UUID Anda hanya sebagus generator acak Anda. Dengan yang sangat ( sangat ) miskin satu tabrakan tidak hanya akan terjadi tetapi tidak bisa dihindari. Yang mengatakan mungkin memeriksa duplikat pada waktu generasi memang akan berlebihan, tetapi berharap bahwa situasinya dapat terjadi dan, menurut pendapat saya, tidak terlalu banyak meminta. Dalam beberapa domain (layanan kesehatan misalnya) saya pikir perlu untuk memiliki kode yang menangkap situasi seperti itu (mungkin sebagai deteksi tabrakan dalam database). Anda akan terkejut betapa banyak waktu yang saya habiskan untuk situasi debugging yang tidak pernah terjadi.
Newtopian
1
Saya pikir saya tidak membuat diri saya jelas. Saya telah memperbarui jawabannya menjadi lebih eksplisit.
Pete
7

Ini pertanyaan yang sangat bagus. Saya tidak percaya itu dianggap cukup terburu-buru untuk menggunakan UUID di mana-mana. Saya belum menemukan penelitian yang solid.

Sebuah saran: injak dengan sangat hati-hati di sini, dan ketahui kriptografi Anda dengan baik. Jika Anda menggunakan UUID 128-bit, 'efek ulang tahun' memberi tahu kami bahwa kemungkinan tabrakan setelah Anda menghasilkan sekitar 2 ^ 64 kunci, asalkan Anda memiliki 128 bit entropi di setiap kunci .

Sebenarnya agak sulit untuk memastikan bahwa inilah masalahnya. Keacakan yang sebenarnya dapat dihasilkan dari (a) peluruhan radioaktif (b) kebisingan radio latar belakang acak, sering terkontaminasi kecuali Anda berhati-hati (c) kebisingan elektronik yang dipilih dengan tepat, misalnya diambil dari dioda Zener yang bias balik. (Saya sudah bermain dengan yang terakhir, dan itu berfungsi seperti pesona, BTW).

Saya tidak akan mempercayai pernyataan seperti "Saya belum pernah melihat ini dalam satu tahun penggunaan", kecuali jika pengguna telah menghasilkan sesuatu yang mendekati 2 ^ 64 (mis. Sekitar 10 ^ 19) kunci, dan memeriksa semuanya terhadap satu sama lain, sebuah latihan non-sepele.

Masalahnya adalah ini. Katakanlah Anda hanya memiliki 100 bit entropi, ketika membandingkan kunci Anda dengan semua kunci lain yang dihasilkan orang lain di ruang kunci yang sama. Anda akan mulai melihat tabrakan di sekitar 2 ^ 50 yaitu. sekitar 10 ^ 15 kunci. Peluang Anda melihat tabrakan jika Anda telah mengisi basis data Anda dengan hanya 1000 miliar kunci masih dapat diabaikan. Dan jika Anda tidak memeriksa, nanti Anda akan mendapatkan kesalahan tak terduga yang merayap ke dalam database berukuran baris-peta Anda. Ini bisa menggigit keras.

Kenyataan bahwa ada beberapa pendekatan untuk menghasilkan UUID tersebut harus menimbulkan kekejangan sesaat. Ketika Anda menyadari bahwa beberapa generator menggunakan proses 'benar-benar acak' dengan entropi yang cukup untuk UUID tipe 4, Anda harus sangat khawatir kecuali Anda telah dengan cermat memeriksa konten entropi generator. (Kebanyakan orang tidak akan melakukan ini, atau bahkan tahu bagaimana caranya; Anda mungkin mulai dengan suite DieHarder). JANGAN mengacaukan pembuatan nomor pseudorandom dengan pembuatan nomor acak.

Sangat penting bagi Anda untuk menyadari bahwa entropi yang Anda masukkan adalah entropi yang Anda miliki, dan hanya mengganggu kunci dengan menerapkan fungsi kriptografi tidak mengubah entropi. Mungkin tidak jelas secara intuitif bahwa jika seluruh ruang saya terdiri dari angka 0 dan 1, konten entropi sama dengan dua string berikut, asalkan mereka satu-satunya dua pilihan: "Ini adalah string yang benar-benar sangat kompleks. 293290729382832 * ! @@ # & ^% $$), m} "dan" DAN SEKARANG UNTUK SESUATU YANG SANGAT BERBEDA ". Masih ada dua opsi.

Keacakan sulit untuk dilakukan dengan benar, dan hanya percaya bahwa "para ahli telah melihatnya, oleh karena itu tidak apa-apa" mungkin tidak cukup. Ahli kriptografi (dan ada beberapa di antaranya yang benar-benar cakap) adalah orang pertama yang mengakui bahwa mereka sering keliru. Kami memercayai hati, DigiNotar, dll.

Saya pikir Paul Tomblin sedang berhati-hati. 2c saya

pengguna199506
sumber
6

Masalah yang Anda miliki adalah bahwa jika Anda menggunakan "generator angka acak" dan Anda tidak tahu seberapa acak generator itu, maka kemungkinan tabrakan sebenarnya tidak diketahui. Jika generator angka acak berkorelasi dalam beberapa cara, kemungkinan tabrakan dapat meningkat secara dramatis - mungkin banyak, banyak pesanan atau besarnya.

Bahkan jika Anda memiliki probabilitas tabrakan yang sangat kecil, Anda memiliki masalah mendasar: Probabilitasnya adalah TIDAK 0. Ini berarti bahwa tabrakan AKAN akhirnya akan terjadi, mereka tidak akan sering terjadi.

Semakin sering Anda menghasilkan dan menggunakan UUID semakin cepat bahwa tabrakan cenderung terlihat. (menghasilkan 1 per tahun berarti waktu tunggu yang lebih lama daripada menghasilkan satu juta per detik, semua hal lain dianggap sama).

Jika probabilitas itu terbatas, tidak diketahui, dan Anda menggunakan banyak UUID maka Anda perlu mempertimbangkan konsekuensi dari tabrakan. Jika tidak bisa melempar pengecualian dan mematikan aplikasi bisnis, maka jangan lakukan itu! (Contoh di atas kepala saya: "Tidak apa-apa untuk mematikan server web di tengah memperbarui checkin perpustakaan ... itu tidak akan sering terjadi" dan "Tidak apa-apa untuk mematikan sistem penggajian di tengah-tengah melakukan pay run ". Keputusan ini mungkin merupakan langkah yang membatasi karier.)

Anda mungkin memiliki kasus yang lebih buruk, sekali lagi tergantung pada aplikasi Anda. Jika Anda menguji keberadaan UUID (yaitu, melakukan pencarian) dan kemudian membuat yang baru jika belum ada - yang merupakan hal yang cukup umum untuk dilakukan - maka Anda mungkin menemukan Anda sedang menghubungkan catatan atau membuat hubungan , padahal sebenarnya Anda sedang menghubungkan 2 hal melalui UUID yang seharusnya tidak terhubung. Ini adalah sesuatu di mana melempar pengecualian tidak akan menyelesaikan apa pun dan Anda memiliki kekacauan yang tidak terdeteksi dibuat di suatu tempat. Ini adalah jenis hal yang menyebabkan kebocoran informasi dan bisa sangat memalukan. (mis: Masuk ke bank Anda dan temukan Anda dapat melihat saldo akun orang lain! Buruk!)

Ringkasan: Anda perlu mempertimbangkan cara UUID Anda digunakan, dan konsekuensi dari tabrakan. Ini menentukan apakah Anda harus berhati-hati untuk mendeteksi dan menghindari tabrakan, mengambil tindakan sederhana jika terjadi tabrakan, atau tidak melakukan apa pun. Solusi sederhana, tunggal, satu-untuk-semua, cenderung tidak sesuai dalam beberapa keadaan.

dengan cepat_now
sumber
2
"Probabilitas (tabrakan) BUKAN 0" Urutan berhingga panjang memiliki properti ini. Bahkan dengan UUID v4 acak sempurna , setelah Anda menghasilkan 2 ^ 122 UUID unik (versi 128 bit minus 4 bit minus 2 bit yang dicadangkan), yang berikutnya Anda hasilkan dijamin akan bertabrakan. Kemungkinan besar Anda akan menabrak tabrakan lebih cepat dari itu. Pertanyaan yang lebih besar adalah apakah tabrakan setelah sesuatu seperti pengulangan 5e36 adalah masalah, dan itu tidak dapat dijawab secara umum (meskipun jelas mungkin untuk menjawab dalam setiap kasus tertentu), seperti yang Anda katakan dalam ringkasan.
CVn
Tentu saja. Ini adalah pernyataan yang jelas (tetapi masih diulang). Masalahnya adalah berapa banyak korelasi dengan generator nomor acak miliki. Ini mungkin meningkatkan kemungkinan tabrakan secara signifikan (2 ^ besar), tetapi berapa banyak sesuatu yang Anda tidak akan tahu kecuali Anda melakukan banyak penggalian, penelitian, atau perhitungan. Dengan asumsi probabilitas tabrakan secara signifikan lebih buruk daripada nilai terbaik mungkin lebih bijaksana. Setelah itu ... Anda kemudian perlu mempertimbangkan konsekuensinya.
cepat,
0

Ada dua masalah yang terlibat:

  1. Kualitas generator nomor acak yang digunakan.

  2. Jumlah UUID yang mungkin dihasilkan.

UUID "acak" memiliki 122 bit acak. Dengan asumsi keacakan sempurna, Anda dapat mengharapkan tumbukan pertama sekitar 2 ^ 61 dihasilkan UUIDs (itu akar kuadrat dari 2 ^ 122). Jika semua orang di dunia ini menghasilkan UUID per detik, itu 10.000.000.000 * 365 * 24 * 60 * 60 = 315360000000000000000 UUID per tahun, yang cukup dekat dengan 2 ^ 58. Artinya, setelah beberapa tahun Anda akan mendapatkan tabrakan pertama. Kecuali jika aplikasi Anda mendekati angka-angka itu, Anda dapat yakin bahwa Anda tidak akan mendapatkan tabrakan jika generator acak Anda memiliki kualitas yang baik.

Berbicara tentang generator bilangan acak: Jika Anda menggunakan generator perpustakaan C standar (langsung, tidak langsung, atau generator serupa), mungkin menaburinya dengan waktu, Anda akan dilewati. Ini tidak bisa menarik cukup entropi untuk menghindari tabrakan. Namun, jika Anda menggunakan linux, cukup baca 16 byte data dari /dev/urandom: Ini mengacu pada kumpulan entropi yang diaduk oleh kernel, yang memiliki akses ke beberapa peristiwa acak nyata. Kecuali Anda biasanya menghasilkan UUID benar-benar, sangat awal dalam urutan boot, /dev/urandomharus berperilaku seperti sumber acak yang sebenarnya.

cmaster
sumber
-1

Saya sudah mengujinya sekali menggunakan program (brute force) yang cukup sederhana yang menghasilkan 10 juta UUID-s dan saya belum pernah mengalami tabrakan.

The UUID RFC mengatakan bahwa UUID tidak hanya sekelompok (semu) nomor acak.

xea
sumber
1
Versi 4, yang saya tanyakan, cukup banyak adalah angka acak, kecuali 6 bit yang akan persis sama di semua.
Paul Tomblin
8
10 juta bahkan tidak setetes pun dalam ember. Hanya ada 1 dalam 3E30 kemungkinan tabrakan. Jika Anda menemukan satu, saya akan menyarankan Anda untuk bergegas keluar dan membeli tiket di setiap lotere yang Anda bisa!
Ross Patterson
@RossPatterson, yang secara khusus saya tanyakan adalah apakah Anda memiliki beberapa ratus komputer menggunakan algoritma psuedo-random yang sama persis pada perangkat keras yang sama secara dramatis meningkatkan kemungkinan tabrakan. Saya kira itu akan terjadi.
Paul Tomblin
1
@ Paul - Saya akan berpikir hanya jika ada cukup entropi dalam proses penyemaian awal - misalnya jika benih hanya dihasilkan dari waktu hari, dan semua mesin Anda mulai sangat dekat dengan saat yang sama. Saya sangat meragukan bahwa penyemaiannya sangat lemah - bahkan mungkin nomor seri perangkat keras digunakan, yang tentu saja akan unik untuk setiap mesin.
Steve314
1
Sayangnya, penyemaian bisa sangat lemah. Sistem Linux gemar menaburkan PRNG dari sumber yang sangat acak (aktivitas driver perangkat, dll. ), Tetapi di lingkungan lain, standarnya adalah menggunakan cap waktu saat ini, yang dengan mesin yang cukup dalam sinkronisasi waktu dekat, bisa menjadi masalah.
Ross Patterson