UUID est-il unique?

451

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?

Jason
la source
11
Pour une valeur suffisamment grande de "assez de temps" :)
91
"Dans quelle mesure l'UUID est-il unique?" Universellement unique, je crois. ;)
Miles
29
Et à moins que vous ne prévoyiez de développer sur Vénus, un GUID devrait suffire.
skaffman
1
plus de détails et générateur ici: générateur uuid en ligne
Dave
2
"unique" signifie ne jamais entrer en collision . S'il a un potentiel de collision, ce n'est pas unique . Par conséquent, par définition, l'UUID n'est pas unique et n'est sûr que si vous êtes préparé à des collisions potentielles, indépendamment des risques de collisions. Sinon, votre programme est tout simplement incorrect. Vous pouvez dire UUID comme "presque unique" mais cela ne signifie pas qu'il est "unique".
Eonil

Réponses:

444

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 −11 ), 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 .

Martijn Pieters
la source
22
J'aime cette partie de Wikipedia: 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. Alors, quelle est la vraie chance de doublon en notant cette phrase. Nous ne pouvons pas créer de vrais nombres aléatoires sur ordinateur, n'est-ce pas?
mans
6
En fait, beaucoup de travail a été fait pour trouver des moyens d'introduire autant d'entropie ("vrais aléas", je suppose que vous pourriez l'appeler) que possible dans les API de nombres aléatoires. Voir en.wikipedia.org/wiki/Entropy_%28computing%29
broofa
4
C'est en fait une probabilité de collision plus élevée que je ne l'avais imaginé. Paradoxe d'anniversaire, je suppose.
Cameron
Pouvez-vous confirmer que l'utilisation de l'UUID serait sûre entre les exécutions d'une application? (par exemple un script python)
George Sp
excellent exemple ...: D
NuttLoose
151

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.

rêne
la source
185
Mais seulement après avoir utilisé jusqu'à 256 exaoctets de stockage pour ces ID.
Bob Aman
16
Ce qui est drôle, c'est que vous pourriez en générer 2 d'affilée qui étaient 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 le plaisir de penser à ce moment où vous avez créé un doublon! Capture d'écran vidéo!
scalabl3
4
L'unicité est-elle uniquement due au hasard? Ou y a-t-il d'autres facteurs? (par exemple, horodatage, ip, etc.)
Weishi Zeng
15
@TheTahaan Ce n'est pas ce que signifie le hasard. Cela ne signifie pas «totalement imprévisible» - généralement, ils suivent une sorte de distribution. Si vous lancez 10 pièces, les chances d'obtenir 2 têtes, suivies de 3 queues, puis de 5 têtes, sont assez faibles (2 ^ -10, environ 0,001). C'est vraiment aléatoire, mais nous pouvons absolument savoir la chance d'obtenir un résultat particulier. Nous ne pouvons tout simplement pas dire à l'avance si cela se produira.
Richard Rast
5
Juste pour expliquer ce que cette implémentation a fait de mal, ils utilisent un UUID version 1, qui s'appuie sur une combinaison d'horodatage et d'adresse mac pour son caractère unique. Cependant, si vous générez des UUID assez rapidement, l'horodatage ne sera pas encore incrémenté. Dans ce scénario, votre algorithme de génération d'UUID est censé suivre le dernier horodatage utilisé et l'incrémenter de 1. Ils ont clairement échoué à franchir cette étape. Cependant, tous les UUID de la version 1 correctement générés par la même machine sur une courte période présenteront des similitudes évidentes, mais devraient toujours être uniques.
Bob Aman
103

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.

Hoylen
la source
1
La valeur par défaut d'un UUID version 1 présente de graves problèmes lorsqu'ils sont générés par le même serveur pour de nombreuses personnes. L'UUID de la version 4 est ma valeur par défaut car vous pouvez rapidement écrire quelque chose pour en générer un dans n'importe quelle langue ou plate-forme (y compris javascript).
Justin Bozonier
1
@Hoylen Bien expliqué! mais est-ce beaucoup d'exagération nécessaire?
Dinoop paloli
1
En théorie , il est uniquement attribué par le fabricant.
OrangeDog
4
Il n'est pas nécessaire de générer 10 millions d'UUID de version 1 en une seconde pour rencontrer un doublon; il faut simplement générer un lot de 16 384 UUID en l'espace d'un seul "tick" afin de déborder le numéro de séquence. J'ai vu cela se produire avec une implémentation qui reposait, naïvement, sur une source d'horloge qui (1) avait une granularité de niveau μs, et (2) n'était pas garantie d'être monotone (les horloges système ne le sont pas). Faites attention au code de génération UUID que vous utilisez et soyez particulièrement prudent avec les générateurs UUID temporels. Ils sont difficiles à obtenir correctement, alors soumettez-les à des tests de charge avant de les utiliser.
Mike Strobel
Le laps de temps entre les UUID v4 générés pourrait-il conduire à plus de probabilités de collision? Je veux dire dans une application à fort trafic, supposons que des milliers de uuides soient générés en même temps, y a-t-il plus de chances de collision que si la même quantité de uuids était générée sur une période de temps relativement plus longue?
Jonathan
18

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.

Mat
la source
14

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.

Dave Vogt
la source
9

Je suis d'accord avec les autres réponses. Les UUID sont suffisamment sûrs pour presque toutes les fins pratiques 1 , 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 .

  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 3 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.

Stephen C
la source
Je veux juste souligner que la méthode numéro 2 défait fondamentalement le but principal de l'utilisation de l'UUID et vous pourriez tout aussi bien utiliser un ID numéroté classique à ce stade.
Petr Vnenk
Je ne suis pas d'accord. Le défaut des identifiants numérotés séquentiels est qu'ils sont trop faciles à deviner. Vous devriez être en mesure d'implémenter la méthode 2 d'une manière qui rend les UUID difficiles à deviner.
Stephen C
8

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.

Parappa
la source
6

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.

Posthuma
la source
5

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

Tschallacka
la source
Essayez avec un UUID RFC 4122 version 1 (date-heure et adresse MAC).
zaph
Il était très rapide jusqu'à une récente mise à jour de Chrome. J'avais remarqué la même chose il y a 4 semaines.
Tschallacka
3

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 .

Grant Wagner
la source
1
Gardez à l'esprit que la référence liée ici parle des UUID de la version 1 (qui prennent des informations sur l'ordinateur générateur, etc. dans l'ID). La plupart des autres réponses parlent de la version 4 (qui sont totalement aléatoires). L'article Wikipedia lié ci-dessus en.wikipedia.org/wiki/Universally_unique_identifier explique les différents types d'UUID.
kratenko
3

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)
perdu
la source
En fait, je suppose que cela suppose un emballage à 100%, alors je devrais peut-être ajouter un facteur à cela!
perdu le