Kolizje UUID [zamknięte]

33

Czy ktoś przeprowadził jakiekolwiek rzeczywiste badania dotyczące prawdopodobieństwa kolizji UUID, szczególnie w przypadku UUID w wersji 4, biorąc pod uwagę, że generatory liczb losowych, których używamy, nie są tak naprawdę losowe i że możemy mieć dziesiątki lub setki identycznych maszyn z tym samym kodem generujesz UUID?

Moi współpracownicy uważają testowanie pod kątem kolizji UUID za całkowitą stratę czasu, ale zawsze umieszczam kod, aby wychwycić zduplikowany wyjątek klucza z bazy danych i spróbować ponownie z nowym UUID. Ale to nie rozwiąże problemu, jeśli UUID pochodzi z innego procesu i odnosi się do prawdziwego obiektu.

Paul Tomblin
źródło
4
Odpowiedź na pytanie została już udzielona na stosie przepełnienia: stackoverflow.com/questions/3038023/... , jak pokazuje podstawowe wyszukiwanie w Google: google.com/search?q=uuid+collision
Arseni Mourzenko
3
To pytanie dotyczy konkretnych algorytmów używanych w SQL * Server, który zdecydowanie nie jest wersją 4 (losową). Pytam konkretnie o wersję 4.
Paul Tomblin
Czy mówisz, że implementacja NEWID()funkcji przez SQL Server nie jest przypadkowa? Jeśli tak, czy masz jakieś źródła na poparcie takiego roszczenia? Jego dane wyjściowe wyraźnie mi przypominają UUID v4. NEWSEQUENTIALID()zdecydowanie nie jest całkowicie losowy, ale taki jest jego cel : generowanie identyfikatorów UUID, które działają dobrze (podobnie jak identyfikatory UUID) jako klucze indeksu.
CVn
1
Przechodzę od odpowiedzi na połączone pytanie, które stwierdza, że ​​NEWID () zawiera niektóre bity adresu mac, co czyni go UUID V1 lub V2, a nie V4.
Paul Tomblin
2
To pytanie wydaje się być nie na temat, ponieważ dotyczy czegoś, co zostało już omówione w Internecie, w książkach, a zwłaszcza na StackOverflow

Odpowiedzi:

18

Wikipedia ma pewne szczegóły:

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

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

Ale prawdopodobieństwo zachodzi tylko wtedy, gdy bity są całkowicie losowe. Jednak RFC http://tools.ietf.org/html/rfc4122#page-14 połączony w drugiej odpowiedzi definiuje to dla wersji 4:

„4.4. [...] UUID w wersji 4 służy do generowania UUID z liczb prawdziwie losowych lub pseudolosowych. [...] Ustaw wszystkie inne bity na losowo (lub pseudolosowo) wybrane wartości.”

To prawie wszystko pozwala od losowego generatora xkcd http://xkcd.com/221/ do urządzenia sprzętowego wykorzystującego szum kwantowy. Względy bezpieczeństwa w RFC:

„6. Aplikacje rozproszone generujące UUID na różnych hostach muszą polegać na źródle liczb losowych na wszystkich hostach. Jeśli nie jest to wykonalne, należy zastosować wariant przestrzeni nazw.”

Przeczytałem to jako: Jesteś sam. Jesteś odpowiedzialny za swój losowy generator we własnej aplikacji, ale wszystko inne opiera się na zaufaniu. Jeśli nie ufasz własnej umiejętności prawidłowego zrozumienia wybranego losowego generatora i korzystania z niego, dobrym pomysłem jest sprawdzenie kolizji. Jeśli nie ufasz programatorowi innych procesów, sprawdź kolizje lub użyj innej wersji UUID.

Bezpieczne
źródło
11

Z pewnością powinieneś wykryć, czy nastąpi kolizja, a Twoja aplikacja powinna zgłosić wyjątek, jeśli tak się stanie. Np. Jeśli identyfikator UUID jest używany jako klucz podstawowy w bazie danych, wówczas baza danych powinna zgłosić błąd podczas wstawiania kolidującego identyfikatora.

Uważam jednak, że pisanie kodu do generowania nowego identyfikatora UUID w przypadku kolizji i ponownej próby marnowania czasu. Szansa na kolizję jest tak mała, że ​​rzucenie wyjątku byłoby całkowicie rozsądnym sposobem na poradzenie sobie z tym.

