UUID はどれくらいユニークですか?

StackOverflow https://stackoverflow.com/questions/1155008

  •  18-09-2019
  •  | 
  •  

質問

何かを一意に識別するために UUID を使用することはどの程度安全ですか (サーバーにアップロードされたファイルに UUID を使用しています)。私の理解では、それは乱数に基づいています。しかし、十分な時間があれば、まったくの偶然で、最終的には同じことが繰り返されるように私には思えます。この問題を軽減するためのより良いシステムや何らかのパターンはあるのでしょうか?

役に立ちましたか？

解決

非常に安全ます：

  

隕石に見舞われている与えられた人の年間リスクがあります   意味170億1回のチャンスであると推定   確率は約0.00000000006（6×10 -11 ）、オッズに相当します   年のUUIDの兆の数十を作成し、1つを有するの   重複します。言い換えれば、唯一のすべての10億のUUIDを生成した後   次の100年のための第二、1つだけ作成する確率   重複は約50％になります。

警告：

  

しかし、これらの確率は唯一のUUIDが生成されたときに保持します   十分なエントロピーを使用。重複のそれ以外の場合は、確率   統計的な分散可能性があるため、有意に高いことができ   低くなります。一意の識別子は、分散のために必要とされる場合   アプリケーション、のUUIDが重複することがないようにしても、多くのデータ   デバイスがマージされ、種子や発電機のランダム性は、上の使用します   すべてのデバイスは、アプリケーションの生活のために信頼できるものでなければなりません。どこ   これは現実的ではありません、RFC4122は、名前空間のバリアントを使用することをお勧めします   その代わります。

ソース： の重複のランダムUUID確率<汎用一意識別子（編集部分を手直しする前に、リンクが2016年12月からの改正につながる）上のWikipediaの記事の/ em>のセクションでます。

また、同じ汎用一意識別子の記事で同じテーマに関する現在のセクションを参照してください の衝突のを。

他のヒント

