UUID est-il unique?

Dans quelle mesure est-il sûr d'utiliser UUID pour identifier de manière unique quelque chose (je l'utilise pour les fichiers téléchargés sur le serveur)? Si je comprends bien, il est basé sur des nombres aléatoires. Cependant, il me semble qu'avec suffisamment de temps, il finirait par se répéter, par pur hasard. Existe-t-il un meilleur système ou un modèle quelconque pour atténuer ce problème?

Très sûr:

le risque annuel qu'une personne donnée soit touchée par une météorite est estimé à une chance sur 17 milliards, ce qui signifie que la probabilité est d'environ 0,0000000000006 (6 × 10 ⁻¹¹ ), ce qui équivaut à la probabilité de créer quelques dizaines de milliers de milliards d'UUID. en un an et en avoir un double. En d'autres termes, seulement après avoir généré 1 milliard d'UUID par seconde pendant les 100 prochaines années, la probabilité de créer un seul doublon serait d'environ 50%.

Caveat:

Cependant, ces probabilités ne tiennent que lorsque les UUID sont générés en utilisant une entropie suffisante. Sinon, la probabilité de doublons pourrait être considérablement plus élevée, car la dispersion statistique pourrait être plus faible. Lorsque des identifiants uniques sont requis pour les applications distribuées, afin que les UUID ne se heurtent pas même lorsque les données de nombreux appareils sont fusionnées, le caractère aléatoire des germes et des générateurs utilisés sur chaque appareil doit être fiable pour la durée de vie de l'application. Lorsque cela n'est pas possible, la RFC4122 recommande d'utiliser une variante d'espace de noms à la place.

Source: section Probabilité de doublons de l'UUID aléatoire de l'article de Wikipédia sur les identificateurs uniques (lien Universellement conduit à une révision à partir de Décembre 2016 avant l' édition retravaillé la section).

Voir également la section actuelle sur le même sujet dans le même article d'identifiant universel unique, Collisions .

Si "donner suffisamment de temps" signifie 100 ans et que vous les créez à un rythme d'un milliard par seconde, alors oui, vous avez 50% de chances d'avoir une collision après 100 ans.

Il existe plusieurs types d'UUID. Par conséquent, "la sécurité" dépend du type (que les spécifications de l'UUID appellent "version") que vous utilisez.

• La version 1 est l'UUID basé sur le temps et l'adresse MAC. Les 128 bits contiennent 48 bits pour l'adresse MAC de la carte réseau (qui est uniquement attribuée par le fabricant) et une horloge de 60 bits avec une résolution de 100 nanosecondes. Cette horloge s'enroule dans 3603 AD afin que ces UUID soient en sécurité au moins jusque-là (à moins que vous n'ayez besoin de plus de 10 millions de nouveaux UUID par seconde ou que quelqu'un clone votre carte réseau). Je dis "au moins" parce que l'horloge commence au 15 octobre 1582, vous avez donc environ 400 ans après que l'horloge se termine avant qu'il y ait même une petite possibilité de duplication.

• La version 4 est l'UUID à nombre aléatoire. Il y a six bits fixes et le reste de l'UUID est de 122 bits d'aléatoire. Voir Wikipédia ou une autre analyse décrivant la probabilité d'un doublon.

