Bentrok saat membuat UUID di JavaScript?

94

Ini berkaitan dengan pertanyaan ini . Saya menggunakan kode di bawah ini dari jawaban ini untuk menghasilkan UUID dalam JavaScript:

'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, function(c) {
    var r = Math.random()*16|0, v = c == 'x' ? r : (r&0x3|0x8);
    return v.toString(16);
});

Solusi ini tampaknya berfungsi dengan baik, tetapi saya mengalami benturan. Inilah yang saya miliki:

  • Aplikasi web yang berjalan di Google Chrome.
  • 16 pengguna.
  • sekitar 4000 UUID telah dibuat dalam 2 bulan terakhir oleh para pengguna ini.
  • Saya mendapat sekitar 20 tabrakan - misalnya UUID baru yang dibuat hari ini sama dengan sekitar 2 bulan lalu (pengguna berbeda).

Apa yang menyebabkan masalah ini dan bagaimana cara menghindarinya?

Muxa
sumber
2
Gabungkan angka acak yang bagus dengan waktu saat ini (dalam milidetik). Peluang dari nomor acak bertabrakan pada saat yang sama sangat, sangat, sangat rendah.
jfriend00
7
@ jfriend00 jika Anda perlu melakukan itu maka itu bukan "nomor acak yang baik", bahkan bukan nomor acak-semu yang layak.
Attila O.
2
untuk apa (r&0x3|0x8)porsi / evaluasi itu?
Kristian
Bagaimana dengan menambahkan Date.now (). ToString () ke dalamnya?
Vitim.us
4
Ada masalah besar dalam arsitektur Anda, yang tidak terkait dengan UUID - klien mungkin sengaja menghasilkan ID yang bertabrakan. Hasilkan ID hanya dengan sistem yang Anda percayai. Sebagai solusinya, tambahkan ID yang dibuat klien dengan user_id, sehingga klien lawan / yang salah hanya dapat bertabrakan dengan dirinya sendiri (dan menanganinya di sisi server).
Dzmitry Lazerka

Jawaban:

35

Tebakan terbaik saya adalah yang Math.random()rusak pada sistem Anda karena beberapa alasan (aneh kedengarannya). Ini adalah laporan pertama yang saya lihat dari seseorang yang mengalami tabrakan.

node-uuidmemiliki test harness yang dapat Anda gunakan untuk menguji distribusi digit hex dalam kode itu. Jika itu terlihat oke maka tidak Math.random(), jadi coba gantikan implementasi UUID yang Anda gunakan ke dalam uuid()metode di sana dan lihat apakah Anda masih mendapatkan hasil yang baik.

[Pembaruan: Baru saja melihat laporan Veselin tentang bug dengan Math.random()saat startup. Karena masalahnya hanya pada saat permulaan, node-uuidpengujian tersebut tidak mungkin berguna. Saya akan berkomentar lebih detail di tautan devoluk.com.]

broofa
sumber
1
Terima kasih, saya menggunakan uuid.js sekarang, karena ini menggunakan kripto yang kuat dari browser jika tersedia. Akan melihat apakah ada tabrakan.
Muxa
dapatkah Anda memberikan tautan ke kode uuid.js yang Anda maksud? (maaf, tidak yakin lib mana yang Anda maksud.)
broofa
10
Tidak ada tabrakan sejauh ini :)
Muxa
Bagaimanapun, jika itu Chrome dan hanya saat memulai, aplikasi Anda dapat menghasilkan dan membuang deretan, katakanlah, sepuluh panduan menggunakan fungsi di atas :)
Vinko Vrsalovic
Masalahnya adalah dengan entropi terbatas yang Anda dapatkan dari Math.random (). Untuk beberapa browser, entropinya serendah hanya 41 bit. Memanggil Math.random () beberapa kali tidak akan menaikkan entropi. Jika Anda benar-benar menginginkan UUID v4 yang unik, Anda perlu menggunakan RNG yang kuat secara kriptografis yang menghasilkan setidaknya 122bit entropi per UUID yang dihasilkan.
mlehmk
36

Memang ada benturan tapi hanya di bawah Google Chrome. Lihat pengalaman saya tentang topik tersebut di sini

http://devoluk.com/google-chrome-math-random-issue.html