で「十分な時間が与えられた」場合は、100年を意味し、あなたが億秒の速度でそれらを作成している、[はい、あなたは100年後の衝突を持つ50％の確率を持っています。

UUID には複数のタイプがあるため、「どの程度安全か」は、使用しているタイプ (UUID 仕様では「バージョン」と呼ばれます) によって異なります。

  • バージョン 1 は、時間ベースと MAC アドレスの UUID です。128 ビットには、ネットワーク カードの MAC アドレス (製造元によって独自に割り当てられる) の 48 ビットと、100 ナノ秒の分解能を持つ 60 ビット クロックが含まれます。その時計 西暦 3603 年に終わります。 したがって、これらの UUID は、少なくともそれまでは安全です (1 秒あたり 1,000 万を超える新しい UUID が必要になるか、誰かがネットワーク カードのクローンを作成しない限り)。「少なくとも」と言ったのは、時計が 1582 年 10 月 15 日に始まるため、時計が一周してから重複の可能性がわずかでもなくなるまでに約 400 年かかるからです。

  • バージョン 4 は乱数 UUID です。UUID には 6 つの固定ビットがあり、残りの 122 ビットはランダムです。見る ウィキペディア または、重複の可能性がいかに低いかを説明するその他の分析。

  • バージョン 3 は MD5 を使用し、バージョン 5 は乱数または擬似乱数ジェネレーターの代わりに SHA-1 を使用して 122 ビットを作成します。したがって、安全性の観点から見ると、バージョン 4 が統計的な問題であるようなものです (ダイジェスト アルゴリズムが処理している内容が常に一意であることを確認している限り)。

  • バージョン 2 はバージョン 1 に似ていますが、クロックが小さいため、より早く終了します。ただし、バージョン 2 の UUID は DCE 用であるため、これらを使用しないでください。

したがって、すべての実際的な問題については安全です。確率に任せるのが不安な場合（例：あなたは、生きているうちに地球が大きな小惑星によって破壊されるのではないかと心配するタイプの人です）。必ずバージョン 1 の UUID を使用してください。これは、（西暦 3603 年以降に生きるつもりでない限り、生涯にわたって）一意であることが保証されています。 ）。

では、なぜ誰もが単純にバージョン 1 の UUID を使用しないのでしょうか?これは、バージョン 1 の UUID は、それが生成されたマシンの MAC アドレスを明らかにし、予測可能であるためです。この 2 つの点は、これらの UUID を使用するアプリケーションにセキュリティ上の影響を与える可能性があります。

これに対する答えは、UUIDのバージョンに大きく依存してます。

多くのUUIDジェネレータは、バージョン4の乱数を使用しています。しかし、これらの多くは、それらを生成する擬似乱数発生器を使用します。

小さな期間であれば悪いシードのPRNGが、私はそれがすべてで非常に安全ではないと言うだろうUUIDを生成するために使用されます。

そのため、アルゴリズムはそれを生成するのに使用されるだけのように安全です。

これらの質問に対する答えを知っていれば、

は、フリップ側では、私はバージョン4 UUIDを使用することは非常に安全であるべきだと思います。実際、私は、ネットワークブロック・ファイル・システム上のブロックを識別するためにそれを使用していますし、これまでの衝突を持っていませんでした。

私の場合、私が使用しているPRNGは、メルセンヌツイスターであり、私はは/ dev / urandomが含む複数のソースからのもので、それは播種の道に注意されています。私が繰り返しUUIDを参照してくださいする前に非常に非常に長い時間になるだろう。

1. - 。メルセンヌツイスターは2 ^ 19937の期間を持っています

ウィキペディアするから引用

  

このように、誰もがUUIDと使用を作成することができます   それはで何かを識別するために   合理的な自信を持っています   識別子はなることはありません   意図せずのために誰でも使用   何か

これは、それが実際にどのように安全にかなり良い詳細をで説明するために行きます。だから、あなたの質問に答える：はい、それは十分に安全です。

。

利用可能な場合UUIDスキームは、一般に、ネットワークMACアドレスとして、擬似ランダムな要素だけでなく、現在のシステム時刻、およびしばしば固有のハードウェアIDのいくつかの並べ替えていないだけを使用します。

UUIDを使用しての全体のポイントは、あなた自身が行うことができるだろうあなたよりもユニークなIDを提供するより良い仕事をすることを信頼していることです。これは、サードパーティの暗号ライブラリを使用してのではなく、独自の圧延の背後にある同じ原理です。それを自分で行うと、より楽しいこと、それは一般的にそうすることが少ない責任だことがあります。

は、年のためにそれをやって。問題に遭遇することはありません。

私は通常私のDBのすべてのキーと変更された日付と、そのようなが含まれている一つのテーブルを持つように設定します。これまで重複キーの問題に実行していない。

それが持っている唯一の欠点は、あなたがすぐにいくつかの情報を見つけるために、いくつかのクエリを書いているときに、キーのコピー＆ペーストをたくさんやっているです。あなたは短い簡単にはもうidを覚えておく必要はありません。

ここであなたはそれのuniquenesをテストするためのテスト抜粋です。 @のscalabl3さんのコメントに触発された。

  

おかしい事は、あなたが偶然、幸運と神の介入の心の遠くなるようなレベルではもちろん、同一であった行の2を発生させる可能性があるが、まだ計り知れないオッズにもかかわらず、それはまだ可能です！ ：Dはい、それは発生しません。ちょうどあなたが複製を作成したとき、その瞬間を考えるの娯楽のために言って！スクリーンショット動画！ - 19時11分でscalabl3 10月20日'15

あなたはラッキーだと思う場合は、チェックボックスをチェックし、それだけで現在生成されたidをチェックします。あなたは歴史のチェックを希望される場合は、チェックボックスをオフのままにします。 あなたは未チェックのままならば、あなたはいくつかの点でラムが不足することがありますので、予めご了承ください。私は必要なときにすぐに中止することができますので、それは優しい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/>

他の回答に同意します。UUID は、ほぼすべての実用的な目的に対して十分に安全です1, 、そして確かにあなたのために。

しかし、（仮に）そうではないと考えてください。

この問題を軽減するためのより良いシステムや何らかのパターンはあるのでしょうか?

以下にいくつかのアプローチを示します。

  1. より大きな UUID を使用してください。たとえば、128 のランダム ビットの代わりに、256 または 512 などを使用します。信頼できるエントロピーのソースがあると仮定すると、タイプ 4 スタイルの UUID にビットを追加するたびに、衝突の確率が半分に減少します。2.

  2. UUID を生成し、これまでに発行したすべての UUID を記録する集中型または分散型サービスを構築します。新しい UUID を生成するたびに、その UUID が以前に発行されたことがないかどうかがチェックされます。このようなサービスは、サービスを実行している人々が絶対に信頼でき、腐敗しないなどと仮定すれば、技術的には簡単に実装できるでしょう (私はそう思います)。残念ながら、そうではありません...特に政府が介入する可能性がある場合。したがって、このアプローチはおそらく非現実的であり、実際には不可能である可能性があります。3 現実世界では不可能。

1 - UUID の一意性によって、あなたの国の首都に核ミサイルが発射されたかどうかが決まるとしたら、多くの国民は「確率は極めて低い」ということに納得しないでしょう。したがって、私の「ほぼすべて」の資格があります。

2 - ここであなたに哲学的な質問があります。本当にランダムなものなどあるのでしょうか？そうでない場合はどうすればわかるでしょうか?私たちが知っている宇宙はシミュレーションなのでしょうか?物理法則を「微調整」して結果を変える神がいるでしょうか?

3 - この問題に関する研究論文を知っている人がいたら、コメントしてください。

私は=のhref =「http://blogs.msdn.com/oldnewthing/archive/2008/06/27/8659071.aspx」のrelを<そのこれがあなたにとって重要ならば知っているが、心の中で保管しないで「nofollowをnoreferrer」> GUIDはグローバルにユニークですが、GUIDの部分文字列はのではありません。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top