• La version 3 utilise MD5 et la version 5 utilise SHA-1 pour créer ces 122 bits, au lieu d'un générateur de nombres aléatoire ou pseudo-aléatoire. Donc, en termes de sécurité, c'est comme si la version 4 était un problème statistique (tant que vous vous assurez que ce que l'algorithme de résumé traite est toujours unique).

• La version 2 est similaire à la version 1, mais avec une horloge plus petite, elle se terminera beaucoup plus tôt. Mais comme les UUID de la version 2 sont pour DCE, vous ne devriez pas les utiliser.

Donc, pour tous les problèmes pratiques, ils sont sûrs. Si vous n'êtes pas à l'aise de le laisser aux probabilités (par exemple, vous êtes le type de personne inquiète de la destruction de la terre par un gros astéroïde au cours de votre vie), assurez-vous simplement d'utiliser un UUID version 1 et il est garanti d'être unique ( au cours de votre vie, sauf si vous prévoyez de vivre après 3603 après JC).

Alors pourquoi tout le monde n'utilise-t-il pas simplement les UUID de la version 1? En effet, les UUID de la version 1 révèlent l'adresse MAC de la machine sur laquelle ils ont été générés et ils peuvent être prévisibles - deux choses qui pourraient avoir des implications en termes de sécurité pour l'application utilisant ces UUID.

La réponse à cela peut dépendre largement de la version de l'UUID.

De nombreux générateurs UUID utilisent un nombre aléatoire de la version 4. Cependant, beaucoup d'entre eux utilisent Pseudo un générateur de nombres aléatoires pour les générer.

Si un PRNG mal ensemencé avec une petite période est utilisé pour générer l'UUID, je dirais que ce n'est pas très sûr du tout.

Par conséquent, il n'est aussi sûr que les algorithmes utilisés pour le générer.

D'un autre côté, si vous connaissez la réponse à ces questions, je pense qu'un uuid de la version 4 devrait être très sûr à utiliser. En fait, je l'utilise pour identifier des blocs sur un système de fichiers de blocs réseau et jusqu'à présent, il n'y a pas eu de conflit.

Dans mon cas, le PRNG que j'utilise est un twister mersenne et je fais attention à la façon dont il est semé, qui provient de plusieurs sources, dont / dev / urandom. Mersenne twister a une période de 2 ^ 19937 - 1. Ça va être très très long avant de voir une répétition uuid.

Citation de Wikipedia :

Ainsi, n'importe qui peut créer un UUID et l'utiliser pour identifier quelque chose avec une confiance raisonnable que l'identifiant ne sera jamais utilisé involontairement par quiconque pour autre chose

Il explique en détail assez bien à quel point il est sûr. Donc, pour répondre à votre question: oui, c'est assez sûr.

Je suis d'accord avec les autres réponses. Les UUID sont suffisamment sûrs pour presque toutes les fins pratiques ¹ , et certainement pour le vôtre.

Mais supposons (hypothétiquement) qu'ils ne le soient pas.

Existe-t-il un meilleur système ou un modèle quelconque pour atténuer ce problème?

Voici quelques approches:

1. Utilisez un UUID plus grand. Par exemple, au lieu de 128 bits aléatoires, utilisez 256 ou 512 ou ... Chaque bit que vous ajoutez à un UUID de type 4 réduira de moitié la probabilité d'une collision, en supposant que vous avez une source fiable d'entropie ² .

2. Créez un service centralisé ou distribué qui génère des UUID et enregistre chacun de ceux qu'il a jamais émis. Chaque fois qu'il en génère un nouveau, il vérifie que l'UUID n'a jamais été émis auparavant. Un tel service serait techniquement simple à mettre en œuvre (je pense) si nous supposions que les personnes qui géraient le service étaient absolument dignes de confiance, incorruptibles, etc. Malheureusement, ils ne le sont pas ... surtout lorsqu'il y a la possibilité que les organisations de sécurité des gouvernements interfèrent. Donc, cette approche est probablement impraticable, et peut-être ³ impossible dans le monde réel.

^{1 - Si l'unicité des UUID déterminait si des missiles nucléaires étaient lancés dans la capitale de votre pays, beaucoup de vos concitoyens ne seraient pas convaincus par "la probabilité est extrêmement faible". D'où ma qualification de "presque tous".}

^{2 - Et voici une question philosophique pour vous. Quelque chose est-il vraiment vraiment aléatoire? Comment saurions-nous si ce n'était pas le cas? L'univers tel que nous le connaissons est-il une simulation? Y a-t-il un Dieu qui pourrait "modifier" les lois de la physique pour modifier un résultat?}

^{3 - Si quelqu'un connaît des articles de recherche sur ce problème, veuillez commenter.}

Les schémas UUID utilisent généralement non seulement un élément pseudo-aléatoire, mais aussi l'heure actuelle du système et une sorte d'ID matériel souvent unique si disponible, comme une adresse MAC réseau.

L'intérêt de l'utilisation de l'UUID est que vous lui faites confiance pour mieux fournir un ID unique que vous ne pourriez le faire vous-même. C'est la même raison derrière l'utilisation d'une bibliothèque de cryptographie tierce plutôt que de rouler la vôtre. Le faire vous-même peut être plus amusant, mais c'est généralement moins responsable de le faire.

Je le fais depuis des années. Ne rencontrez jamais de problème.

J'ai l'habitude de configurer mes bases de données pour avoir une table qui contient toutes les clés et les dates modifiées et autres. Je n'ai jamais rencontré de problème de clés en double.

Le seul inconvénient est que lorsque vous écrivez des requêtes pour trouver rapidement des informations, vous faites beaucoup de copier-coller des clés. Vous n'avez plus les identifiants courts et faciles à retenir.

Voici un extrait de test pour tester ses uniquenes. inspiré par le commentaire de @ scalabl3

Ce qui est drôle, c'est que vous pourriez en générer 2 d'affilée qui sont identiques, bien sûr à des niveaux ahurissants de coïncidence, de chance et d'intervention divine, mais malgré les chances insondables, c'est toujours possible! : D Oui, cela n'arrivera pas. dire juste pour l'amusement de penser à ce moment où vous avez créé un doublon! Capture d'écran vidéo! - scalabl3 20 octobre 15 à 19:11

Si vous vous sentez chanceux, cochez la case, il ne vérifie que les identifiants actuellement générés. Si vous souhaitez une vérification de l'historique, ne la cochez pas. Veuillez noter que vous risquez de manquer de RAM à un moment donné si vous ne le cochez pas. J'ai essayé de le rendre convivial pour le processeur afin que vous puissiez abandonner rapidement en cas de besoin, appuyez simplement sur le bouton d'exécution de l'extrait de code ou quittez la page.

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

Je ne sais pas si cela vous importe, mais gardez à l'esprit que les GUID sont globalement uniques, mais pas les sous-chaînes de GUID .

Pour UUID4, je fais en sorte qu'il y ait à peu près autant de pièces d'identité qu'il y a de grains de sable dans une boîte en forme de cube avec des côtés de 360 ​​000 km de long. C'est une boîte avec des côtés ~ 2 1/2 fois plus longs que le diamètre de Jupiter.

Travailler pour que quelqu'un puisse me dire si j'ai foiré des unités:

• volume de grain de sable 0,00947 mm ^ 3 ( gardien )
• UUID4 a 122 bits aléatoires -> 5.3e36 valeurs possibles ( wikipedia )
• volume de ce nombre de grains de sable = 5,0191e34 mm ^ 3 ou 5,0191e + 25m ^ 3
• longueur latérale de la boîte cubique avec ce volume = 3,69E8m ou 369 000 km
• diamètre de Jupiter: 139 820 km (google)