Kolizje UUID [zamknięte]

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.

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.

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.

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.

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.

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.

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.