Jak wyjątkowy jest UUID?

Jak bezpieczne jest używanie UUID do jednoznacznej identyfikacji czegoś (używam tego do plików przesyłanych na serwer)? Jak rozumiem, opiera się na liczbach losowych. Wydaje mi się jednak, że biorąc pod uwagę wystarczającą ilość czasu, w końcu powtórzy to samo, zupełnie przypadkiem. Czy istnieje lepszy system lub jakiś wzorzec łagodzący ten problem?

Bardzo bezpieczny:

roczne ryzyko uderzenia meteorytu w osobę szacuje się na jedną szansę na 17 miliardów, co oznacza, że ​​prawdopodobieństwo wynosi około 0,00000000006 (6 × ^10-11 ), co odpowiada prawdopodobieństwu wytworzenia kilkudziesięciu bilionów UUID za rok i posiadanie jednego duplikatu. Innymi słowy, tylko po wygenerowaniu 1 miliarda UUID co sekundę przez następne 100 lat prawdopodobieństwo utworzenia tylko jednego duplikatu wyniesie około 50%.

Zastrzeżenie:

Jednak te prawdopodobieństwa istnieją tylko wtedy, gdy UUID są generowane przy użyciu wystarczającej entropii. W przeciwnym razie prawdopodobieństwo duplikatów może być znacznie wyższe, ponieważ dyspersja statystyczna może być mniejsza. Tam, gdzie wymagane są unikalne identyfikatory dla aplikacji rozproszonych, aby identyfikatory UUID nie kolidowały nawet po połączeniu danych z wielu urządzeń, losowość nasion i generatorów używanych na każdym urządzeniu musi być niezawodna przez cały okres użytkowania aplikacji. Tam, gdzie nie jest to możliwe, RFC4122 zaleca stosowanie zamiast tego wariantu przestrzeni nazw.

Źródło: Losowe prawdopodobieństwo UUID duplikatów sekcji artykułu z Wikipedii na temat Uniwersalnie unikatowych identyfikatorów (link prowadzi do wersji z grudnia 2016 r. Przed edycją przerobił sekcję).

Zobacz także bieżącą sekcję na ten sam temat w tym samym artykule o unikalnym identyfikatorze uniwersalnym, Kolizje .

Jeśli przez „wystarczająco dużo czasu” masz na myśli 100 lat i tworzysz je z szybkością miliarda na sekundę, to tak, masz 50% szansy na kolizję po 100 latach.

Istnieje więcej niż jeden typ identyfikatora UUID, więc „jak bezpieczny” zależy od typu (którego specyfikacje UUID nazywają „wersją”), którego używasz.

• Wersja 1 to UUID oparty na czasie plus adres MAC. 128-bitowy zawiera 48-bitowy adres MAC karty sieciowej (który jest jednoznacznie przypisany przez producenta) i 60-bitowy zegar o rozdzielczości 100 nanosekund. Ten zegar jest zawijany w 3603 AD, więc te UUID są bezpieczne przynajmniej do tego czasu (chyba że potrzebujesz więcej niż 10 milionów nowych UUID na sekundę lub ktoś sklonuje twoją kartę sieciową). Mówię „przynajmniej”, ponieważ zegar zaczyna się 15 października 1582 r., Więc masz około 400 lat po tym, jak zegar się zawija, zanim istnieje nawet niewielka możliwość powielania.

• Wersja 4 to losowy numer UUID. Jest sześć ustalonych bitów, a reszta identyfikatora UUID ma 122 bitów losowości. Zobacz Wikipedię lub inną analizę opisującą, jak mało prawdopodobne jest duplikowanie.

• Wersja 3 wykorzystuje MD5, a wersja 5 używa SHA-1 do tworzenia tych 122-bitów zamiast generatora liczb losowych lub pseudolosowych. Jeśli chodzi o bezpieczeństwo, to jest tak, jakby wersja 4 była kwestią statystyczną (o ile upewnisz się, że algorytm przetwarzający jest zawsze unikalny).

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

Są więc bezpieczne dla wszystkich praktycznych problemów. Jeśli nie czujesz się komfortowo, pozostawiając to prawdopodobieństwu (np. Jesteś osobą, która martwi się, że Ziemia zostanie zniszczona przez dużą asteroidę w swoim życiu), po prostu upewnij się, że używasz UUID w wersji 1, a gwarantuje to, że będzie unikalna ( za twojego życia, chyba że planujesz żyć po 3603 AD).

Dlaczego więc nie wszyscy po prostu używają identyfikatorów UUID w wersji 1? Jest tak, ponieważ identyfikatory UUID w wersji 1 ujawniają adres MAC maszyny, na której zostały wygenerowane, i można je przewidzieć - dwie rzeczy, które mogą mieć wpływ na bezpieczeństwo aplikacji korzystającej z tych identyfikatorów UUID.

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

Wiele generatorów UUID używa losowej liczby w wersji 4. Jednak wiele z nich używa Pseudo a Random Number Generator do ich generowania.

Jeśli do wygenerowania UUID zostanie użyty źle rozstawiony PRNG z krótkim okresem, powiedziałbym, że wcale nie jest zbyt bezpieczny.

Dlatego jest tak bezpieczny, jak algorytmy użyte do jego wygenerowania.

Z drugiej strony, jeśli znasz odpowiedź na te pytania, to uważam, że uuid w wersji 4 powinien być bardzo bezpieczny w użyciu. W rzeczywistości używam go do identyfikowania bloków w sieciowym systemie plików i do tej pory nie doszło do konfliktu.

W moim przypadku PRNG, którego używam, jest twisterem Mersenne i uważam na sposób, w jaki jest on rozprowadzany z wielu źródeł, w tym / dev / urandom. Mersenne Twister ma okres 2 ^ 19937 - 1. Minie bardzo dużo czasu, zanim zobaczę powtarzający się uuid.