(Tautan rusak pada 2019. Tautan arsip: https://web.archive.org/web/20190121220947/http://devoluk.com/google-chrome-math-random-issue.html .)

Sepertinya tabrakan hanya terjadi pada beberapa panggilan pertama Math.random. Penyebab jika Anda hanya menjalankan metode createGUID / testGUIDs di atas (yang jelas merupakan hal pertama yang saya coba) itu hanya berfungsi tanpa benturan sama sekali.

Jadi untuk melakukan tes lengkap seseorang perlu memulai ulang Google Chrome, menghasilkan 32 byte, memulai ulang Chrome, menghasilkan, memulai ulang, menghasilkan ...

Veselin Kulov
sumber
2
Itu cukup mengkhawatirkan - apakah ada yang melaporkan bug?
UpTheCreek
1
Terutama seperti tautan ke generator bilangan acak yang lebih baik di javascript: baagoe.com/en/RandomMusings/javascript
Leopd
Sayangnya, tautan tersebut sekarang rusak :(
Gus
7
Adakah yang bisa memastikan jika bug ini telah diatasi?
Xdrone
20

Hanya agar orang lain dapat mengetahui hal ini - saya mengalami banyak sekali tabrakan yang terlihat menggunakan teknik pembuatan UUID yang disebutkan di sini. Tabrakan ini berlanjut bahkan setelah saya beralih ke seedrandom untuk generator nomor acak saya. Itu membuat saya merobek rambut saya, seperti yang bisa Anda bayangkan.

Saya akhirnya menemukan bahwa masalahnya (hampir?) Secara eksklusif terkait dengan bot perayap web Google. Segera setelah saya mulai mengabaikan permintaan dengan "googlebot" di bidang agen pengguna, tabrakan tersebut menghilang. Saya menduga mereka harus menyimpan hasil skrip JS dalam beberapa cara semi-cerdas, dengan hasil akhir bahwa peramban spidering mereka tidak dapat diandalkan untuk berperilaku seperti yang dilakukan peramban normal.

Hanya FYI.

Ken Smith
sumber
2
Mengalami masalah yang sama dengan sistem metrik kami. Melihat ribuan tabrakan UUID menggunakan modul 'node-uuid' untuk menghasilkan ID sesi di browser. Ternyata itu googlebot selama ini. Terima kasih!
domkck
4

Saya ingin memposting ini sebagai komentar untuk pertanyaan Anda, tetapi tampaknya StackOverflow tidak mengizinkan saya.

Saya baru saja menjalankan pengujian dasar 100.000 iterasi di Chrome menggunakan algoritme UUID yang Anda posting dan tidak ada benturan. Berikut cuplikan kodenya:

var createGUID = function() {
    return 'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, function(c) {
        var r = Math.random()*16|0, v = c == 'x' ? r : (r&0x3|0x8);
        return v.toString(16);
    });
}

var testGUIDs = function(upperlimit) {
    alert('Doing collision test on ' + upperlimit + ' GUID creations.');
    var i=0, guids=[];
    while (i++<upperlimit) {
        var guid=createGUID();
        if (guids.indexOf(guid)!=-1) {
            alert('Collision with ' + guid + ' after ' + i + ' iterations');
        }
        guids.push(guid);
    }
    alert(guids.length + ' iterations completed.');
}

testGUIDs(100000);

Apakah Anda yakin tidak ada hal lain yang terjadi di sini?

pengguna533676
sumber
4
Ya, saya juga menjalankan beberapa tes lokal dan tidak ada tabrakan. Tabrakan terjadi antara UUID yang dibuat di mesin pengguna yang berbeda. Saya mungkin perlu membuat beberapa data pada mesin yang berbeda dan memeriksa tabrakan.
Muxa
2
Juga, saya telah memperhatikan bahwa tabrakan antara UUID yang dihasilkan berjarak 3-4 minggu.
Muxa
Sangat aneh. Platform apa yang Anda jalankan?
pengguna533676
1
Tampaknya tidak mungkin ada cacat yang begitu mendasar dalam Math.random () V8, tetapi Chromium 11 menambahkan dukungan untuk pembuatan bilangan acak yang kuat menggunakan API window.crypto.getRandomValues ​​jika Anda ingin mencobanya. Lihat blog.chromium.org/2011/06/… .
pengguna533676
Berjalan dengan kombinasi Windows 7 dan Windows XP.
Muxa
3

Jawaban yang awalnya memposting solusi UUID ini diperbarui pada 2017-06-28:

Sebuah artikel yang baik dari pengembang Chrome membahas keadaan kualitas Math.random PRNG di Chrome, Firefox, dan Safari. tl; dr - Pada akhir 2015 "cukup bagus", tetapi bukan kualitas kriptografi. Untuk mengatasi masalah itu, berikut adalah versi terbaru dari solusi di atas yang menggunakan ES6, cryptoAPI, dan sedikit JS wizardy Saya tidak dapat mengambil kredit untuk :

function uuidv4() {
  return ([1e7]+-1e3+-4e3+-8e3+-1e11).replace(/[018]/g, c =>
    (c ^ crypto.getRandomValues(new Uint8Array(1))[0] & 15 >> c / 4).toString(16)
  )
}

console.log(uuidv4());

Luke
sumber
0

Jawabannya di sini berhubungan dengan "apa yang menyebabkan masalah?" (Masalah benih Chrome Math.random) tetapi bukan "bagaimana saya bisa menghindarinya?".

Jika Anda masih mencari cara untuk menghindari masalah ini, saya menulis jawaban ini beberapa waktu lalu sebagai modifikasi dari fungsi Broofa untuk mengatasi masalah yang sebenarnya ini. Ini bekerja dengan mengimbangi 13 angka hex pertama dengan bagian hex dari timestamp, yang berarti bahwa meskipun Math.random berada di seed yang sama, itu masih akan menghasilkan UUID yang berbeda kecuali dibuat pada milidetik yang sama persis.

Briguy37
sumber