Pamiętaj, że pisanie kodu to nie tylko strata własnego czasu, ale także komplikuje kod, utrudniając odczytanie kolejnej osobie, prawie bez żadnego zysku.

Pete
źródło
2
Twój UUID jest tak dobry, jak Twój generator losowy. Przy bardzo ( bardzo ) złym stanie się nie tylko kolizje, ale i nieuniknione. To powiedziawszy, być może sprawdzanie duplikatów w czasie generacji byłoby rzeczywiście przesadą, ale spodziewanie się, że sytuacja może się zdarzyć, i moim zdaniem nie tyle o co prosić. W niektórych domenach (na przykład opieka zdrowotna) uważam, że konieczne jest posiadanie kodu, który wychwytuje takie sytuacje (być może jako wykrywanie kolizji w bazie danych). byłbyś zaskoczony, ile czasu spędziłem na debugowaniu sytuacji, które nigdy się nie zdarzają.
Newtopian
1
Myślę, że nie wyraziłem się jasno. Zaktualizowałem odpowiedź, aby była bardziej jednoznaczna.
Pete,
7

To jest bardzo dobre pytanie. Nie sądzę, by w pośpiechu rozważano stosowanie UUID wszędzie. Nie znalazłem żadnych solidnych badań.

Sugestia: stąpaj bardzo ostrożnie tutaj i dobrze poznaj swoją kryptografię. Jeśli używasz 128-bitowego UUID, „efekt urodzinowy” mówi nam, że kolizja jest prawdopodobna po wygenerowaniu około 2 ^ 64 kluczy, pod warunkiem, że masz 128 bitów entropii w każdym kluczu .

Właściwie raczej trudno jest to zapewnić. Prawdziwą przypadkowość można wygenerować na podstawie (a) rozpadu promieniotwórczego (b) losowego szumu radiowego tła, często zanieczyszczonego, chyba że jesteś ostrożny (c) odpowiednio dobranego szumu elektronicznego, np. Pobranego z diody Zenera z uprzedzeniem wstecznym. (Grałem z ostatnim i działa jak urok, BTW).

Nie ufałbym takim stwierdzeniom, jak „Nie widziałem tego od roku użytkowania”, chyba że użytkownik wygenerował coś zbliżającego się do 2 ^ 64 (tj. Około 10 ^ 19) kluczy i nie sprawdziłby ich wszystkich względem siebie, a ćwiczenie nietrywialne.

Problem jest taki. Załóżmy, że masz tylko 100 bitów entropii, gdy porównujesz klucze ze wszystkimi innymi kluczami, które wszyscy inni generują we wspólnej przestrzeni klawiszy. Zaczniesz widzieć kolizje za około 2 ^ 50 tj. około 10 ^ 15 kluczy. Twoje szanse na kolizję, jeśli zapełnisz bazę danych zaledwie 1000 miliardami kluczy, są nadal znikome. A jeśli nie sprawdzisz, później otrzymasz nieoczekiwane błędy, które wkradną się do bazy danych wielkości wiersza peta. To może mocno ugryźć.

Sam fakt, że istnieje wiele podejść do generowania takich UUID, powinien wywołać chwilowy przypływ niepokoju. Kiedy zdasz sobie sprawę, że niewiele generatorów używa „prawdziwie losowych” procesów z wystarczającą entropią dla UUID typu 4, powinieneś być nadmiernie zaniepokojony, chyba że dokładnie zbadałeś zawartość entropii w generatorze. (Większość ludzi tego nie zrobi, a nawet wie, jak to zrobić; możesz zacząć od pakietu DieHarder). NIE mylić generowania liczb pseudolosowych z prawdziwym generowaniem liczb losowych.

Ważne jest, abyś zdał sobie sprawę, że entropia, którą wprowadziłeś, jest entropią, którą masz, a po prostu zaburzenie klucza przez zastosowanie funkcji kryptograficznej nie zmienia entropii. Może nie być intuicyjnie oczywiste, że jeśli cała moja przestrzeń zawiera cyfry 0 i 1, zawartość entropii jest taka sama jak następujących dwóch ciągów, pod warunkiem, że są to jedyne dwie opcje: „To naprawdę bardzo złożony ciąg 293290729382832 * ! @@ # & ^% $$) ,. m} ”i„ A TERAZ DLA COŚ ZUPEŁNIE INNEGO ”. Nadal są tylko dwie opcje.

