Seberapa unik UUID?

Seberapa aman menggunakan UUID untuk mengidentifikasi sesuatu secara unik (Saya menggunakannya untuk file yang diunggah ke server)? Seperti yang saya pahami, ini didasarkan pada angka acak. Namun, bagi saya tampaknya diberikan waktu yang cukup, pada akhirnya akan mengulanginya sendiri, hanya secara kebetulan. Apakah ada sistem atau pola jenis yang lebih baik untuk mengatasi masalah ini?

Sangat aman:

risiko tahunan seseorang yang terkena meteorit diperkirakan satu peluang dalam 17 miliar, yang berarti probabilitasnya adalah sekitar 0,00000000006 (6 × 10 ⁻¹¹ ), setara dengan peluang menciptakan beberapa trilyunan UUID. dalam setahun dan memiliki satu duplikat. Dengan kata lain, hanya setelah menghasilkan 1 miliar UUID setiap detik selama 100 tahun ke depan, kemungkinan membuat hanya satu duplikat adalah sekitar 50%.

Peringatan:

Namun, probabilitas ini hanya berlaku ketika UUID dihasilkan menggunakan entropi yang memadai. Kalau tidak, probabilitas duplikat bisa secara signifikan lebih tinggi, karena dispersi statistik mungkin lebih rendah. Di mana pengidentifikasi unik diperlukan untuk aplikasi terdistribusi, sehingga UUID tidak berbenturan bahkan ketika data dari banyak perangkat digabungkan, keacakan benih dan generator yang digunakan pada setiap perangkat harus dapat diandalkan selama umur aplikasi. Di mana ini tidak layak, RFC4122 merekomendasikan untuk menggunakan varian namespace.

Sumber: Probabilitas UUID acak untuk bagian rangkap dari artikel Wikipedia tentang pengidentifikasi unik secara universal (tautan mengarah ke revisi mulai Desember 2016 sebelum pengeditan mengerjakan ulang bagian tersebut).

Juga lihat bagian saat ini pada subjek yang sama pada artikel pengenal unik universal yang sama, Tabrakan .

Jika dengan "diberikan waktu yang cukup" yang Anda maksud adalah 100 tahun dan Anda membuatnya dengan kecepatan satu miliar per detik, maka ya, Anda memiliki peluang 50% untuk mengalami tabrakan setelah 100 tahun.

Ada lebih dari satu jenis UUID, jadi "seberapa aman" tergantung pada jenis apa (spesifikasi UUID menyebut "versi") yang Anda gunakan.

• Versi 1 adalah berbasis waktu plus alamat MAC UUID. 128-bit berisi 48-bit untuk alamat MAC kartu jaringan (yang secara unik ditugaskan oleh pabrikan) dan jam 60-bit dengan resolusi 100 nanodetik. Jam itu terbungkus pada tahun 3603 AD sehingga UUID ini aman setidaknya sampai saat itu (kecuali jika Anda membutuhkan lebih dari 10 juta UUID baru per detik atau seseorang mengkloning kartu jaringan Anda). Saya katakan "setidaknya" karena jam mulai pada 15 Oktober 1582, jadi Anda memiliki sekitar 400 tahun setelah jam membungkus sebelum bahkan ada kemungkinan kecil duplikasi.

• Versi 4 adalah nomor acak UUID. Ada enam bit tetap dan sisa UUID adalah 122-bit keacakan. Lihat Wikipedia atau analisis lain yang menggambarkan betapa tidak mungkin duplikat itu.

• Versi 3 menggunakan MD5 dan Versi 5 menggunakan SHA-1 untuk membuat 122-bit tersebut, bukan pembangkit angka acak atau pseudo-acak. Jadi dalam hal keamanan, itu seperti Versi 4 yang menjadi masalah statistik (selama Anda memastikan apa yang diproses oleh algoritma digest selalu unik).

• Versi 2 mirip dengan Versi 1, tetapi dengan jam yang lebih kecil sehingga akan membungkus lebih cepat. Tetapi karena UUID Versi 2 adalah untuk DCE, Anda seharusnya tidak menggunakannya.

