Collisions UUID [fermé]

Quelqu'un a-t-il réellement mené des recherches sur la probabilité de collisions d'UUID, en particulier avec des UUID de version 4 (aléatoires), étant donné que les générateurs de nombres aléatoires que nous utilisons ne sont pas vraiment aléatoires et que nous pourrions avoir des dizaines ou des centaines de machines identiques exécutant le même code générer des UUID?

Mes collègues considèrent que le test de collision UUID est une perte de temps totale, mais je mets toujours du code pour récupérer une exception de clé dupliquée dans la base de données et réessayer avec un nouvel UUID. Mais cela ne va pas résoudre le problème si l'UUID provient d'un autre processus et fait référence à un objet réel.

Wikipedia a quelques détails:

http://en.wikipedia.org/wiki/Universally_unique_identifier

http://en.wikipedia.org/wiki/Universally_unique_identifier#Random_UUID_probability_of_duplicates

Mais la probabilité ne tient que si les bits sont parfaitement aléatoires. Cependant, la RFC http://tools.ietf.org/html/rfc4122#page-14 liée dans l’autre réponse définit ceci pour la version 4:

"4.4. [...] La version 4 de l'UUID est conçue pour générer des UUID à partir de nombres véritablement aléatoires ou pseudo-aléatoires. [...] Régler tous les autres bits sur des valeurs choisies de manière aléatoire (ou pseudo-aléatoire)."

Cela permet à peu près tout, du générateur aléatoire xkcd http://xkcd.com/221/ à un périphérique matériel utilisant le bruit quantique. Les considérations de sécurité dans le RFC:

"6. Les applications distribuées générant des UUID sur divers hôtes doivent pouvoir accepter de recourir à la source de nombres aléatoires sur tous les hôtes. Si cela n'est pas réalisable, la variante d'espace de noms doit être utilisée."

Je lis ceci comme suit: Vous êtes seul. Vous êtes responsable de votre générateur aléatoire au sein de votre propre application, mais ceci et tout le reste est basé sur la confiance. Si vous ne faites pas confiance à votre propre capacité à comprendre correctement et à utiliser le générateur aléatoire de votre choix, il est alors judicieux de vérifier les collisions. Si vous ne faites pas confiance au programmeur des autres processus, vérifiez les collisions ou utilisez une version différente de l'UUID.

Vous devez certainement détecter si une collision se produit et votre application doit émettre une exception si cela se produit. Par exemple, si l'UUID est utilisé comme clé primaire dans la base de données, celle-ci devrait générer une erreur lors de l'insertion d'un ID en conflit.

Cependant, j’imagine qu’écrire du code pour générer un nouvel UUID en cas de collision et tenter à nouveau d’être une perte de temps. Le risque de collision est si faible que le fait de lancer une exception constituerait un moyen parfaitement raisonnable de la gérer.

Souvenez-vous que ce n'est pas seulement une perte de temps que vous rédigez le code, mais que cela le rend plus complexe, rendant la lecture plus difficile pour la personne suivante, sans aucun gain.

C'est une très bonne question. Je ne crois pas qu'il ait été suffisamment pris en compte dans la hâte d'utiliser des UUID partout. Je n'ai trouvé aucune recherche solide.

Une suggestion: marchez très attentivement ici et connaissez bien votre cryptographie. Si vous utilisez un UUID de 128 bits, «l'effet d'anniversaire» nous indique qu'une collision surviendra probablement après la génération d'environ 2 à 64 clés, à condition que vous disposiez de 128 bits d'entropie dans chaque clé .

Il est en fait assez difficile de s’assurer que c’est le cas. Le véritable caractère aléatoire peut être généré à partir (a) de la désintégration radioactive (b) du bruit radioélectrique de fond aléatoire, souvent contaminé à moins d’être prudent (c) du bruit électronique choisi de manière appropriée, par exemple pris d’une diode Zener à polarisation inverse. (J'ai joué avec le dernier et ça marche à merveille, BTW).

Je ne me fierais pas à des énoncés tels que "Je ne l'ai pas vu depuis un an", à moins que l'utilisateur n'ait généré quelque chose s'approchant de 2 ^ 64 (c'est-à-dire environ 10 ^ 19) et les ait toutes vérifiées, un exercice non trivial.

Le problème est le suivant. Supposons que vous n’ayez que 100 bits d’entropie lorsque vous comparez vos clés à toutes les autres clés générées dans un espace de clés commun. Vous allez commencer à voir des collisions dans environ 2 ^ 50, à savoir. environ 10 ^ 15 touches. Vos chances de voir une collision si vous avez rempli votre base de données avec seulement 1 000 milliards de clés sont toujours négligeables. Et si vous ne le vérifiez pas, vous obtiendrez plus tard des erreurs inattendues qui se glissent dans votre base de données de la taille d'une rangée de péta. Cela pourrait mordre fort.

Le fait même qu'il existe de multiples approches pour générer de tels UUID devrait provoquer un spasme momentané d'inquiétude. Lorsque vous vous rendez compte que peu de générateurs utilisent des processus «réellement aléatoires» avec suffisamment d'entropie pour un UUID de type 4, vous devez être extrêmement inquiet à moins que vous n'ayez soigneusement examiné le contenu d'entropie du générateur. (La plupart des gens ne le feront pas ou ne sauront même pas comment; vous pourriez commencer par la suite DieHarder). Ne confondez pas la génération de nombres pseudo-aléatoires avec la génération réelle de nombres aléatoires.

