Насколько уникален UUID?

451

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

Джейсон
источник
11
Для достаточно большого значения «достаточно времени» :)
91
"Насколько уникален UUID?" Я считаю, что это уникально. ;)
Майлз
29
И если вы не планируете разработку на Венере, GUID должно быть достаточно.
Скаффман
1
подробнее и генератор здесь: онлайн генератор uuid
Дейв
2
«уникальный» означает никогда не сталкиваются . Если у него есть потенциал для столкновения, это не уникально . Поэтому по определению UUID не является уникальным и безопасным только в том случае, если вы подготовлены к возможным столкновениям независимо от вероятности столкновений. В противном случае ваша программа просто неверна. Вы можете сказать UUID как «почти уникальный», но это не значит, что он «уникальный».
Эонил

Ответы:

446

Очень безопасно:

ежегодный риск удара метеорита по данному человеку составляет один шанс из 17 миллиардов, что означает, что вероятность составляет около 0,00000000006 (6 × 10 -11 ), что эквивалентно вероятности создания нескольких десятков триллионов UUID. через год и с одним дубликатом. Другими словами, только после генерирования 1 миллиарда UUID каждую секунду в течение следующих 100 лет вероятность создания только одного дубликата составит около 50%.

Предостережение:

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

Источник: раздел Случайная вероятность UUID дубликатов в статье Википедии об универсально уникальных идентификаторах (ссылка ведет к пересмотру с декабря 2016 года, прежде чем редактирование переработало раздел).

Также см. Текущий раздел на ту же тему в той же статье с универсальным уникальным идентификатором, Collisions .

Мартейн Питерс
источник
22
Мне нравится эта часть из Википедии: Однако эти вероятности имеют место только тогда, когда UUID генерируются с использованием достаточной энтропии. В противном случае вероятность дубликатов может быть значительно выше, поскольку статистическая дисперсия может быть ниже. Так какова реальная возможность дублирования, отмечая это предложение? Мы не можем создавать реальные случайные числа на компьютере, не так ли?
Ман
6
На самом деле, была проделана большая работа по поиску способов ввести как можно больше энтропии («реальной случайности», я думаю, вы бы ее назвали) в API случайных чисел. См en.wikipedia.org/wiki/Entropy_%28computing%29
broofa
4
Это на самом деле более высокая вероятность столкновения, чем я себе представлял. День рождения парадокс в, я думаю.
Кэмерон
Можете ли вы подтвердить, что использование UUID будет безопасным между выполнениями приложения? (например, скрипт на python)
Джордж Сп
отличный пример ...: D
NuttLoose
152

Если под «достаточным количеством времени» вы подразумеваете 100 лет и создаете их со скоростью миллиард в секунду, то да, у вас есть 50% шанс столкновения через 100 лет.

узда
источник
186
Но только после использования 256 эксабайт хранилища для этих идентификаторов.
Боб Аман
16
Забавно то, что вы могли генерировать 2 подряд, которые были бы идентичны, конечно, на ошеломляющих уровнях совпадений, удачи и божественного вмешательства, но, несмотря на непостижимые шансы, это все еще возможно! : D Да, этого не произойдет. просто для развлечения подумать о том моменте, когда вы создали дубликат! Скриншот видео!
scalabl3
4
Является ли уникальность исключительно из-за случайности? Или есть другие факторы? (например, отметка времени, IP-адрес и т. д.)
Вейши Цзэн
15
@TheTahaan Это не то, что означает случайное. Это не означает «абсолютно непредсказуемый» - обычно они следуют некоторому распределению. Если вы подбросите 10 монет, шанс получить 2 головы, затем 3 хвоста, а затем 5 голов, довольно низок (2 ^ -10, около 0,001). Это действительно случайно, но мы точно можем знать, шансов получить конкретный результат. Мы просто не можем сказать заранее , будет ли это будет происходить.
Ричард Раст
5
Просто чтобы объяснить, что эта реализация сделала неправильно, они используют UUID версии 1, который использует комбинацию метки времени и MAC-адреса для своей уникальности. Однако если вы генерируете UUID достаточно быстро, отметка времени еще не будет увеличена. В этом сценарии ваш алгоритм генерации UUID должен отслеживать последнюю использованную метку времени и увеличивать ее на 1. Они явно не смогли сделать этот шаг. Однако все идентификаторы UUID версии 1, правильно сгенерированные одной и той же машиной за короткий период, будут иметь очевидное сходство, но все же должны быть уникальными.
Боб Аман
103

