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

Question

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

Answer 1

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

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

Оговорка:

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

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

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

Answer 2

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

Answer 3

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

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

Answer 4

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

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

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

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

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

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

Answer 5

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

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

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

Answer 6

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

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

Answer 7

Вот тестовый фрагмент, чтобы проверить его уникальность. вдохновлено комментарием @ 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/>

Answer 8

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

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

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

Answer 9

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

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

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

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

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

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

---

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

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

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

Answer 10

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