Kolizje podczas generowania identyfikatorów UUID w JavaScript?

94

Dotyczy to tego pytania . Używam poniższego kodu z tej odpowiedzi do generowania UUID w 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);
});

Wydawało się, że to rozwiązanie działa dobrze, ale pojawiają się kolizje. Oto co mam:

  • Aplikacja internetowa działająca w Google Chrome.
  • 16 użytkowników.
  • około 4000 UUID zostało wygenerowanych w ciągu ostatnich 2 miesięcy przez tych użytkowników.
  • Mam około 20 kolizji - np. Nowy UUID wygenerowany dzisiaj był taki sam jak około 2 miesiące temu (inny użytkownik).

Co powoduje ten problem i jak mogę go uniknąć?

Muxa
źródło
2
Połącz dobrą liczbę losową z bieżącym czasem (w milisekundach). Szanse na zderzenie się liczb losowych dokładnie w tym samym czasie są naprawdę, bardzo, bardzo niskie.
jfriend00
7
@ jfriend00, jeśli musisz to zrobić, to nie jest to „dobra liczba losowa”, nawet przyzwoita liczba pseudolosowa.
Attila O.
2
co oznacza (r&0x3|0x8)porcja / ocena?
Kristian,
A co z dołączeniem do niego Date.now (). ToString ()?
Vitim.us
4
W Twojej architekturze jest duży problem niezwiązany z identyfikatorami UUID - klient może celowo generować kolidujące identyfikatory. Generuj identyfikatory tylko przez zaufany system. Aby obejść ten problem, dołącz identyfikatory generowane przez klienta przed identyfikatorem user_id, aby przeciwnik / wadliwy klient mógł kolidować tylko ze sobą (i obsługiwać to po stronie serwera).
Dzmitry Lazerka

Odpowiedzi:

35

Domyślam się, że Math.random()z jakiegoś powodu twój system jest uszkodzony (jakkolwiek dziwnie to brzmi). To jest pierwszy raport, jaki widziałem, że ktoś ma kolizje.

node-uuidma wiązkę testową , której można użyć do przetestowania dystrybucji cyfr szesnastkowych w tym kodzie. Jeśli to wygląda w porządku, to nie jest Math.random(), więc spróbuj zastąpić implementację UUID, której używasz, do uuid()metody tamtej i sprawdź, czy nadal masz dobre wyniki.

[Aktualizacja: Właśnie zobaczyłem raport Veselina o błędzie Math.random()podczas uruchamiania. Ponieważ problem występuje tylko podczas uruchamiania, node-uuidtest raczej nie będzie przydatny. Bardziej szczegółowo skomentuję link devoluk.com.]

broofa
źródło
1
Dzięki, teraz korzystam z uuid.js, ponieważ używa on silnego krypto przeglądarki, jeśli jest dostępny. Zobaczy, czy są jakieś kolizje.
Muxa
czy możesz podać link do kodu uuid.js, do którego się odnosisz? (przepraszam, nie jestem pewien, którą bibliotekę masz na myśli.)
broofa,
10
Jak dotąd nie miał żadnych kolizji :)
Muxa
W każdym razie, jeśli jest to Chrome i tylko podczas uruchamiania, Twoja aplikacja może wygenerować i odrzucić rząd, powiedzmy, dziesięciu przewodników za pomocą powyższej funkcji :)
Vinko Vrsalovic
Problem polega na ograniczonej entropii, którą otrzymujesz z Math.random (). W przypadku niektórych przeglądarek entropia wynosi łącznie zaledwie 41 bitów. Wielokrotne wywołanie Math.random () nie podniesie entropii. Jeśli naprawdę potrzebujesz unikalnych UUID v4, musisz użyć silnego kryptograficznie RNG, który wytwarza co najmniej 122-bitową entropię na wygenerowany UUID.
mlehmk
36

Rzeczywiście są kolizje, ale tylko w Google Chrome. Sprawdź moje doświadczenie na ten temat tutaj

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