Cytowanie z Wikipedii :

Zatem każdy może utworzyć UUID i użyć go do zidentyfikowania czegoś z uzasadnioną pewnością, że identyfikator nigdy nie zostanie przypadkowo wykorzystany przez nikogo do niczego innego

Dalej wyjaśnia dość dokładnie, jak naprawdę jest bezpieczny. Aby odpowiedzieć na twoje pytanie: Tak, jest wystarczająco bezpieczny.

Zgadzam się z innymi odpowiedziami. UUID są wystarczająco bezpieczne dla prawie wszystkich praktycznych celów ¹ , a na pewno dla twojego.

Załóżmy jednak (hipotetycznie), że nie są.

Czy istnieje lepszy system lub jakiś wzorzec łagodzący ten problem?

Oto kilka podejść:

1. Użyj większego UUID. Na przykład zamiast 128 losowych bitów użyj 256 lub 512 lub ... Każdy bit dodany do UUID typu 4 zmniejszy prawdopodobieństwo kolizji o połowę, zakładając, że masz wiarygodne źródło entropii ² .

2. Zbuduj scentralizowaną lub rozproszoną usługę, która generuje UUID i rejestruje każdą wydaną przez siebie. Za każdym razem, gdy generuje nowy, sprawdza, czy UUID nigdy wcześniej nie był wydawany. Taka usługa byłaby technicznie prosta do wdrożenia (myślę), gdybyśmy przyjęli, że osoby prowadzące tę usługę są absolutnie godne zaufania, nieprzekupne itp. Niestety nie są ... szczególnie, gdy istnieje możliwość ingerencji rządowych organizacji bezpieczeństwa. Tak, to podejście jest prawdopodobnie niepraktyczne i może być ³ niemożliwe w realnym świecie.

^{1 - Jeśli wyjątkowość UUID określi, czy rakiety nuklearne zostały wystrzelone w stolicy kraju, wielu współobywateli nie przekonałoby „prawdopodobieństwo bardzo niskie”. Stąd moje „prawie wszystkie” kwalifikacje.}

^{2 - A oto pytanie filozoficzne. Czy coś jest naprawdę przypadkowego? 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 „ulepszyć” prawa fizyki, aby zmienić wynik?}

^{3 - Jeśli ktoś zna jakieś prace badawcze dotyczące tego problemu, prosimy o komentarz.}

Schematy UUID generalnie wykorzystują nie tylko element pseudolosowy, ale także bieżący czas systemowy i jakiś często unikalny identyfikator sprzętu, jeśli jest dostępny, taki jak adres MAC sieci.

Cały sens używania UUID polega na tym, że ufasz, że wykonasz lepszą robotę, dostarczając unikalny identyfikator, niż sam byłbyś w stanie zrobić. Jest to to samo uzasadnienie, co do korzystania z zewnętrznej biblioteki kryptograficznej zamiast tworzenia własnej. Robienie tego samemu może być przyjemniejsze, ale zazwyczaj jest to mniej odpowiedzialne.

Robiłem to od lat. Nigdy nie napotykaj problemu.

Zazwyczaj konfiguruję swoje bazy danych, aby mieć jedną tabelę, która zawiera wszystkie klucze i zmodyfikowane daty i tak dalej. Nigdy nie spotkałem się z problemem zduplikowanych kluczy.

Jedyną wadą jest to, że kiedy piszesz zapytania, aby szybko znaleźć informacje, dużo kopiujesz i wklejasz klucze. Nie masz już łatwego do zapamiętania identyfikatora.

Oto fragment testowy umożliwiający przetestowanie jego unikatowości. zainspirowany komentarzem @ scalabl3

Zabawne jest to, że można wygenerować 2 z rzędu, które były identyczne, oczywiście przy zadziwiającym poziomie zbiegów okoliczności, szczęścia i boskiej interwencji, ale pomimo niezgłębionych szans, wciąż jest to możliwe! : D Tak, to się nie stanie. po prostu dla zabawy, gdy pomyślałeś o tym momencie, kiedy stworzyłeś duplikat! Zrzut ekranu wideo! - scalabl3 20 października 2015 o 19:11

Jeśli masz szczęście, zaznacz pole wyboru, sprawdza tylko aktualnie wygenerowany identyfikator. Jeśli chcesz sprawdzić historię, pozostaw ją niezaznaczoną. Uwaga: w pewnym momencie możesz zabraknąć pamięci RAM, jeśli nie zaznaczysz jej. Próbowałem uczynić go przyjaznym dla procesora, abyś mógł w razie potrzeby szybko przerwać, po prostu naciśnij ponownie przycisk fragmentu uruchom 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 ma to dla Ciebie znaczenie, ale pamiętaj, że identyfikatory GUID są globalnie unikalne, ale podciągi GUID nie są .

W przypadku UUID4 sprawiam, że jest mniej więcej tyle samo dowodów, ile ziaren piasku w pudełku w kształcie sześcianu o bokach długości 360 000 km. To pudełko o bokach ~ 2 1/2 razy dłuższych niż średnica Jowisza.

Działa, aby ktoś mógł mi powiedzieć, czy zepsułem jednostki:

• objętość ziarna piasku 0,00947 mm ^ 3 ( Guardian )
• UUID4 ma 122 losowe bity -> 5.3e36 możliwych wartości ( wikipedia )
• objętość tak wielu ziaren piasku = 5,0191e34 mm ^ 3 lub 5,0191e + 25 m ^ 3
• długość boku sześciennej skrzynki o tej objętości = 3,69E8m lub 369 000 km
• średnica Jowisza: 139 820 km (google)