Il est essentiel que vous réalisiez que l'entropie que vous avez entrée est celle que vous avez, et le simple fait de perturber la clé en appliquant une fonction cryptographique ne modifie pas l'entropie. Il n’est peut-être pas intuitivement évident que si tout mon espace comprend les chiffres 0 et 1, le contenu de l’entropie est identique à celui des deux chaînes suivantes, à condition qu’il s’agisse des deux seules options possibles: "C’est une chaîne vraiment très complexe. 293290729382832 * ! @@ # & ^% $$) ,. m} "et" Et maintenant, pour quelque chose de complètement différent ". Il n'y a toujours que deux options.

Le hasard est délicat à comprendre, et croire que "les experts l'ont examiné, donc c'est OK" peut ne pas suffire. Les cryptographes experts (et quelques-uns d'entre eux sont vraiment compétents) sont les premiers à admettre qu'ils se trompent souvent. Nous avons fait confiance à heartbleed, DigiNotar, etc.

Je pense que Paul Tomblin exerce la prudence appropriée. Mon 2c.

Le problème que vous avez est que si vous utilisez un "générateur de nombres aléatoires" et que vous ne savez pas à quel point ce générateur est aléatoire, la probabilité de collision est en réalité inconnue. Si les générateurs de nombres aléatoires sont corrélés d'une manière ou d'une autre, la probabilité de collision peut considérablement augmenter - peut-être de très nombreux ordres ou magnitudes.

Même si votre probabilité de collision est très faible, vous avez un problème fondamental: la probabilité n'est pas 0. Cela signifie qu'une collision se produira ENCORE, elles ne se produiront tout simplement pas très souvent.

Plus vous générez et utilisez fréquemment les UUID, plus tôt cette collision risque de se produire. (générer 1 par an signifie un temps d'attente plus long que générer un million par seconde, toutes choses étant égales par ailleurs).

Si cette probabilité est finie, inconnue et que vous utilisez beaucoup d'UUID, vous devez tenir compte des conséquences d'une collision. S'il n'est pas acceptable de lancer une exception et de fermer une application métier, ne le faites pas! (Exemples spontanés: "C’est correct d’arrêter le serveur Web au cours de la mise à jour de l’archivage d’une bibliothèque ... cela n'arrivera pas souvent" et "C’est correct de fermer le système de paie au milieu de faire le salaire ". Ces décisions peuvent être des mouvements limitant carrière.)

Vous pouvez avoir un cas pire cependant, encore une fois en fonction de votre application. Si vous testez la présence d'un UUID (par exemple, effectuez une recherche), puis créez-en un nouveau s'il n'en existe pas déjà un - ce qui est assez courant, alors vous risquez de vous retrouver en train de lier des enregistrements ou d'établir des relations. , alors que vous connectez 2 objets via un UUID qui ne doivent pas être connectés. C'est une situation dans laquelle le lancement d'une exception ne résoudra rien et que vous créez un désordre indétectable quelque part. C’est le genre de chose qui entraîne des fuites d’informations et qui peut être très embarrassant. (ex: connectez-vous à votre banque et trouvez que vous pouvez voir le solde du compte quelqu'un d'autre! Mauvais!)

Résumé: vous devez tenir compte de la manière dont vos UUID sont utilisés et des conséquences d’une collision. Cela détermine si vous devez prendre soin de détecter et d'éviter les collisions, prendre des mesures simples en cas de collision ou ne rien faire. Une solution simple, unique et universelle ne sera probablement pas appropriée dans certaines circonstances.

Il y a deux problèmes en jeu:

1. Qualité des générateurs de nombres aléatoires utilisés.

2. Quantité d'UUID pouvant être générés.

Un UUID "aléatoire" a 122 bits aléatoires. En supposant que le hasard soit parfait, vous pouvez vous attendre à une première collision aux alentours de 2 ^ 61 UUID générés (c'est la racine carrée de 2 ^ 122). Si tout le monde sur cette terre générait un UUID par seconde, c’est 10 000 000 000 * 365 * 24 * 60 * 60 = 315360000000000000 UUID par an, ce qui est assez proche de 2 ^ 58. C'est-à-dire qu'après quelques années, vous auriez les premières collisions. À moins que votre application ne soit proche de ces chiffres, vous pouvez être presque certain que vous ne rencontrerez pas de collision si votre générateur aléatoire est de bonne qualité.

Parler du générateur de nombres aléatoires: Si vous utilisez les générateurs des bibliothèques C standard (directement, indirectement ou similaires), en les semant probablement avec le temps, vous êtes foutu. Ceux-ci ne peuvent pas tirer sur suffisamment d'entropie pour éviter les collisions. Cependant, si vous êtes sur Linux, lisez simplement 16 octets de données dans /dev/urandom: Ceci s’appuie sur un pool d’entropie agité par le noyau, qui a accès à certains événements aléatoires réels. Sauf si vous générez généralement des UUID très tôt dans la séquence de démarrage, vous /dev/urandomdevriez vous comporter comme une véritable source aléatoire.

Je l'ai testé une fois en utilisant un programme assez simple (force brute) qui a généré 10 millions d'UUID et je n'ai pas eu de collision.

Le RFC UUID indique que l’UUID n’est pas simplement un groupe de nombres (pseudo) aléatoires.