(Link uszkodzony od 2019 r. Link do archiwum: https://web.archive.org/web/20190121220947/http://devoluk.com/google-chrome-math-random-issue.html .)

Wydaje się, że kolizje mają miejsce tylko podczas kilku pierwszych wywołań Math.random. Ponieważ jeśli po prostu uruchomisz powyższą metodę createGUID / testGUIDs (która oczywiście była pierwszą rzeczą, którą wypróbowałem), działa ona bez żadnych kolizji.

Aby wykonać pełny test, należy ponownie uruchomić Google Chrome, wygenerować 32 bajty, ponownie uruchomić Chrome, wygenerować, ponownie uruchomić, wygenerować ...

Weselin Kulow
źródło
2
To dość niepokojące - czy ktoś zgłosił zgłoszenie błędu?
UpTheCreek
1
Szczególnie jak link do lepszych generatorów liczb losowych w javascript: baagoe.com/en/RandomMusings/javascript
Leopd
Niestety, wspomniany link jest teraz uszkodzony :(
Gus,
7
Czy ktoś może potwierdzić, czy ten błąd został rozwiązany?
Xdrone
21

Aby inni ludzie mogli to wiedzieć - napotkałem zaskakująco dużą liczbę pozornych kolizji przy użyciu techniki generowania UUID wspomnianej tutaj. Te kolizje trwały nawet po przełączeniu się na seedrandom dla mojego generatora liczb losowych. To sprawiło, że wyrwałem sobie włosy, jak możesz sobie wyobrazić.

W końcu doszedłem do wniosku, że problem był (prawie?) Związany wyłącznie z robotami robotów indeksujących Google. Gdy tylko zacząłem ignorować żądania z „googlebotem” w polu klienta użytkownika, kolizje zniknęły. Zgaduję, że muszą buforować wyniki skryptów JS w jakiś półinteligentny sposób, w wyniku czego nie można liczyć na to, że ich przeglądarka internetowa będzie zachowywać się tak, jak robią to zwykłe przeglądarki.

Tylko do Twojej wiadomości.

Ken Smith
źródło
2
Napotkaliśmy ten sam problem z naszym systemem metryk. Widziałem tysiące kolizji UUID przy użyciu modułu „node-uuid” do generowania identyfikatorów sesji w przeglądarce. Okazuje się, że przez cały czas był to Googlebot. Dzięki!
domkck
4

Chciałem opublikować to jako komentarz do twojego pytania, ale najwyraźniej StackOverflow mi na to nie pozwala.

Właśnie przeprowadziłem podstawowy test 100 000 iteracji w Chrome przy użyciu opublikowanego przez Ciebie algorytmu UUID i nie wykryłem żadnych kolizji. Oto fragment kodu:

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);

Czy na pewno nie dzieje się tu coś więcej?

user533676
źródło
4
Tak, przeprowadziłem też kilka lokalnych testów i nie miałem żadnych kolizji. Zdarzają się kolizje między identyfikatorami UUID, które są generowane na komputerach różnych użytkowników. Może być konieczne wygenerowanie niektórych danych na różnych komputerach i sprawdzenie kolizji.
Muxa
2
Zauważyłem również, że kolizje występują między identyfikatorami UUID generowanymi w odstępie 3-4 tygodni.
Muxa
Bardzo dziwne. Na jakiej platformie pracujesz?
user533676
1
Wydaje się mało prawdopodobne, że w Math.random () w V8 występuje tak podstawowa wada, ale Chromium 11 dodał obsługę silnego generowania liczb losowych za pomocą interfejsu API window.crypto.getRandomValues, jeśli chcesz go wypróbować. Zobacz blog.chromium.org/2011/06/… .
user533676
Działa w połączeniu z Windows 7 i Windows XP.
Muxa
3

Odpowiedź, która pierwotnie opublikowała to rozwiązanie UUID, została zaktualizowana 28 czerwca 2017 r .:

Dobry artykuł z programistów Chrome Omawiając stan jakości Math.random PRNG w Chrome, Firefoksie i Safari. tl; dr - od końca 2015 r. jest „całkiem niezła”, ale nie kryptograficzna. Aby rozwiązać ten problem, oto zaktualizowana wersja powyższego rozwiązania, która wykorzystuje ES6, cryptoAPI i trochę kreatora JS, za które nie mogę przypisać :

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());

Łukasz
źródło
0

Odpowiedzi tutaj dotyczą „co powoduje problem?” (Problem z nasionami Chrome Math.random), ale nie „jak mogę tego uniknąć?”.

Jeśli nadal szukasz, jak uniknąć tego problemu, napisałem tę odpowiedź jakiś czas temu jako zmodyfikowaną wersję funkcji Broofa, aby obejść ten konkretny problem. Działa poprzez przesunięcie pierwszych 13 liczb szesnastkowych o część szesnastkową znacznika czasu, co oznacza, że ​​nawet jeśli Math.random znajduje się na tym samym ziarnie, nadal generuje inny identyfikator UUID, chyba że zostanie wygenerowany dokładnie w tej samej milisekundach.

Briguy37
źródło