Comment unique est UUID?
https://stackoverflow.com/questions/1155008
-
18-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Comment est-il sûr d'utiliser UUID pour identifier 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 que donné assez de temps, il finit par répéter elle-même, par hasard pur. Y at-il un meilleur système ou un modèle d'un certain type pour remédier à ce problème?
La solution
Très sûr:
le risque annuel d'une personne donnée étant frappé par une météorite est estimée à une chance sur 17 milliards, ce qui signifie que la probabilité est d'environ ,00000000006 (6 × 10 -11 ), ce qui correspond à la cote de créer quelques dizaines de billions de UUID en un an et ayant une dupliquer. En d'autres termes, seulement après avoir généré 1 milliard UUID tous seconde pour les 100 prochaines années, la probabilité de créer un seul en double serait d'environ 50%.
Caveat:
Cependant, ces probabilités tiennent que lorsque les UUID sont générés en utilisant l'entropie suffisante. Dans le cas contraire, la probabilité de doublons pourrait être beaucoup plus élevé, étant donné que la dispersion statistique pourrait être plus faible. Où identificateurs uniques sont requis pour distribuer applications, de sorte que UUID ne se heurtent pas même lorsque les données de nombreux les appareils sont fusionnées, le caractère aléatoire des graines et des générateurs utilisés sur chaque appareil doit être fiable pour la vie de l'application. Où cela est impossible, RFC4122 recommande d'utiliser une variante d'espace de noms à la place.
Source: Aléatoire probabilité UUID de doublons section de l'article de Wikipédia sur les identificateurs uniques (universellement lien conduit à une révision à partir de Décembre 2016 avant l'édition retravaillé la section).
Voir aussi la section en cours sur le même sujet sur le même article identifiant unique universel, collisions .
Autres conseils
Si par « donné assez de temps » vous dire 100 ans et vous les créer à raison d'un milliard par seconde, alors oui, vous avez une chance de 50% d'avoir une collision au bout de 100 ans.
Il y a plus d'un type de UUID, donc « comment sûr » dépend de quel type (dont les spécifications UUID appellent « version ») que vous utilisez.
-
La version 1 est le temps en fonction plus l'adresse MAC UUID. 128 bits contient 48 bits pour l'adresse MAC de la carte réseau (qui est unique fixées par le fabricant) et une horloge de 60 bits avec une résolution de 100 nanosecondes. Cette horloge drape dans 3603 AD pour ces UUID sont sûrs au moins jusque-là (sauf si vous avez besoin de plus de 10 millions de nouveaux UUID par seconde ou quelqu'un cloner votre carte réseau). Je dis « au moins » parce que l'horloge commence à 15 Octobre 1582, de sorte que vous avez environ 400 ans après l'horloge enveloppe avant qu'il y ait même une petite possibilité de duplications.
-
La version 4 est le nombre aléatoire UUID. Il y a six bits fixes et le reste du UUID est de 122 bits de caractère aléatoire. Voir Wikipedia ou d'autres analyses qui décrivent la façon dont très peu probable qu'un double est.
-
Version 3 est utilise MD5 et Version 5 utilise SHA-1 pour créer ces 122 bits, au lieu d'un générateur de nombres aléatoires ou pseudo-aléatoires. Donc, en termes de sécurité, il est comme la version 4 étant une question statistique (aussi longtemps que vous assurez-vous que l'algorithme de hachage est le traitement est toujours unique).
-
La version 2 est similaire à la version 1, mais avec une plus petite horloge il va enrouler autour de beaucoup plus tôt. Mais depuis la version 2 UUID sont pour DCE, vous ne devraient pas utiliser ces derniers.
Donc, pour tous les problèmes pratiques qu'ils sont sûrs. Si vous êtes mal à l'aise avec le laisser jusqu'à probabilités (par exemple, vous êtes le genre de personne inquiète de la terre se détruit par un gros astéroïde dans votre vie), assurez-vous que vous utilisez une version 1 UUID et il est garanti d'être unique ( dans votre vie, à moins que vous envisagez de vivre passé 3603 AD).
Alors, pourquoi ne pas tout le monde utilise simplement la version 1 UUID? C'est parce que la version 1 UUID révèlent l'adresse MAC de la machine, il a été généré sur et ils peuvent être prévisibles -. Deux choses qui pourraient avoir des répercussions sur la sécurité pour l'application en utilisant les UUID
La réponse à cela peut dépendre en grande partie de la version UUID.
De nombreux générateurs UUID utilisent une version 4 nombre aléatoire. Cependant, beaucoup d'entre eux utilisent un pseudo générateur de nombres aléatoires pour les générer.
Si un mal tête de série PRNG avec une petite période est utilisée pour générer l'UUID je dirais que ce n'est pas très sûr du tout.
Par conséquent, il est aussi sûr que les algorithmes utilisés pour générer.
Du côté de la médaille, si vous connaissez la réponse à ces questions, alors je pense une version 4 UUID devrait être très sûr à utiliser. En fait je l'utilise pour identifier les blocs sur un système de fichiers de bloc réseau et jusqu'à présent ne l'ai pas eu un choc.
Dans mon cas, le PRNG j'utilise est un twister Mersenne et je fais attention à la façon dont il est tête de série qui est à partir de plusieurs sources, y compris / dev / urandom. Mersenne Twister a une période de 2 ^ 19937 -. 1. Ça va être un très très longtemps avant que je vois un UUID de répétition
Je cite Wikipedia :
Ainsi, tout le monde peut créer un UUID et l'utilisation d'identifier quelque chose avec confiance raisonnable que la identifiant ne sera jamais sans le vouloir utilisé par quiconque pour quoi que ce soit d'autre
Il va à expliquer en détail assez bon sur la façon dont il est réellement sans danger. Donc, pour répondre à votre question. Oui, il est assez sûr
régimes UUID utilisent généralement non seulement un élément pseudo-aléatoire, mais aussi le temps de système actuel, et une sorte d'identité matérielle souvent unique si elle est disponible, comme une adresse MAC du réseau.
Le point entier d'utiliser UUID est que vous faites confiance pour faire un meilleur travail de fournir un identifiant unique que vous ne vous serait en mesure de le faire. C'est la même raison d'être à l'aide d'une bibliothèque de cryptographie 3e partie plutôt que de rouler vos propres. Faire vous-même peut être plus amusant, mais il est généralement moins responsable de le faire.
fais depuis des années. Ne faites jamais fonctionner un problème.
Je habituellement mis en place pour avoir une table de mon DB qui contient toutes les clés et les dates modifiées et autres. Je n'ai pas rencontré un problème des clés en double jamais.
Le seul inconvénient est qu'il a lorsque vous écrivez des requêtes pour trouver des informations rapidement vous faites beaucoup de copier-coller des clés. Vous n'avez pas court facile à retenir ids plus.
Voici un extrait de test pour vous de le tester est uniquenes. inspiré par le commentaire de @ scalabl3
Le plus drôle est, vous pouvez générer 2 dans une rangée qui étaient identiques, bien sûr à des niveaux ahurissants de hasard, la chance et l'intervention divine, mais malgré les chances insondables, il est toujours possible! : D Oui, il ne se produira pas. dire simplement pour l'amusement de penser à ce moment où vous avez créé un doublon! vidéo Capture d'écran! - scalabl3 20 octobre '15 à 19h11
Si vous vous sentez chanceux, cochez la case, il vérifie que les id actuellement générés de. Si vous souhaitez un chèque de l'histoire, laissez sans contrôle. S'il vous plaît noter que vous pourriez manquer de RAM à un moment donné si vous le laissez sans contrôle. J'ai essayé de le rendre cpu convivial vous pouvez donc annuler rapidement en cas de besoin, appuyez simplement sur le bouton extrait de l'exécution à nouveau ou quitter 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 <baagoe@baagoe.com>, 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 <baagoe@baagoe.com>, 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 suis d'accord avec les autres réponses. UUID sont suffisamment en sécurité à des fins presque toutes les pratiques 1 , et certainement pour le vôtre.
Mais supposons (hypothétiquement) qu'ils ne sont pas.
Y at-il un meilleur système ou un modèle d'un certain type pour remédier à ce problème?
Voici quelques approches:
-
Utilisez un plus grand UUID. Par exemple, au lieu d'un 128 bits aléatoires, utilisez 256 ou 512 ou ... Chaque bit que vous ajoutez à un UUID de style de type 4 permettra de réduire la probabilité d'une collision d'un demi, en supposant que vous avez une source fiable d'entropie < sup> 2 .
-
Construire un service centralisé ou distribué qui génère UUID et enregistre chacun qu'il n'a jamais émis. Chaque fois qu'il génère un nouveau, il vérifie que le UUID n'a jamais été publié auparavant. Un tel service serait straight-forward technique à mettre en œuvre (je pense) si nous supposons que les gens qui dirigent le service étaient absolument digne de confiance, incorruptibles, etcetera. Malheureusement, ils ne sont pas ... surtout quand il y a la possibilité de gouvernements importuns. Ainsi, cette approche est probablement peu pratique, et peut être 3 impossible dans le monde réel.
1 - Si l'unicité de UUID déterminer si des missiles nucléaires se sont lancés à la capitale de votre pays, beaucoup de vos concitoyens ne serait pas convaincu par « la probabilité est extrêmement faible ». D'où ma qualification "presque tous".
2 - Et voici une question philosophique pour vous. Quelque chose ne jamais vraiment au hasard? Comment pourrions-nous savoir si ce n'était pas? L'univers que nous connaissons une simulation? Y at-il un Dieu qui pourrait théoriquement « modifier » les lois de la physique pour modifier un résultat?
3 -. Si quelqu'un connaît des documents de recherche sur ce problème, s'il vous plaît commenter
Je ne sais pas si cela est important pour vous, mais gardez à l'esprit que GUIDs sont uniques au monde, mais de sous-chaînes GUIDs ne sont pas .