Jadi untuk semua masalah praktis, mereka aman. Jika Anda merasa tidak nyaman dengan menyerahkannya pada probabilitas (mis. Anda adalah tipe orang yang khawatir akan bumi dihancurkan oleh asteroid besar dalam hidup Anda), pastikan Anda menggunakan UUID Versi 1 dan dijamin unik ( seumur hidup Anda, kecuali jika Anda berencana untuk hidup melewati 3603 AD).

Jadi mengapa tidak semua orang cukup menggunakan UUID Versi 1? Itu karena Versi 1 UUID mengungkapkan alamat MAC dari mesin yang dihasilkan dan mereka dapat diprediksi - dua hal yang mungkin memiliki implikasi keamanan untuk aplikasi menggunakan UUID tersebut.

Jawabannya tergantung pada versi UUID.

Banyak generator UUID menggunakan nomor acak versi 4. Namun, banyak dari ini menggunakan Pseudo a Random Number Generator untuk menghasilkannya.

Jika PRNG yang kurang diunggulkan dengan periode kecil digunakan untuk menghasilkan UUID saya akan mengatakan itu tidak aman sama sekali.

Oleh karena itu, hanya seaman algoritma yang digunakan untuk menghasilkannya.

Di sisi lain, jika Anda tahu jawaban untuk pertanyaan-pertanyaan ini maka saya pikir versi 4 uuid harus sangat aman digunakan. Sebenarnya saya menggunakannya untuk mengidentifikasi blok pada sistem file blok jaringan dan sejauh ini belum mengalami bentrokan.

Dalam kasus saya, PRNG yang saya gunakan adalah twister mersenne dan saya berhati-hati dengan cara itu diunggulkan yang berasal dari berbagai sumber termasuk / dev / urandom. Mersenne twister memiliki periode 2 ^ 19937 - 1. Ini akan menjadi waktu yang sangat lama sebelum saya melihat uuid berulang.

Mengutip dari Wikipedia :

Dengan demikian, siapa pun dapat membuat UUID dan menggunakannya untuk mengidentifikasi sesuatu dengan keyakinan yang masuk akal bahwa pengidentifikasi tidak akan pernah digunakan secara tidak sengaja oleh siapa pun untuk hal lain

Selanjutnya dijelaskan dengan cukup baik tentang seberapa aman sebenarnya. Jadi untuk menjawab pertanyaan Anda: Ya, cukup aman.

Saya setuju dengan jawaban lain. UUID cukup aman untuk hampir semua tujuan praktis ¹ , dan tentunya untuk Anda.

Tapi anggaplah (secara hipotetis) bahwa mereka tidak.

Apakah ada sistem atau pola jenis yang lebih baik untuk mengatasi masalah ini?

Berikut adalah beberapa pendekatan:

1. Gunakan UUID yang lebih besar. Misalnya, alih-alih 128 bit acak, gunakan 256 atau 512 atau ... Setiap bit yang Anda tambahkan ke gaya-4 gaya UUID akan mengurangi kemungkinan tabrakan hingga setengahnya, dengan asumsi bahwa Anda memiliki sumber entropi ^{2 yang} andal. .

2. Membangun layanan terpusat atau terdistribusi yang menghasilkan UUID dan mencatat masing-masing dan setiap yang pernah dikeluarkannya. Setiap kali menghasilkan yang baru, itu memeriksa bahwa UUID belum pernah dikeluarkan sebelumnya. Layanan seperti itu akan secara teknis mudah untuk diterapkan (saya pikir) jika kita mengasumsikan bahwa orang yang menjalankan layanan tersebut benar-benar dapat dipercaya, tidak dapat rusak, dan sebagainya. Sayangnya, mereka tidak ... terutama ketika ada kemungkinan organisasi keamanan pemerintah ikut campur. Jadi, pendekatan ini mungkin tidak praktis, dan mungkin ³ tidak mungkin di dunia nyata.

