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

Question

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

Answer 1

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

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

Caveat:

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

Источник: http://en.wikipedia.org/wiki/UUID#Random_UUID_probability_of_duplicates

Википедия статье этот раздел удален, но у них есть полезные ссылки на внешние ссылки на него где-нибудь еще: http://www.h2database.com/html/advanced.html#uuid

Answer 2

Цитирование из Wikipedia:

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

Он продолжает объяснять, в довольно хорошая информация о том, насколько безопасно это на самом деле. Поэтому, чтобы ответить на ваш вопрос: Да, это достаточно безопасно.

Answer 3

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

Answer 4

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

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

Answer 5

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

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

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

Answer 6

Я не знаю, имеет ли это значение для вас, но имейте в виду, что GUIDs are globally unique, but substrings of GUIDs aren't.

Answer 7

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

• Версия 1 - это временной адрес плюс MAC-адрес UUID. 128 бит содержит 48 бит для MAC-адреса сетевой карты (который однозначно назначен производителем) и 60-битный тактовый сигнал с разрешением 100 наносекунд. Это часы wraps in 3603 A.D., поэтому эти UUID безопасны по крайней мере до тех пор (если вам не требуется более 10 миллионов новых UUID в секунду, или кто-то клонирует вашу сетевую карту). Я говорю «по крайней мере», потому что часы начинаются 15 октября 1582 года, поэтому у вас есть около 400 лет после того, как часы обертываются, прежде чем есть даже небольшая возможность дублирования.

• Версия 4 - это случайное число UUID. Существует шесть фиксированных бит, а остальная часть UUID - 122-бит случайности. См. Wikipedia или другой анализ, в котором описывается, насколько маловероятен дубликат.

• Версия 3 использует MD5, а версия 5 использует SHA-1 для создания этих 122-бит вместо генератора случайных или псевдослучайных чисел. Таким образом, с точки зрения безопасности это похоже на версию 4, являющуюся статистической проблемой (при условии, что вы убедитесь, что алгоритм дайджеста является уникальным).

• Версия 2 аналогична версии 1, но с меньшими часами, поэтому она собирается обернуться намного раньше. Но поскольку UUID версии 2 предназначены для DCE, вы не должны использовать их.

Так что для всех практических проблем они безопасны. Если вам неудобно оставлять это до вероятностей (например, ваш тип человека, который беспокоится о том, что земля будет уничтожена большим астероидом в вашей жизни), просто убедитесь, что вы используете UUID Версии 1, и гарантированно будет уникальным (в вашей жизни, если вы не планируете жить за 3603 г. н.э.).

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

Answer 8

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

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

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

Поэтому он настолько же безопасен, как и алгоритмы его генерации.

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

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

Answer 9

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

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

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

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