Насколько случайным является System.Guid.NewGuid ()? (Возьми два)

Question

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

Я не знаю, как .NET генерирует свои GUID, вероятно, только Microsoft, но есть большая вероятность, что он просто вызывает CoCreateGuid () . Эта функция, однако, задокументирована для вызова UuidCreate () . А алгоритмы для создания UUID довольно хорошо документированы .

Короче говоря, как бы то ни было, кажется, что System.Guid.NewGuid() действительно использует алгоритм генерации UUID версии 4 * , потому что все генерируемые им GUID соответствуют критериям (посмотрите сами, я пробовал пару миллионов GUID, все они совпадают).

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

Затем возникает вопрос: насколько случайным является IS таким случайным? Как знает каждый хороший маленький программист, алгоритм псевдослучайных чисел является настолько же случайным, как и его начальное число (он же энтропия). Так что же за семя UuidCreate()? Как часто PRNG повторно посеян? Является ли он криптографически стойким, или я могу ожидать, что одни и те же GUID начнут выливаться, если два компьютера случайно вызовут System.Guid.NewGuid() одновременно? И можно ли угадать состояние PRNG, если собрано достаточно много последовательно сгенерированных GUID?

Добавлено: Чтобы уточнить, я хотел бы выяснить, насколько случайным я могу верить этому и, следовательно, - где я могу его использовать. Итак, давайте установим приблизительную шкалу «случайности» здесь:

1. Базовая случайность, принимая текущее время в качестве начального числа. Используется для перетасовки карт в пасьянсе, но мало что из-за того, что столкновения слишком легко обнаружить, даже не пытаясь.
2. Более продвинутая случайность, использующая не только время, но и другие машинно-специфические факторы для семян. Возможно также посеял только один раз при запуске системы. Это может быть использовано для генерации идентификаторов в БД, поскольку дублирование маловероятно. Тем не менее, это не хорошо для безопасности, потому что результаты могут быть предсказаны с достаточными усилиями.
3. Криптографически случайный, с использованием шума устройства или других расширенных источников случайности для семян. Повторно сеять при каждом вызове или, по крайней мере, довольно часто. Может использоваться для идентификаторов сеансов, раздачи ненадежным сторонам и т. Д.

Я пришел к этому вопросу, подумав, можно ли использовать их в качестве идентификаторов БД и будет ли ошибочной реализация алгоритма Guid.comb вместе с System.Guid.NewGuid() (как это делает NHibernate) или нет.

Answer 1

Ответ таков: вам не нужно это знать. Как указано в принятом ответе на связанный вопрос :

GUID не дает гарантий относительно случайности, он дает гарантии вокруг уникальности.

Еще более сильное утверждение о безопасности и случайности сделано в RFC4122 , в котором указан формат UUID:

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

Все остальное является деталью реализации (и может быть предметом изменения).

Особенности Windows

Часто люди утверждают, что поведение в Windows задокументировано, и поэтому гарантируется, что GUID являются криптографически безопасными.

Архив в настоящее время [MS-SECO] Обзор безопасности Windows Документ упоминается в Приложении A:

Хотя только небольшое меньшинство GUID версии 4 требует криптографическая случайность, получены случайные биты для всех GUID версии 4, встроенных в Windows через криптографический API Windows CryptGenRandom или аналогичный, тот же источник, который используется для генерации криптографических ключей.

Кроме того, в разделе 2.5.5 того же документа явно упоминается использование значений «секретного GUID» в качестве одноразового номера или аутентификатора.

НО: эта часть документации о поведении продукта не является спецификацией, на которой вы обычно основываете безопасность своего продукта (в частности, в контексте .NET).

На самом деле, вышеупомянутый документ описывает подробности реализации конкретного продукта . Даже если текущие реализации Windows и .NET Framework 4.x выдают действительно случайные значения UUID версии 4 в Windows, нет гарантии, что System.Guid.NewGuid сделает это в будущем или на других платформах .NET (например, Mono, Silverlight, CF). .NET Core и т. Д.).

Как пример, алгоритм UUID, используемый в более ранних версиях .NET Core , зависит от платформы , и вы можете получить UUID версии 1 (для BSD).

Answer 2

Некоторые люди уже намекали на это, но я хочу повторить это, так как там, кажется, ошибочное мнение:

Случайность и уникальность являются ортогональными понятиями.

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

