Jak unikalny jest UUID?

Jeśli przez "wystarczająco dużo czasu" masz na myśli 100 lat i tworzysz je w tempie miliarda na sekundę, to tak, masz 50% szans na kolizję po 100 latach.

Istnieje więcej niż jeden typ UUID, więc "jak bezpieczny" zależy od tego, jakiego typu (który Specyfikacja uuid nazywa "wersją") używasz.

• Wersja 1 to time based plus MAC address UUID. 128 bitów zawiera 48 bitów dla adresu MAC karty sieciowej (który jest jednoznacznie przypisany przez producenta) oraz 60-bitowy zegar o rozdzielczości 100 nanosekund. Ten zegar zawija się w 3603 A. D. więc te Uuidy są bezpieczne przynajmniej do tego czasu (chyba że potrzebujesz więcej niż 10 milionów nowych uuid na sekundę lub ktoś klonuje Twoją kartę sieciową). Mówię "przynajmniej", ponieważ zegar zaczyna się 15 października 1582, więc masz około 400 lat po zawinięciu zegara, zanim będzie nawet mała możliwość powielania.

• Wersja 4 jest liczbą losową UUID. Jest sześć stałych bitów, a reszta UUID to 122 bity losowości. Zobacz Wikipedia lub inne analizy, które opisują, jak bardzo mało prawdopodobny jest duplikat.

• Wersja 3 to używa MD5, a wersja 5 używa SHA-1 do tworzenia tych 122-bitów, zamiast generatora liczb losowych lub pseudolosowych. Tak więc pod względem bezpieczeństwa jest jak Wersja 4 będąca zagadnieniem statystycznym (o ile upewnisz się, że algorytm digest jest przetwarzany zawsze jest unikalny).

• Wersja 2 jest podobna do wersji 1, ale z mniejszym zegarem, więc będzie owijać się znacznie wcześniej. Ale ponieważ uuid w wersji 2 są dla DCE, nie powinieneś ich używać.

Więc dla wszystkich praktyczne problemy są bezpieczne. Jeśli czujesz się niekomfortowo z pozostawieniem go do prawdopodobieństwa (np. jesteś typem osoby, która martwi się, że ziemia zostanie zniszczona przez dużą asteroidę w twoim życiu), po prostu upewnij się, że używasz wersji 1 UUID i jest gwarantowana, że będzie unikalna (w twoim życiu, chyba że planujesz żyć po 3603 AD).

Dlaczego więc nie wszyscy po prostu używają uuid w wersji 1? Dzieje się tak dlatego, że identyfikatory uuid wersji 1 ujawniają adres MAC maszyny, na której została wygenerowana i mogą być przewidywalne-dwie rzeczy, które mogą mieć wpływ na bezpieczeństwo aplikacji używającej tych uuid.

Odpowiedź na to pytanie może w dużej mierze zależeć od wersji UUID.

Wiele generatorów UUID używa losowej liczby w wersji 4. Jednak wiele z nich używa Pseudo generatora liczb losowych do ich generowania.

Jeśli do wygenerowania UUID używany jest słabo zaszeregowany PRNG z małym okresem, powiedziałbym, że nie jest on wcale Bezpieczny.

Dlatego jest tylko tak bezpieczny, jak algorytmy używane do jej generowania.

Z drugiej strony, jeśli znasz odpowiedź na te pytania, to myślę, że uuid w wersji 4 powinien być bardzo bezpieczny w użyciu. W rzeczywistości używam go do identyfikacji bloków w systemie plików bloków sieciowych i do tej pory nie miałem kolizji.

W moim przypadku PRNG, którego używam, to Mersenne twister i jestem ostrożny w sposobie, w jaki jest seedowany, który pochodzi z wielu źródeł, w tym /dev/urandom. Mersenne twister ma okres 2^19937-1 . Minie bardzo dużo czasu, zanim zobaczę powtarzające się uuid.

Cytowanie z Wikipedii :

W ten sposób każdy może utworzyć UUID i użyć to utożsamiać coś z rozsądna pewność, że identyfikator nigdy nie będzie nieumyślnie używany przez kogokolwiek do anything else

To wyjaśnia dość szczegółowo, jak to naprawdę jest bezpieczne. Aby odpowiedzieć na twoje pytanie: tak, jest wystarczająco bezpieczny.