^{1 - Jika keunikan UUID menentukan apakah rudal nuklir diluncurkan di ibu kota negara Anda, banyak warga negara Anda tidak akan diyakinkan oleh "kemungkinannya sangat rendah". Oleh karena itu kualifikasi "hampir semua" saya.}

^{2 - Dan inilah pertanyaan filosofis untuk Anda. Apakah ada yang benar-benar acak? Bagaimana kita tahu kalau bukan? Apakah alam semesta seperti yang kita kenal sebagai simulasi? Adakah Tuhan yang mungkin "mengubah" hukum fisika untuk mengubah hasil?}

^{3 - Jika ada yang tahu makalah penelitian tentang masalah ini, silakan komentar.}

Skema UUID umumnya menggunakan tidak hanya elemen pseudo-acak, tetapi juga waktu sistem saat ini, dan semacam ID perangkat keras yang sering unik jika tersedia, seperti alamat MAC jaringan.

Inti dari menggunakan UUID adalah bahwa Anda memercayainya untuk melakukan pekerjaan yang lebih baik dalam memberikan ID unik daripada yang dapat Anda lakukan sendiri. Ini adalah alasan yang sama di balik menggunakan perpustakaan kriptografi pihak ke-3 daripada menggulirkan milik Anda sendiri. Melakukannya sendiri mungkin lebih menyenangkan, tetapi biasanya kurang bertanggung jawab untuk melakukannya.

Sudah melakukannya selama bertahun-tahun. Tidak pernah mengalami masalah.

Saya biasanya mengatur DB saya untuk memiliki satu tabel yang berisi semua kunci dan tanggal yang dimodifikasi dan semacamnya. Belum pernah mengalami masalah kunci duplikat.

Satu-satunya kelemahan yang dimilikinya adalah ketika Anda menulis beberapa pertanyaan untuk menemukan beberapa informasi dengan cepat, Anda melakukan banyak penyalinan dan menempelkan kunci. Anda tidak memiliki id pendek yang mudah diingat lagi.

Berikut cuplikan pengujian bagi Anda untuk mengujinya. terinspirasi oleh komentar @ scalabl3

Lucunya, Anda bisa menghasilkan 2 berturut-turut yang identik, tentu saja pada tingkat kebetulan, keberuntungan, dan campur tangan ilahi yang membingungkan, namun meskipun ada peluang yang tak terduga, itu masih mungkin! : D Ya, itu tidak akan terjadi. hanya mengatakan untuk bersenang-senang memikirkan saat itu ketika Anda membuat duplikat! Tangkapan layar video! - scalabl3 20 Okt '15 jam 19:11

Jika Anda merasa beruntung, centang kotak, itu hanya memeriksa id yang saat ini dihasilkan. Jika Anda ingin pemeriksaan riwayat, biarkan tidak dicentang. Harap dicatat, Anda mungkin kehabisan ram di beberapa titik jika Anda membiarkannya tidak dicentang. Saya mencoba membuatnya cpu friendly sehingga Anda dapat membatalkan dengan cepat saat dibutuhkan, cukup tekan tombol run snippet lagi atau tinggalkan halaman.

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 <[email protected]>, 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 <[email protected]>, 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/>

Saya tidak tahu apakah ini penting bagi Anda, tetapi perlu diingat bahwa GUID secara global unik, tetapi substring dari GUID tidak .

Untuk UUID4 saya membuatnya bahwa ada sekitar ID sebanyak yang ada butiran pasir dalam kotak berbentuk kubus dengan sisi 360.000 km panjang. Itu kotak dengan sisi ~ 2 1/2 kali lebih panjang dari diameter Jupiter.

Bekerja agar seseorang dapat memberi tahu saya jika saya mengacaukan unit:

• volume butiran pasir 0,00947mm ^ 3 ( Wali )
• UUID4 memiliki 122 bit acak -> 5.3e36 nilai yang mungkin ( wikipedia )
• volume pasir sebanyak itu = 5.0191e34 mm ^ 3 atau 5.0191e + 25m ^ 3
• panjang sisi kotak kubik dengan volume itu = 3,69E8m atau 369.000 km
• diameter Jupiter: 139.820km (google)