Udostępnij za pośrednictwem

Руководство по GUID. Часть 3

  • Artykuł

Давайте напомним, о чем шла речь: GUID – это 128-разрядное целое, который используется в качестве глобального уникального идентификатора. Система генерации GUID не является безопасной; при наличии злоумышленника, намеренно создающего коллизии, уникальность GUID не гарантируется; скорее GUID представляет собой простой и быстрый способ генерации идентификаторов без коллизий для взаимно доверенных участников. Один из механизмов, обеспечивающих глобальную уникальность, заключается в генерации GUID, составные части которого уникально определяются местом и временем. Недостаток такого подхода в том, что по составным частям GUID очень легко получить информацию о компьютере, на котором данный GUID сгенерирован. Это естественно вызывает вопросы к приватности данных.

Чтобы решить эту проблему существует второй распространенный метод генерации GUID, который генерирует GUID случайным образом. Такой GUID содержат цифру 4 в первой позиции третьей секции.

Во-первых, о каких данных GUID идет речь? Мы только что сказали, что первая цифра третьей секции такого «случайного» GUID равна 4. В прошлый раз я не упомянул о том, что в четвертой секции GUID содержится дополнительная информация о версии; вы можете обратить внимание, что первое шестнадцатеричное число четвертой секции всегда содержит 8, 9, a или b. Так что 6 разрядов в GUID зарезервировано для версии, а остальные 122 разряда могут быть использованы случайным образом.

Во-вторых, почему мы считаем, что случайные данные смогут обеспечить уникальность? Результат бросания монетки является случайным, но его точно нельзя назвать уникальным! Все на что мы здесь рассчитываем – это вероятная уникальность. Бросание монетки не дает уникального результата, но бросание монетки 122 раза подряд почти наверняка дает последовательность орлов и решек, которые никогда ранее не выпадали и которые наверняка не выпадут в будущем.

Давайте обсудим эти вероятности подробнее. Предположим, мы получили случайно сгенерированный GUID. Какова вероятность того, что генерация другого GUID когда-либо приведет к коллизии с данным конкретным значением? Очевидно, что при случайном и равномерном распределении вероятность коллизии составляет 2-122. А какова будет вероятность коллизии с данным GUID при генерации серии из n GUID? Поскольку эти события независимы, то вероятности складываются (*), и вероятность коллизии будет составлять n, деленное на 2122. 2122 является невероятно большим числом.

В мире существует порядка 230 персональных компьютеров (не считая, конечно карманных устройств или других устройств с соизмеримой вычислительной мощностью, но давайте их проигнорируем). Давайте предположим, что мы заставим все компьютеры мира генерировать GUID; если каждый из них способен генерировать, скажем, 220 GUID в секунду, тогда где-то через 272 секунд (через сто пятьдесят триллионов лет) мы получимвысокую вероятность коллизии. И вероятность коллизии становится заметной лишь через тридцать триллионов лет.

Но это, если речь идет о коллизии с одним конкретным GUID. Очевидно, что значительно больше шансов возникновения коллизиигде-то по мере генерации новых GUID-ов. Вспомните, что пару лет назад я анализировал вероятность коллизии при генерации случайного 32-разрядного числа; как выяснилось, вероятность коллизии стремительно возрастает примерно после 216генераций. Это обобщенное правило, которое заключается в том, что вероятность возникновения коллизии при генерации случайного n-разрядного числа возрастает при генерации 2n/2 значений. Так что если мы будем использовать миллиард персональных компьютеров для генерации GUID со 122 случайными разрядами, то коллизия, скорее всего произойдет при генерации 261 экземпляров. А поскольку мы предполагаем, что 230 компьютеров будут генерировать 220 GUID в секунду, то ожидаемая коллизия произойдет где-то через 211 секунд, т.е. примерно через час.

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