Losowość jest trudna do poprawienia, a samo przekonanie, że „eksperci to obejrzeli, dlatego jest w porządku” może nie wystarczyć. Doświadczeni kryptografowie (a niewielu z nich jest naprawdę biegłych) jako pierwsi przyznają, że często mylą się. Zaufaliśmy heartbleed, DigiNotar itp.

Myślę, że Paul Tomblin zachowuje odpowiednią ostrożność. Mój 2c.

użytkownik199506
źródło
6

Problem polega na tym, że jeśli używasz „Generatora liczb losowych” i nie wiesz, jak losowy jest ten generator, prawdopodobieństwo kolizji jest w rzeczywistości nieznane. Jeśli generatory liczb losowych są w jakiś sposób skorelowane, prawdopodobieństwo kolizji może dramatycznie wzrosnąć - być może wiele, wiele rzędów lub wielkości.

Nawet jeśli masz bardzo małe prawdopodobieństwo kolizji, masz zasadniczy problem: prawdopodobieństwo NIE wynosi 0. Oznacza to, że kolizja W końcu nastąpi, po prostu nie będą występować zbyt często.

Im częściej generujesz i używasz UUID, tym szybciej może wystąpić kolizja. (generowanie 1 rocznie oznacza dłuższy czas oczekiwania niż generowanie miliona na sekundę, przy czym wszystkie inne rzeczy są równe).

