UUID столкновения [закрыто]

33

Кто-нибудь проводил какие-либо реальные исследования вероятности коллизий UUID, особенно с UUID версии 4 (случайных), учитывая, что генераторы случайных чисел, которые мы используем, не являются действительно случайными и что у нас могут быть десятки или сотни идентичных машин, работающих с одним и тем же кодом генерировать UUID?

Мои коллеги считают, что тестирование на коллизию UUID - это пустая трата времени, но я всегда добавляю код, чтобы перехватить исключение дублирующегося ключа из базы данных, и попробуйте снова с новым UUID. Но это не решит проблему, если UUID происходит из другого процесса и ссылается на реальный объект.

Пол Томблин
источник
4
На вопрос о переполнении стека уже был дан ответ: stackoverflow.com/questions/3038023/… , как показывает основной поиск Google: google.com/search?q=uuid+collision
Арсений Мурзенко
3
Этот вопрос касается конкретных алгоритмов, используемых в SQL * Server, который совершенно определенно НЕ является версией 4 (случайной). Я спрашиваю о версии 4 специально.
Пол Томблин
Вы говорите, что реализация NEWID()функции SQL Server не случайна? Если да, есть ли у вас источники, подтверждающие такое заявление? Его вывод явно выглядит как v4 UUIDs для меня. NEWSEQUENTIALID()определенно не совсем случайный, но это его цель : генерировать UUID, которые хорошо работают (а также, по крайней мере, UUID), в качестве ключей индекса.
CVN
1
Я собираюсь ответить на связанный вопрос, в котором говорится, что NEWID () содержит некоторые биты MAC-адреса, что делает его UUID V1 или V2, а не V4.
Пол Томблин
2
Этот вопрос, кажется, не по теме, потому что он о чем-то уже обсуждавшемся до тошноты в Интернете, в книгах и особенно в StackOverflow

Ответы:

18

В Википедии есть некоторые детали:

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

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

Но вероятность имеет место, только если биты совершенно случайны. Однако RFC http://tools.ietf.org/html/rfc4122#page-14, указанный в другом ответе, определяет это для версии 4:

«4.4. [...] UUID версии 4 предназначен для генерации UUID из действительно случайных или псевдослучайных чисел. [...] Установите все остальные биты в случайно (или псевдослучайно) выбранные значения».

Это в значительной степени позволяет все, от генератора случайных чисел xkcd http://xkcd.com/221/ до аппаратного устройства, использующего квантовый шум Соображения безопасности в RFC:

«6. Распределенные приложения, генерирующие UUID на разных хостах, должны быть готовы полагаться на источник случайных чисел на всех хостах. Если это невозможно, следует использовать вариант пространства имен».

Я читаю это как: Ты сам по себе. Вы несете ответственность за генератор случайных чисел в своем собственном приложении, но это и все остальное основано на доверии. Если вы не доверяете своей способности правильно понимать и использовать генератор случайных чисел по вашему выбору, то это действительно хорошая идея, чтобы проверить наличие столкновений. Если вы не доверяете программисту других процессов, проверьте наличие коллизий или используйте другую версию UUID.

Безопасный
источник
11

Вы обязательно должны определить, произошло ли столкновение, и ваше приложение должно выдать исключение, если оно произойдет. Например, если UUID используется в качестве первичного ключа в базе данных, база данных должна выдать ошибку при вставке идентификатора коллизии.

Тем не менее, я считаю, что написание кода для генерации нового UUID в случае коллизии и повторной попытки будет пустой тратой времени. Вероятность столкновения настолько мала, что исключение будет вполне разумным способом решения этой проблемы.

Помните, что это не только напрасная трата вашего собственного времени на написание кода, но также делает код более сложным, затрудняя чтение для следующего человека, почти не принося никакой пользы.

Пит
источник
2
ваш UUID хорош только как ваш генератор случайных чисел. При очень ( очень ) плохом столкновении не только произойдет, но и неизбежно. Тем не менее, возможно, проверка на наличие дубликатов во время генерации будет излишней, но ожидать, что ситуация может возникнуть, и, на мой взгляд, не так много, чтобы просить. В некоторой области (например, здравоохранение) я думаю, что необходимо иметь код, который улавливает такие ситуации (например, обнаружение столкновений в базе данных). Вы будете удивлены, сколько времени я потратил на отладку ситуаций, которые никогда не происходят.
Newtopian
1
Я думаю, что я не прояснил себя. Я обновил ответ, чтобы быть более явным.
Пит
7

Это очень хороший вопрос. Я не верю, что в спешке адекватно рассматривалось использование UUID везде. Я не нашел никаких серьезных исследований.