Но, конечно же, мы не собираемся этого делать. Количество GUID, генерируемых на нашей планете даже и близко не равняется 250! Я очень удивлюсь, если в мире генерируется хотя бы 220 GUID в секунду, а это значит, что для возникновения коллизии нам потребуется 241 секунд, что составляет около семидесяти тысяч лет. А если мы рассматриваем коллизию конкретного GUID и учтем значительно меньшее количество генерируемых в мире GUID, то на это потребуется в миллиард раз больше времени, по сравнению с исходной оценкой.

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

Так что эти шансы весьма малы.

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

  • Какой источник энтропии используется в качестве исходного значения для этого псевдослучайного генератора?
  • Какой размер данных берется из этого источника?
  • При запуске двух виртуальных машин на одном физическом компьютере, используют ли они один общий источник энтропии?
  • Основываются ли данные из этих источников на идентификаторе компьютера (таком как MAC-адрес) или на человеке, создающем GUID?
  • Точно зная алгоритм генерации GUID и имея конкретный GUID, возможно ли вычислить значение, используемое в качестве начального для генерации?
  • При наличии двух GUID, возможно ли вычислить тот факт, что они оба сгенерированы на основе одного значения энтропии? (И, таким образом, вероятно на одном компьютере.)

Я не знаю ответов на все эти вопросы, потому будет разумным предположить, что ответом на последние четыре вопроса будет «да». Очевидно, что по экземпляру случайного GUID будет значительно сложнее определить, кто и где его создал, по сравнению с версией, рассмотренной в прошлый раз, когда информация об этом явно зашивается в сам GUID. Но я не думаю, что это невозможно.

Существует еще один механизм генерации GUID. Если первое шестнадцатеричное число третьей секции равно 2, то это GUID 1-й версии, но временная метка, которого имеет немного другое значение. Если эта число равно 3 или 5, то данные получаются путем исполнения криптографической хэш-функции по уникальной строке; уникальность строки, при этом, основывается на уникальности URL. Но я не буду вдаваться в такие подробности.

Подведем итоги:

  • Генерируемые GUID должны быть уникальными, но не обязательно случайными. Не используйте их в качестве случайных значений.
  • GUID-ы, являющиеся случайными значениями, не обладают криптографической устойчивостью.
  • Уникальность GUID является кооперативной; если кто-то захочет использовать сгенерированное ранее значение GUID и получить, таким образом, коллизию, то никто не сможет этому помешать. Механизм генерации GUID не является безопасным.
  • GUID обладают внутренней структурой; как минимум шесть бит зарезервированы и обладают особым значением.
  • GUID могут генерироваться последовательно и обычно, так и происходит.
  • Только всё значение GUID является уникальным.
  • Существует множество разных алгоритмов генерации GUID.
  • Вероятность коллизии GUID, сгенерированных случайным образом, в обозримом будущем статистически очень мала.
  • GUID могут раскрывать информацию о времени и месте создания, либо напрямую (как в версии 1) или путем криптоанализа (в версии 4).
  • В будущем могут использоваться совершенно иные алгоритмы генерации.

(*) Как правильно заметили в комментариях, это приближение истинно только, если вероятность события мала и значение n относительно мало по сравнению с общим числом возможных комбинаций.

Оригинал статьи

Comments

  • Anonymous
    August 06, 2012
    и тут вылезли 2 ромба:) "рассмотре��ной" когда уже починят этот DynamicCompressionModule

  • Anonymous
    August 09, 2012
    Да, это сильно раздражает. А за статью спасибо, очень интересно.

  • Anonymous
    August 22, 2012
    И при чем здесь DynamicCompressionModule IIS-а к проблеме с кодировкой?

  • Anonymous
    September 04, 2012
    Перевод неверный. "Очевидно, что при случайном и равномерном распределении вероятность коллизии составляет 2 в степени 122". Должно быть "Очевидно, что при случайном и равномерном распределении вероятность коллизии составляет 1 деленное на 2 в степени 122"

  • Anonymous
    September 04, 2012
    Спасибо, Алексей! Вы правы.Исправлено.