GUID были разработаны, чтобы быть уникальными, а не случайными. Если .NET-генератор использует случайный ввод, хорошо. Но не полагайтесь на него как на источник случайности ни в криптографических, ни в каких-либо других целях (в частности, какую функцию распределения вы ожидаете получить?). С другой стороны, вы можете быть достаточно уверены, что GUID, созданные в .NET, даже в больших объемах, будут уникальными.

Answer 3

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

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

public Guid CreateCryptographicallyStrongGuid() {
    var rng = new System.Security.Cryptography.RNGCryptoServiceProvider();
    var data = new byte[16];
    rng.GetBytes(data);
    return new Guid(data);
}

Эти GUID являются просто 128 битами криптографической случайности. Они не структурированы и не будут сталкиваться.

См. эту статью для некоторых из математики. Используя «Общую формулу дня рождения», перестановка дает

n = sqrt (-2T * ln (p))

где n - количество выбранных элементов, T - общее количество элементов (2 ^ 128), а p - целевая вероятность того, что все n выбранные элементы будут отличаться. При p = 0,99 это дает * n = 2,61532104 * 10 ^ 18 *. Это означает, что мы можем генерировать миллиард действительно случайных идентификаторов GUID в секунду в системе в течение миллиарда секунд (32 года), и в конце мы получим более 99% вероятности того, что каждый из них уникален в системе.

Answer 4

Определение рандома никоим образом не относится к определению глобально уникального.

Двойное подбрасывание монеты и получение HH, HT, TH, TT - все они случайные. HH так же случайно, как HT.

Дважды подбросив «специальную» монету и гарантируя, что вы получите только HT или TH, уникальность.

Answer 5

Согласно https://msdn.microsoft.com/en-us/library/bb417a2c-7a58-404f-84dd-6b494ecf0d13#id11, с момента выпуска Windows 2000 в 1999 году,

"получены случайные биты для всех GUID версии 4, встроенных в Windows через криптографический API Windows CryptGenRandom или аналогичный, тот же источник, который используется для генерации криптографических ключей "

Так что я бы посчитал их криптографически безопасными - по крайней мере, в той степени, в которой они обеспечивают 122 бита энтропии.

Также см. https://stackoverflow.com/a/35384818/284704,, где Уилл Дин на шаге отладки подтвердил, что CLR вызывает надлежащий безопасный генератор случайных ОС.

Answer 6

GUID разработаны для того, чтобы быть под номером 2 в вашей шкале, то есть "могут использоваться для генерации идентификаторов в БД, поскольку дубликаты маловероятны *."

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

На практике, согласно этому комментарию и этому , генерация GUID реализована в терминах криптографически безопасного ГСЧ (* 1012) *). Но это кажется недокументированной деталью реализации. (И я не проверял это - это случайные комментарии в Интернете, возьмите с собой кучу соли).

(* Где "вряд ли" означает что-то вроде "шансы любого найти дубликат GUID до конца вселенной меньше, чем шансы, что вы лично выиграете в лотерею." Ошибки реализации исключены, конечно.)

Answer 7

Сосредоточив внимание на вашем вопросе , используя GUID в качестве идентификаторов строк :

GUID предназначены для баз данных, ориентированных на репликацию или заранее генерирующих строки перед их добавлением в БД. Если вам не нужны GUID для решения конкретной проблемы, попробуйте придерживаться пошаговой нумерации. GUID немного усложняет отладку и тестирование.

Метод COMB в упомянутой статье кажется довольно хорошим. Я так и не понял, спасибо за это! ( p.s. Версия этой статьи для печати читается намного лучше )

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

Также взгляните на Джефф на ID против GUID

create table #temp ([id] uniqueidentifier primary key default(newid()), [name] varchar(20))
insert into #temp (name) values ('apple')
insert into #temp (name) values ('orange')
insert into #temp (name) values ('banana')
select * from #temp
drop table #temp

id                                   name
------------------------------------ --------------------
911B0CBD-4EED-4EB0-8488-1B2CDD915C02 banana
56CF3A80-A2DE-4949-9C9B-5F890824EA9C orange
5990B9FD-143D-41B0-89D1-957B2C57AB94 apple

Answer 8

Я где-то читал, что шансы на выигрыш в лотерее будут эквивалентны 2 4-байтовым "GUID", сталкивающимся. Стандартные 16-байтовые GUID предлагают гораздо меньше шансов на столкновение.

Answer 9

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