Schematy UUID zazwyczaj używają nie tylko pseudolosowego elementu, ale także bieżącego czasu systemowego i pewnego rodzaju często unikalnego identyfikatora sprzętu, jeśli jest dostępny, takiego jak sieciowy adres MAC.

Cały sens używania UUID polega na tym, że ufasz mu, że wykona lepszą pracę polegającą na dostarczaniu unikalnego identyfikatora, niż sam byłby w stanie to zrobić. Jest to to samo uzasadnienie korzystania z biblioteki kryptograficznej innej firmy, a nie zwijania własnej. Robienie tego samemu może być przyjemniejsze, ale zazwyczaj mniej odpowiedzialny za to.

Robi to od lat. Nigdy nie wpadaj w kłopoty.

Zwykle ustawiam moje DB ' y, aby miały jedną tabelę, która zawiera wszystkie klucze i daty modyfikacji i takie. Nigdy nie napotkałem problemu z duplikatami kluczy.

Jedyną wadą jest to, że gdy piszesz kilka zapytań, aby szybko znaleźć informacje, robisz wiele kopiowania i wklejania kluczy. Nie masz już krótkich, łatwych do zapamiętania identyfikatorów.

Oto fragment testowania, aby przetestować jego unikalność. zainspirowany komentarzem @ scalabl3

Zabawne jest to, że można było wygenerować dwa z rzędu, które były identyczne, oczywiście na zadziwiającym poziomie zbiegu okoliczności, szczęścia i boskiej interwencji, ale mimo niezgłębionych szans, to nadal możliwe! : D tak, to się nie stanie. mówię tylko dla Zabawy, myśląc o tym momencie, kiedy stworzyłeś duplikat! Screenshot video! - skalabl3 20 paź '15 o 19:11

Jeśli masz szczęście, zaznacz pole wyboru, sprawdza tylko aktualnie wygenerowane identyfikatory. jeśli chcesz sprawdzić historię, pozostaw je niezaznaczone. Pamiętaj, że w pewnym momencie może zabraknąć pamięci ram, jeśli pozostawisz ją niezaznaczoną. Starałem się, aby był przyjazny dla procesora, abyś mógł szybko przerwać w razie potrzeby, po prostu ponownie naciśnij przycisk Uruchom fragment lub opuść stronę.

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

Nie wiem, czy to ma dla ciebie znaczenie, ale pamiętaj, że GUID są unikalne globalnie, ale podciągi GUID nie są.

Zgadzam się z innymi odpowiedziami. Uuid są wystarczająco bezpieczne dla prawie wszystkich praktycznych celów¹, i na pewno dla Ciebie.

Ale przypuśćmy (hipotetycznie), że nie są.

Czy istnieje lepszy system lub jakiś wzorzec, który rozwiąże ten problem?

Oto kilka podejść:

1. Użyj większego UUID. Na przykład, zamiast 128 losowych bitów, użyj 256 lub 512 or ... Każdy bit, który dodasz do UUID w stylu type-4, będzie zmniejsz prawdopodobieństwo kolizji o połowę, zakładając, że masz wiarygodne źródło entropii².

2. Twórz scentralizowaną lub rozproszoną usługę, która generuje identyfikatory uuid i rejestruje każdą wydaną przez nią usługę. Za każdym razem, gdy generuje nowy, sprawdza, czy UUID nigdy wcześniej nie został wydany. Taka usługa byłaby technicznie prosta do wdrożenia (myślę), gdybyśmy założyli, że osoby obsługujące usługę są absolutnie godne zaufania, nieskazitelny, etcetera. Niestety, nie są ... zwłaszcza, gdy istnieje możliwość ingerencji rządów. Tak więc takie podejście jest prawdopodobnie niepraktyczne i może być³ niemożliwe w prawdziwym świecie.

^{1 - gdyby unikalność uuid zadecydowała o tym, czy rakiety nuklearne zostały wystrzelone w stolicy państwa, wielu współobywateli nie byłoby przekonanych, że "prawdopodobieństwo jest bardzo niskie". Stąd moje " prawie wszystkie" Kwalifikacje.}

^{2 - A oto pytanie filozoficzne. Czy cokolwiek jest naprawdę przypadkowe? Skąd mielibyśmy wiedzieć, gdyby tak nie było? Czy wszechświat jaki znamy jest symulacją? Czy istnieje Bóg, który mógłby "poprawić" prawa fizyki, aby zmienić wynik?}

^{3 - Jeśli ktoś zna jakieś prace badawcze na ten temat, proszę o komentarz.}