Совет: очень осторожно действуйте здесь и хорошо разбирайтесь в своей криптографии. Если вы используете 128-битный UUID, «эффект дня рождения» говорит нам, что коллизия вероятна после того, как вы сгенерировали около 2 ^ 64 ключей, при условии, что у вас есть 128 битов энтропии в каждом ключе .

На самом деле довольно сложно убедиться, что это так. Истинная случайность может быть получена из (а) радиоактивного распада (б) случайного фонового радиошума, часто загрязненного, если вы не будете осторожны (в) надлежащим образом выбранного электронного шума, например, взятого из обратного смещения стабилитрона. (Я играл с последним, и это работает как шарм, кстати).

Я бы не стал доверять таким высказываниям, как «Я не видел этого за год использования», если бы пользователь не сгенерировал что-то, приближающееся к 2 ^ 64 (т.е. около 10 ^ 19) клавишам, и не проверил их все друг против друга, а нетривиальное упражнение.

Проблема в этом. Допустим, у вас есть всего 100 бит энтропии, когда вы сравниваете свои ключи со всеми остальными ключами, которые все остальные генерируют в общем пространстве ключей. Вы начнете видеть столкновения примерно через 2 ^ 50 т.е. около 10 ^ 15 ключей. Ваши шансы увидеть коллизию, если вы заполнили базу данных только 1000 миллиардами ключей, все еще незначительны. И если вы не проверите, то позже вы получите неожиданные ошибки, которые появляются в вашей базе данных размером с пета-строку. Это может сильно укусить.

Тот факт, что существует множество подходов к генерации таких UUID, должен вызвать кратковременное беспокойство. Когда вы поймете, что немногие генераторы используют «действительно случайные» процессы с достаточной энтропией для UUID типа 4, вы должны быть чрезмерно обеспокоены, если вы не тщательно изучите энтропийное содержание генератора. (Большинство людей не будут этого делать или даже не знают, как это сделать; вы можете начать с комплекта DieHarder). НЕ путайте генерацию псевдослучайных чисел с генерацией истинных случайных чисел.

Очень важно, чтобы вы осознали, что энтропия, которую вы вводите, - это ваша энтропия, и простое возмущение ключа с помощью криптографической функции не изменяет энтропию. Интуитивно не очевидно, что, если все мое пространство содержит цифры 0 и 1, содержание энтропии такое же, как и в следующих двух строках, при условии, что они являются единственными двумя вариантами: «Это действительно очень сложная строка 293290729382832 * ! @@ # & ^% $$),. m} "и" И СЕЙЧАС ДЛЯ ЧЕГО-ТО РАЗЛИЧНОГО ". Есть еще только два варианта.

Случайность сложно понять правильно, и просто полагать, что «эксперты смотрели на это, поэтому все в порядке» может быть недостаточно. Опытные криптографы (а таких действительно мало кто умеет) первыми признают, что часто ошибаются. Нам доверяли Heartbleed, DigiNotar и др.

Я думаю, что Пол Томблин проявляет соответствующую осторожность. Мой 2с.

user199506
источник
6

Проблема в том, что если вы используете «Генератор случайных чисел» и не знаете, насколько случайным является этот генератор, тогда вероятность столкновения на самом деле неизвестна. Если генераторы случайных чисел каким-либо образом коррелируют, вероятность столкновения может резко возрасти - возможно, на много, много порядков или величин.

Даже если у вас очень маленькая вероятность столкновения, у вас есть фундаментальная проблема: вероятность НЕ равна 0. Это означает, что столкновение в конечном итоге произойдет, просто оно не будет происходить очень часто.

Чем чаще вы генерируете и используете UUID, тем скорее всего будет видно столкновение. (генерирование 1 в год означает более длительное время ожидания, чем генерирование миллиона в секунду, при прочих равных условиях).