Существует более одного типа UUID, поэтому «насколько безопасно» зависит от того, какой тип (который спецификации UUID называют «версия») вы используете.

  • Версия 1 основана на времени плюс UUID MAC-адреса. 128-бит содержит 48 бит для MAC-адреса сетевой карты (который уникально назначен производителем) и 60-битную тактовую частоту с разрешением 100 наносекунд. Эти часы помещаются в 3603 AD, поэтому эти 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.

Hoylen
источник
1
По умолчанию версия UUID имеет серьезные проблемы, когда они генерируются одним и тем же сервером для многих людей. UUID версии 4 является моим по умолчанию, так как вы можете быстро написать что-нибудь для генерации на любом языке или платформе (включая javascript).
Джастин Бозонье
1
@Hoylen Хорошо объяснил! но требуется ли много преувеличения?
Dinoop Paloli
1
Теоретически , он однозначно присваивается производителем.
OrangeDog
4
Не нужно генерировать 10 миллионов UUID версии 1 в секунду, чтобы встретить дубликат; нужно просто сгенерировать партию из 16 384 UUID в пределах одного «тика», чтобы переполнить порядковый номер. Я видел, как это происходило с реализацией, которая наивно полагалась на источник синхронизации, который (1) имел гранулярность уровня мкс, и (2) не гарантировалось, что он является монотонным (системные часы нет). Будьте осторожны, чей код генерации UUID вы используете, и будьте особенно осторожны с генераторами UUID на основе времени. Их сложно понять правильно, поэтому подвергните их нагрузочным тестам, прежде чем их использовать.
Майк Штробель
Может ли промежуток времени между генерируемыми UUID v4 привести к большей вероятности коллизий? Я имею в виду, что в приложениях с интенсивным движением предположим, что тысячи uuids генерируются одновременно, есть ли больше шансов на столкновение, чем если бы такое же количество uuids генерировалось за относительно более длительный период времени?
Джонатан
18

Ответ на это может зависеть в значительной степени от версии UUID.

Многие генераторы UUID используют случайное число версии 4. Однако многие из них используют генератор псевдослучайных чисел для их генерации.

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

Следовательно, он настолько же безопасен, насколько и алгоритмы, используемые для его генерации.

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

В моем случае PRNG, который я использую, является мерсенновым твистером, и я осторожен с тем, как он просеивается из нескольких источников, включая / dev / urandom. Твистер Мерсенна имеет период 2 ^ 19937 - 1. Пройдет очень и очень много времени, прежде чем я увижу повторяющуюся волну.

Matt
источник
14

Цитата из Википедии :

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

Далее достаточно подробно объясняется, насколько это безопасно на самом деле. Итак, чтобы ответить на ваш вопрос: да, это достаточно безопасно.

Дейв Фогт
источник
9

Я согласен с другими ответами. UUID достаточно безопасны практически для всех практических целей 1 и, конечно, для ваших.

Но предположим (гипотетически), что это не так.

Есть ли лучшая система или шаблон какого-то типа, чтобы облегчить эту проблему?