Jeśli prawdopodobieństwo jest skończone, nieznane i używasz wielu identyfikatorów UUID, musisz rozważyć konsekwencje kolizji. Jeśli nie można zaakceptować wyjątku i zamknąć aplikacji biznesowej, nie rób tego! (Przykłady z czubka mojej głowy: „Można zamknąć serwer sieciowy w trakcie aktualizowania biblioteki, to się nie zdarza często” i „Można zamknąć system płac w środku wykonywanie wypłaty ". Te decyzje mogą być ruchami ograniczającymi karierę.)

Możesz mieć gorszy przypadek, znowu w zależności od aplikacji. Jeśli przeprowadzasz test na obecność identyfikatora UUID (tj. Wyszukujesz), a następnie tworzysz nowy, jeśli jeszcze go nie ma - co jest dość powszechną rzeczą do zrobienia - może się okazać, że łączysz rekordy lub tworzysz relacje , gdy w rzeczywistości podłączasz 2 rzeczy za pomocą UUID, których nie należy podłączać. Jest to coś, w którym zgłoszenie wyjątku niczego nie rozwiąże, a utworzysz gdzieś niewykrywalny bałagan. Jest to coś, co prowadzi do wycieku informacji i może być bardzo krępujące. (np .: Zaloguj się do swojego banku i sprawdź, czy saldo konta kogoś innego! Źle!)

Podsumowanie: należy wziąć pod uwagę sposób użycia identyfikatorów UUID i konsekwencje kolizji. Określa, czy powinieneś uważać na wykrywanie i unikanie kolizji, podejmować proste działania w przypadku kolizji, czy nic nie robić. Proste, pojedyncze, uniwersalne rozwiązanie może w niektórych okolicznościach być nieodpowiednie.

szybko
źródło
2
„Prawdopodobieństwo (kolizji) NIE wynosi 0”. Każda sekwencja o skończonej długości ma tę właściwość. Nawet przy całkowicie losowym UUID v4, po wygenerowaniu 2 ^ 122 unikalnych UUID (128 bitów minus wersja 4-bitowa minus 2 zarezerwowane bity), kolejna generowana przez Ciebie karta gwarantuje kolizję. Najprawdopodobniej uderzyłbyś w kolizję wcześniej. Większe pytanie dotyczy tego, czy kolizja po czymś takim jak powtórzenia 5e36 stanowi problem i na które nie można udzielić ogólnej odpowiedzi (choć oczywiście można odpowiedzieć w każdym konkretnym przypadku), jak powiedziano w podsumowaniu.
CVn
Oczywiście. Było to stwierdzenie oczywistości (ale wciąż się powtarza). Problemem jest to, ile korelacji mają generatory liczb losowych. Może to znacznie zwiększyć prawdopodobieństwo kolizji (2 ^ duże), ale ile to jest czegoś, czego nie będziesz wiedział, chyba że wykonasz dużo kopania, badań lub obliczeń. Zakładając, że prawdopodobieństwo zderzenia jest znacznie gorsze, niż najlepsza wartość jest prawdopodobnie rozsądna. Potem ... musisz rozważyć konsekwencje.
szybko_now
0

W grę wchodzą dwa problemy:

  1. Jakość używanych generatorów liczb losowych.

  2. Ilość UUID, które mogą zostać wygenerowane.

„Losowy” UUID ma 122 losowe bity. Zakładając idealną losowość, możesz oczekiwać pierwszej kolizji przy około 2 ^ 61 wygenerowanych UUID (to pierwiastek kwadratowy z 2 ^ 122). Jeśli wszyscy na Ziemi mieliby generować UUID na sekundę, to 10 000 000 000 * 365 * 24 * 60 * 60 = 315360000000000000 UUID rocznie, co jest dość bliskie 2 ^ 58. Oznacza to, że po kilku latach dostaniesz pierwsze kolizje. O ile twoja aplikacja nie zbliży się do tych liczb, możesz być całkiem pewien, że nie dostaniesz kolizji, jeśli twój losowy generator ma przyzwoitą jakość.

Mówiąc o generatorze liczb losowych: Jeśli korzystasz ze standardowych generatorów bibliotek C (bezpośrednio, pośrednio lub podobnych), prawdopodobnie zaszczepiając je czasem, jesteś zrujnowany. Nie mogą one korzystać z wystarczającej entropii, aby uniknąć kolizji. Jeśli jednak korzystasz z systemu Linux, po prostu odczytaj 16 bajtów danych z /dev/urandom: Rysuje to pulę entropii, która jest mieszana przez jądro, które ma dostęp do niektórych rzeczywistych zdarzeń losowych. Chyba że zwykle generujesz UUID naprawdę, naprawdę na początku sekwencji rozruchowej, /dev/urandompowinien zachowywać się jak prawdziwe losowe źródło.

cmaster
źródło
-1

Raz go przetestowałem, używając dość prostego programu (brutalna siła), który wygenerował 10 milionów UUID-ów i nie spotkałem kolizji.

UUID RFC mówi, że UUID nie jest tylko kilka (pseudo) losowych liczb.

xea
źródło
1
W wersji 4, o którą pytam, właściwie jest kilka losowych liczb, z wyjątkiem 6 bitów, które będą dokładnie takie same we wszystkich.
Paul Tomblin
8
10 milionów nie jest nawet kroplą w koszyku. Istnieje tylko 1 na 3E30 szansa na kolizję. Jeśli znalazłeś taki, radziłbym ci wybiegać i kupić bilet w każdej loterii, jaką możesz!
Ross Patterson
@RossPatterson, zastanawiałem się konkretnie nad tym, czy masz kilkaset komputerów wykorzystujących dokładnie ten sam algorytm losowo-losowy na tym samym sprzęcie, co znacznie zwiększa prawdopodobieństwo kolizji. Podejrzewam, że tak.
Paul Tomblin
1
@Paul - pomyślałem, że tylko w przypadku niewystarczającej entropii w początkowym procesie wysiewu - na przykład, jeśli ziarno jest generowane tylko z pory dnia, a wszystkie maszyny uruchomiły się bardzo blisko tej samej chwili. Bardzo wątpię, aby wysiew był tak słaby - możliwe jest nawet, że używane są sprzętowe numery seryjne, co oczywiście byłoby unikalne dla każdej maszyny.
Steve314,
1
Niestety, siew może być bardzo słaby. Systemy Linux lubią wysyłać PRNG z bardzo losowych źródeł (aktywność sterowników urządzeń itp. ), Ale w innych środowiskach standardem jest używanie aktualnego znacznika czasu, który przy wystarczającej liczbie maszyn w ścisłej synchronizacji czasu może stanowić problem.
Ross Patterson