Если эта вероятность конечна, неизвестна и вы используете много UUID, то вам необходимо учитывать последствия столкновения. Если недопустимо создавать исключение и закрывать бизнес-приложение, не делайте этого! (Примеры из головы: «Это нормально, чтобы выключить веб-сервер во время обновления проверки библиотеки ... это случается не часто» и «Это нормально, чтобы выключить систему начисления заработной платы в середине делать заработок ". Эти решения могут быть карьерные ограничения.)

У вас может быть и худший случай, опять же, в зависимости от вашего приложения. Если вы проверяете наличие UUID (т. Е. Делаете поиск), а затем делаете новый, если его еще нет - что достаточно распространено, - вы можете обнаружить, что связываете записи или создаете отношения , когда на самом деле вы подключаете 2 вещи через UUID, которые не должны подключаться. Это то, где создание исключения ничего не решит, и у вас где-то будет создан необнаружимый беспорядок. Это такая вещь, которая приводит к утечке информации и может быть очень неловко. (напр .: войдите в свой банк и обнаружите, что вы можете увидеть остаток на счете другого пользователя! Плохо!)

Резюме: вам нужно рассмотреть способ использования ваших UUID и последствия коллизии. Это определяет, следует ли вам позаботиться об обнаружении и предотвращении столкновений, предпринять некоторые простые действия в случае столкновения или ничего не делать. Простое, универсальное, универсальное решение в некоторых случаях может оказаться неуместным.

quickly_now
источник
2
«Вероятность (коллизии) НЕ равна 0». Любая последовательность конечной длины обладает этим свойством. Даже с совершенно случайным UUID v4, после того как вы сгенерировали 2 ^ 122 уникальных UUID (128 бит минус 4 бита версия минус 2 зарезервированных бита), следующий генерируемый вами будет гарантированно коллизионным. Скорее всего, вы столкнетесь с столкновением раньше, чем это. Более серьезный вопрос заключается в том, является ли столкновение после чего-то вроде 5e36 повторений проблемой, и на него нельзя ответить вообще (хотя, очевидно, можно ответить в каждом конкретном случае), как вы говорите в резюме.
CVn
Конечно. Это было утверждением очевидного (но все еще повторяется). Вопрос в том, сколько корреляции имеют генераторы случайных чисел. Это может значительно увеличить вероятность столкновения (2 ^ большое), но сколько это будет, вы не узнаете, если не будете много копать, исследовать или вычислять. Предполагая, что вероятность столкновения значительно хуже, чем наилучшее значение, вероятно, разумно. После этого ... вам нужно учитывать последствия.
quick_now
0

Есть две проблемы:

  1. Качество генераторов случайных чисел, которые используются.

  2. Количество UUID, которые могут быть сгенерированы.

«Случайный» UUID имеет 122 случайных бита. Предполагая идеальную случайность, вы можете ожидать, что первое столкновение будет около 2 ^ 61 сгенерированных UUID (это квадратный корень из 2 ^ 122). Если бы каждый на этой земле генерировал UUID в секунду, то это 10 000 000 000 * 365 * 24 * 60 * 60 = 315360000000000000 UUID в год, что довольно близко к 2 ^ 58. То есть через несколько лет вы получите первые столкновения. Если ваше приложение не приблизится к этим числам, вы можете быть уверены, что не получите столкновения, если ваш генератор случайных чисел будет достойного качества.

Говоря о генераторе случайных чисел: если вы используете стандартные генераторы библиотек C (напрямую, косвенно или аналогичные генераторы), возможно, заполняя их со временем, вы ошибаетесь. Они не могут привлечь достаточно энтропии, чтобы избежать столкновений. Однако, если вы работаете в Linux, просто прочитайте 16 байтов данных из /dev/urandom: Это использует пул энтропии, который перемешивается ядром, которое имеет доступ к некоторым реальным случайным событиям. Если вы обычно не генерируете UUID действительно, очень рано в последовательности загрузки, /dev/urandomдолжны вести себя как настоящий случайный источник.

cmaster
источник
-1

Я однажды протестировал его с помощью довольно простой (грубой силы) программы, которая сгенерировала 10 миллионов UUID, и я не столкнулся с коллизиями.

UUID RFC говорит , что UUID не просто куча (псевдо) случайных чисел.

хеа
источник
1
Версия 4, о которой я спрашиваю, в значительной степени представляет собой набор случайных чисел, за исключением 6 битов, которые будут одинаковыми во всех них.
Пол Томблин
8
10 миллионов - это даже не капля в море. Существует только 1 в 3E30 шанс столкновения. Если бы вы нашли один, я бы посоветовал вам спешить и купить билет в каждой лотерее, которую вы можете!
Росс Паттерсон
@RossPatterson, что меня особенно интересовало, так это то, что если у вас есть несколько сотен компьютеров, использующих один и тот же псевдослучайный алгоритм на одном и том же оборудовании, это значительно увеличивает вероятность столкновения. Я подозреваю, что это будет.
Пол Томблин
1
@Paul - я бы подумал только в том случае, если в начальном процессе посева недостаточно энтропии - например, если семя генерируется только из времени суток, и все ваши машины запускались очень близко к одному и тому же моменту. Я очень сомневаюсь, что засевание настолько слабое - даже возможно, что используются аппаратные серийные номера, которые, конечно, будут уникальными для каждой машины.
Steve314
1
Увы, посев может быть очень слабым. Системы Linux любят посылать PRNG из очень случайных источников (активность драйверов устройств и т. Д. ), Но в других средах стандартом является использование текущей метки времени, что может быть проблемой при достаточном количестве машин в режиме синхронизации по времени.
Росс Паттерсон