Вот несколько подходов:

  1. Используйте больший UUID. Например, вместо 128 случайных битов, используйте 256 или 512 или ... Каждый бит, который вы добавляете к UUID типа 4, уменьшит вероятность коллизии вдвое, предполагая, что у вас есть надежный источник энтропии 2. ,

  2. Создайте централизованную или распределенную службу, которая генерирует идентификаторы UUID и регистрирует каждую из них, которую она когда-либо выпускала. Каждый раз, когда он генерирует новый, он проверяет, что UUID никогда не выдавался раньше. Такой сервис был бы технически прост в реализации (я думаю), если бы мы предполагали, что люди, работающие с сервисом, были абсолютно заслуживающими доверия, неподкупными и так далее. К сожалению, они не ... особенно, когда есть возможность вмешательства правительственных служб безопасности. Таким образом, этот подход, вероятно , нецелесообразно, и может быть 3 невозможно в реальном мире.


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

2 - И вот вам философский вопрос. Что-нибудь действительно случайное? Как мы узнаем, что это не так? Является ли вселенная, какой мы ее знаем, симуляцией? Есть ли Бог, который мог бы «настроить» законы физики, чтобы изменить результат?

3 - Если кто-нибудь знает какие-либо исследовательские работы по этой проблеме, пожалуйста, прокомментируйте.

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

Схемы UUID, как правило, используют не только псевдослучайный элемент, но также текущее системное время и некоторый вид часто уникального идентификатора оборудования, если таковой имеется, например, сетевой MAC-адрес.

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

Parappa
источник
6

Делал это годами. Никогда не сталкивайтесь с проблемой.

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

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

Постума
источник
5

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

Забавно то, что вы могли сгенерировать 2 подряд, которые были бы идентичны, конечно, на ошеломляющих уровнях совпадений, удачи и божественного вмешательства, но, несмотря на непостижимые шансы, это все еще возможно! : D Да, этого не произойдет. просто для развлечения подумать о том моменте, когда вы создали дубликат! Скриншот видео! - scalabl3 20 октября 15 в 19:11

Если вам повезло, установите флажок, он проверяет только сгенерированные идентификаторы. Если вы хотите проверить историю, не проверяйте ее. Обратите внимание, что в какой-то момент у вас может кончиться баран, если вы оставите его без контроля. Я попытался сделать его дружественным к процессору, чтобы вы могли быстро прервать его при необходимости, просто нажмите кнопку «Выполнить фрагмент» еще раз или покиньте страницу.

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/>

Tschallacka
источник
Попробуйте использовать UCID RFC 4122 версии 1 (дата-время и MAC-адрес).
zaph
Раньше он работал быстро, до недавнего обновления Chrome. Я заметил то же самое 4 недели назад.
Чаллака
3

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

Грант Вагнер
источник
1
Имейте в виду, что ссылка, указанная здесь, говорит о UUID версии 1 (которые переносят информацию о генерирующем компьютере и т. Д. В идентификатор). Большинство других Ответов говорят о Версии 4 (которые абсолютно случайны). Приведенная выше ссылка на статью в Википедии en.wikipedia.org/wiki/Universally_unique_identifier объясняет различные типы UUID.
Кратенко
3

Для UUID4 я установил, что в кубическом коробе со стороной 360 000 км в длину примерно столько же идентификаторов, сколько песчинок. Это коробка со сторонами примерно в 2 1/2 раза длиннее диаметра Юпитера.

Работая так, чтобы кто-то мог сказать мне, если я испортил единицы:

  • объем зерна песка 0,00947мм ^ 3 ( Хранитель )
  • UUID4 имеет 122 случайных бита -> 5,3e36 возможных значений ( википедия )
  • объем такого количества песчинок = 5.0191e34 мм ^ 3 или 5.0191e + 25м ^ 3
  • длина стороны кубической коробки с таким объемом = 3,69E8 м или 369 000 км
  • диаметр Юпитера: 139 820 км (Google)
потерял
источник
На самом деле я предполагаю, что это предполагает 100% упаковку, так что, возможно, я должен добавить фактор для этого!
потерял