Насколько уникален UUID?
https://stackoverflow.com/questions/1155008
-
18-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Насколько безопасно использовать UUID для уникальной идентификации чего-либо (я использую его для файлов, загружаемых на сервер)?Насколько я понимаю, он основан на случайных числах.Однако мне кажется, что, если пройти достаточно времени, это в конечном итоге повторится, просто по чистой случайности.Есть ли лучшая система или какой-то шаблон для решения этой проблемы?
Решение
Очень безопасно:
Годовой риск того, что данный человек пострадал от метеорита, оценивается как один шанс в 17 миллиардах, что означает, что вероятность составляет около 0,00000000006 (6 × 10−11), эквивалентно шансов создать несколько десятков триллионов UUID за год и иметь один дубликат.Другими словами, только после создания 1 миллиарда UUID каждую секунду в течение следующих 100 лет вероятность создания только одного дубликата составила бы около 50%.
Предостережение:
Однако эти вероятности сохраняются только тогда, когда UUID генерируются с использованием достаточной энтропии.В противном случае вероятность дубликатов может быть значительно выше, поскольку статистическая дисперсия может быть ниже.Там, где уникальные идентификаторы требуются для распределенных приложений, так что UUID не сталкиваются, даже когда данные из многих устройств объединяются, случайность семян и генераторов, используемых на каждом устройстве, должна быть надежной в течение срока службы приложения.Там, где это невозможно, RFC4122 рекомендует вместо этого использовать вариант пространства имен.
Источник:А Случайная вероятность дубликатов UUID раздел статьи Википедии «Универсально уникальные идентификаторы» (ссылка ведет на редакцию от декабря 2016 года, прежде чем редактирование переработало раздел).
Также см. текущий раздел по той же теме в той же статье «Универсальный уникальный идентификатор», Столкновения.
Другие советы
Если под «достаточно времени» вы подразумеваете 100 лет и создаете их со скоростью миллиард в секунду, то да, у вас есть 50% вероятность столкновения через 100 лет.
Существует более одного типа UUID, поэтому «насколько безопасно» зависит от того, какой тип (который в спецификациях UUID называется «версией») вы используете.
Версия 1 — это UUID, основанный на времени и MAC-адресе.128-битный код содержит 48-битный MAC-адрес сетевой карты (который назначается производителем) и 60-битный тактовый сигнал с разрешением 100 наносекунд.Эти часы действие происходит в 3603 году нашей эры. поэтому эти UUID безопасны, по крайней мере, до тех пор (если вам не нужно более 10 миллионов новых UUID в секунду или если кто-то не клонирует вашу сетевую карту).Я говорю «по крайней мере», потому что отсчет начинается 15 октября 1582 года, так что у вас есть около 400 лет после того, как часы завершится, прежде чем появится хотя бы небольшая возможность дублирования.
Версия 4 — это UUID случайного числа.Здесь шесть фиксированных битов, а остальная часть UUID представляет собой 122-битную случайность.Видеть Википедия или другой анализ, описывающий, насколько маловероятен дубликат.
Версия 3 использует MD5, а версия 5 использует SHA-1 для создания этих 122 бит вместо генератора случайных или псевдослучайных чисел.Таким образом, с точки зрения безопасности это похоже на то, что версия 4 является статистической проблемой (пока вы уверены, что алгоритм дайджеста всегда уникален).
Версия 2 аналогична версии 1, но с меньшей тактовой частотой, поэтому она будет завершена гораздо быстрее.Но поскольку UUID версии 2 предназначены для DCE, вам не следует их использовать.
Так что для всех практических задач они безопасны.Если вам неудобно оставлять это на усмотрение вероятностей (например,вы из тех людей, которые беспокоятся о том, что Земля будет уничтожена большим астероидом при вашей жизни), просто убедитесь, что вы используете UUID версии 1, и он гарантированно будет уникальным (при вашей жизни, если вы не планируете жить после 3603 года нашей эры). ).
Так почему же все просто не используют UUID версии 1?Это связано с тем, что UUID версии 1 раскрывают MAC-адрес машины, на которой он был сгенерирован, и они могут быть предсказуемыми — две вещи, которые могут иметь последствия для безопасности приложения, использующего эти UUID.
Ответ на этот вопрос может во многом зависеть от версии UUID.
Многие генераторы UUID используют случайное число версии 4.Однако многие из них используют псевдогенератор случайных чисел для их генерации.
Если для генерации UUID используется плохо заполненный PRNG с небольшим периодом, я бы сказал, что это совсем не безопасно.
Следовательно, он настолько безопасен, насколько безопасны алгоритмы, используемые для его создания.
С другой стороны, если вы знаете ответы на эти вопросы, я думаю, что uuid версии 4 будет очень безопасным в использовании.На самом деле я использую его для идентификации блоков в файловой системе сетевых блоков, и до сих пор не было конфликтов.
В моем случае ГПСЧ, который я использую, представляет собой твистер Мерсенна, и я с осторожностью отношусь к тому, как он заполняется из нескольких источников, включая /dev/urandom.Смерч Мерсенна имеет период 2^19937 − 1.Пройдет очень-очень много времени, прежде чем я увижу повторяющийся uuid.
Цитата из Википедия:
Таким образом, любой может создать UUID и использовать его, чтобы идентифицировать что -то с разумной уверенностью, что идентификатор никогда не будет непреднамеренно использован кем -либо для чего -либо еще.
Далее довольно подробно объясняется, насколько это на самом деле безопасно.Итак, чтобы ответить на ваш вопрос:Да, это достаточно безопасно.
Схемы UUID обычно используют не только псевдослучайный элемент, но также текущее системное время и какой-то уникальный идентификатор оборудования, если он доступен, например сетевой MAC-адрес.
Весь смысл использования UUID заключается в том, что вы верите, что он предоставит уникальный идентификатор лучше, чем вы сами.Это та же причина, по которой следует использовать стороннюю криптографическую библиотеку вместо создания собственной.Делать это самостоятельно может быть веселее, но обычно это менее ответственно.
Делал это годами.Никогда не сталкивайтесь с проблемой.
Обычно я настраиваю свою БД на одну таблицу, содержащую все ключи, измененные даты и тому подобное.Никогда не сталкивался с проблемой дублирования ключей.
Единственный недостаток, который у него есть, заключается в том, что когда вы пишете несколько запросов для быстрого поиска некоторой информации, вам приходится много копировать и вставлять ключи.У вас больше нет коротких, легко запоминающихся идентификаторов.
Вот фрагмент теста, который поможет вам проверить его уникальность.вдохновлен комментарием @ scalabl3
Забавно то, что вы могли бы создать 2 одинаковых подряд подряд, конечно, при ошеломляющем уровне совпадения, удачи и божественного вмешательства, но, несмотря на непостижимые шансы, это все еще возможно!:D Да, этого не произойдет.просто говорю для развлечения, вспоминая тот момент, когда вы создали дубликат!Скриншот видео!scalabl3 20 окт.
Если вам повезет, установите флажок, он проверяет только сгенерированные в данный момент идентификаторы.Если вы хотите проверить историю, оставьте ее неотмеченной.Обратите внимание: в какой-то момент у вас может закончиться оперативная память, если вы не отметите этот флажок.Я постарался сделать его дружественным к процессору, чтобы при необходимости вы могли быстро прервать его: просто нажмите кнопку «Выполнить фрагмент» еще раз или покиньте страницу.
Math.log2 = Math.log2 || function(n){ return Math.log(n) / Math.log(2); }
Math.trueRandom = (function() {
var crypt = window.crypto || window.msCrypto;
if (crypt && crypt.getRandomValues) {
// if we have a crypto library, use it
var random = function(min, max) {
var rval = 0;
var range = max - min;
if (range < 2) {
return min;
}
var bits_needed = Math.ceil(Math.log2(range));
if (bits_needed > 53) {
throw new Exception("We cannot generate numbers larger than 53 bits.");
}
var bytes_needed = Math.ceil(bits_needed / 8);
var mask = Math.pow(2, bits_needed) - 1;
// 7776 -> (2^13 = 8192) -1 == 8191 or 0x00001111 11111111
// Create byte array and fill with N random numbers
var byteArray = new Uint8Array(bytes_needed);
crypt.getRandomValues(byteArray);
var p = (bytes_needed - 1) * 8;
for(var i = 0; i < bytes_needed; i++ ) {
rval += byteArray[i] * Math.pow(2, p);
p -= 8;
}
// Use & to apply the mask and reduce the number of recursive lookups
rval = rval & mask;
if (rval >= range) {
// Integer out of acceptable range
return random(min, max);
}
// Return an integer that falls within the range
return min + rval;
}
return function() {
var r = random(0, 1000000000) / 1000000000;
return r;
};
} else {
// From http://baagoe.com/en/RandomMusings/javascript/
// Johannes Baagøe <baagoe@baagoe.com>, 2010
function Mash() {
var n = 0xefc8249d;
var mash = function(data) {
data = data.toString();
for (var i = 0; i < data.length; i++) {
n += data.charCodeAt(i);
var h = 0.02519603282416938 * n;
n = h >>> 0;
h -= n;
h *= n;
n = h >>> 0;
h -= n;
n += h * 0x100000000; // 2^32
}
return (n >>> 0) * 2.3283064365386963e-10; // 2^-32
};
mash.version = 'Mash 0.9';
return mash;
}
// From http://baagoe.com/en/RandomMusings/javascript/
function Alea() {
return (function(args) {
// Johannes Baagøe <baagoe@baagoe.com>, 2010
var s0 = 0;
var s1 = 0;
var s2 = 0;
var c = 1;
if (args.length == 0) {
args = [+new Date()];
}
var mash = Mash();
s0 = mash(' ');
s1 = mash(' ');
s2 = mash(' ');
for (var i = 0; i < args.length; i++) {
s0 -= mash(args[i]);
if (s0 < 0) {
s0 += 1;
}
s1 -= mash(args[i]);
if (s1 < 0) {
s1 += 1;
}
s2 -= mash(args[i]);
if (s2 < 0) {
s2 += 1;
}
}
mash = null;
var random = function() {
var t = 2091639 * s0 + c * 2.3283064365386963e-10; // 2^-32
s0 = s1;
s1 = s2;
return s2 = t - (c = t | 0);
};
random.uint32 = function() {
return random() * 0x100000000; // 2^32
};
random.fract53 = function() {
return random() +
(random() * 0x200000 | 0) * 1.1102230246251565e-16; // 2^-53
};
random.version = 'Alea 0.9';
random.args = args;
return random;
}(Array.prototype.slice.call(arguments)));
};
return Alea();
}
}());
Math.guid = function() {
return 'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, function(c) {
var r = Math.trueRandom() * 16 | 0,
v = c == 'x' ? r : (r & 0x3 | 0x8);
return v.toString(16);
});
};
function logit(item1, item2) {
console.log("Do "+item1+" and "+item2+" equal? "+(item1 == item2 ? "OMG! take a screenshot and you'll be epic on the world of cryptography, buy a lottery ticket now!":"No they do not. shame. no fame")+ ", runs: "+window.numberofRuns);
}
numberofRuns = 0;
function test() {
window.numberofRuns++;
var x = Math.guid();
var y = Math.guid();
var test = x == y || historyTest(x,y);
logit(x,y);
return test;
}
historyArr = [];
historyCount = 0;
function historyTest(item1, item2) {
if(window.luckyDog) {
return false;
}
for(var i = historyCount; i > -1; i--) {
logit(item1,window.historyArr[i]);
if(item1 == history[i]) {
return true;
}
logit(item2,window.historyArr[i]);
if(item2 == history[i]) {
return true;
}
}
window.historyArr.push(item1);
window.historyArr.push(item2);
window.historyCount+=2;
return false;
}
luckyDog = false;
document.body.onload = function() {
document.getElementById('runit').onclick = function() {
window.luckyDog = document.getElementById('lucky').checked;
var val = document.getElementById('input').value
if(val.trim() == '0') {
var intervaltimer = window.setInterval(function() {
var test = window.test();
if(test) {
window.clearInterval(intervaltimer);
}
},0);
}
else {
var num = parseInt(val);
if(num > 0) {
var intervaltimer = window.setInterval(function() {
var test = window.test();
num--;
if(num < 0 || test) {
window.clearInterval(intervaltimer);
}
},0);
}
}
};
};Please input how often the calulation should run. set to 0 for forever. Check the checkbox if you feel lucky.<BR/>
<input type="text" value="0" id="input"><input type="checkbox" id="lucky"><button id="runit">Run</button><BR/>Я согласен с другими ответами.UUID достаточно безопасны практически для всех практических целей.1, и обязательно для вашего.
Но предположим (гипотетически), что это не так.
Есть ли лучшая система или какой-то шаблон для решения этой проблемы?
Вот несколько подходов:
Используйте больший UUID.Например, вместо 128 случайных битов используйте 256 или 512 или...Каждый бит, который вы добавляете к UUID в стиле типа 4, снижает вероятность столкновения вдвое, при условии, что у вас есть надежный источник энтропии.2.
Создайте централизованный или распределенный сервис, который генерирует UUID и записывает каждый из них, который он когда-либо выдавал.Каждый раз, когда он генерирует новый, он проверяет, что UUID никогда раньше не выдавался.Такой сервис было бы технически несложно реализовать (я думаю), если бы мы предположили, что люди, управляющие этим сервисом, абсолютно заслуживают доверия, неподкупны и так далее.К сожалению, их нет...особенно когда существует вероятность вмешательства правительств.Таким образом, этот подход, вероятно, непрактичен и может быть3 невозможно в реальном мире.
1. Если бы уникальность UUID определяла, были ли запущены ядерные ракеты в столице вашей страны, многих ваших сограждан не убедило бы «вероятность крайне мала».Отсюда моя квалификация «почти все».
2 – И вот вам философский вопрос.Есть ли что-нибудь по-настоящему случайное?Как бы мы узнали, если бы это было не так?Является ли Вселенная, какой мы ее знаем, симуляцией?Существует ли Бог, который мог бы «настроить» законы физики, чтобы изменить результат?
3 - Если кто-нибудь знает какие-либо научные работы по этой проблеме, прокомментируйте.
Не знаю, важно ли это для вас, но имейте в виду, что GUID глобально уникальны, но подстроки GUID не уникальны..
