Comment les UUID sont générés

Vous avez probablement déjà utilisé des UUID dans vos projets et pensiez qu'ils étaient uniques. Jetons un coup d'œil aux principaux aspects de l'implémentation et voyons pourquoi les UUID sont pratiquement uniques, car il existe une infime possibilité que les mêmes valeurs se produisent.



L'implémentation moderne des UUID remonte à la RFC 4122, qui décrit cinq approches différentes pour générer ces identifiants. Nous allons passer en revue chacun d'eux et parcourir l'implémentation des versions 1 et 4.

Théorie

UUID (IDentifier universellement unique) est un nombre de 128 bits utilisé dans le développement logiciel comme identifiant unique pour les éléments. Sa représentation textuelle classique est une série de 32 caractères hexadécimaux, séparés par des tirets en cinq groupes dans le modèle 8-4-4-4-12.



Par exemple:

3422b448-2460-4fd2-9183-8000de6f8343

Les informations d'implémentation UUID sont intégrées dans cette séquence apparemment aléatoire de caractères:

xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx

Les valeurs aux positions M et N définissent respectivement la version et la variante de l'UUID.

Version

Le numéro de version est identifié par les quatre bits les plus significatifs à la position M. Il existe aujourd'hui les versions suivantes:

Option

Ce champ définit le modèle des informations intégrées dans l'UUID. L'interprétation de tous les autres bits de l'UUID dépend de la valeur de la variante.



Nous le déterminons par les 1 à 3 premiers bits les plus significatifs à la position N.





Aujourd'hui, l'option 1 est le plus souvent utilisée, dans laquelle MSB0est égal 1et MSB1égal 0. Cela signifie que donnée de caractères génériques - bits sélectionnés - seules valeurs possibles sont 8, 9, Aou B.

Mémo:



1 0 0 0 = 8

1 0 0 1 = 9

1 0 1 0 = A

1 0 1 1 = B

Donc, si vous voyez un UUID avec de telles valeurs à la position N, il s'agit de l'identifiant de l'option 1.

Version 1 (heure + identifiant d'hôte unique ou aléatoire)

Dans ce cas, l'UUID est généré comme ceci: une propriété d'identification du périphérique qui génère l'UUID est ajoutée à l'heure actuelle, le plus souvent c'est l'adresse MAC (également appelée ID de nœud).



L'identifiant est obtenu en concaténant une adresse MAC de 48 bits, un horodatage de 60 bits, une séquence d'horloge «unique» de 14 bits et 6 bits réservés aux UUID de version et de variante.

La séquence d'horloge est simplement une valeur qui est incrémentée chaque fois que l'horloge est modifiée.

L'horodatage utilisé dans cette version est le nombre d'intervalles de 100 nanosecondes depuis le 15 octobre 1582, date à laquelle le calendrier grégorien est né.

Vous connaissez peut-être le système temporel Unix depuis le début d'une époque. C'est juste un type différent de Day Zero. Il existe des services sur le Web qui peuvent vous aider à transformer une représentation temporelle en une autre, alors ne nous attardons pas là-dessus.

Bien que cette implémentation semble assez simple et fiable, l'utilisation de l'adresse MAC de la machine sur laquelle l'identifiant est généré ne permet pas de considérer cette méthode comme universelle. Surtout lorsque la sécurité est le critère principal. Par conséquent, dans certaines mises en œuvre, au lieu de l'identificateur de nœud, 6 octets aléatoires pris à partir d'un générateur de nombres aléatoires protégé par cryptographie sont utilisés.



La construction de la version 1 de l'UUID ressemble à ceci:

1. Les 32 bits les moins significatifs de l'horodatage UTC actuel sont pris. Ce seront les 4 premiers octets (8 caractères hexadécimaux) de l'UUID [ TimeLow].
2. Les 16 bits du milieu de l'horodatage UTC actuel sont pris. Ce seront les 2 octets suivants (4 caractères hexadécimaux) [ TimeMid].
3. Les 2 octets suivants (4 caractères hexadécimaux) concaténent les 4 bits de la version UUID avec les 12 MSB restants de l'horodatage UTC actuel (qui a un total de 60 bits) [ TimeHighAndVersion].
4. Les 1-3 bits suivants définissent la variante de version d'UUID. Les bits restants contiennent une séquence d'horloge qui ajoute un peu d'aléatoire à cette implémentation. Cela évite les collisions lorsque plusieurs générateurs UUID fonctionnent sur le même système: soit l'horloge système est reculée pour le générateur, soit le changement d'heure est ralenti [ ClockSequenceHiAndRes && ClockSequenceLow].
5. Les 6 derniers octets (12 caractères hexadécimaux, 48 bits) sont l '"ID de nœud", qui est généralement l'adresse MAC du générateur [ NodeID].

L'UUID version 1 est généré à l'aide de la concaténation:

TimeLow + TimeMid + TimeHighAndVersion + (ClockSequenceHiAndRes && ClockSequenceLow) + NodeID 

Étant donné que cette implémentation dépend de l'horloge, nous devons gérer les situations de pointe. Premièrement, pour minimiser la corrélation entre les systèmes, par défaut, la séquence d'horloge est considérée comme un nombre aléatoire - cela n'est fait qu'une seule fois dans tout le cycle de vie du système. Cela nous donne l'avantage supplémentaire de prendre en charge les ID de nœud qui peuvent être transportés à travers les systèmes, car la séquence d'horloge initiale est complètement indépendante de l'ID de nœud.



N'oubliez pas que le but principal de l'utilisation d'une séquence d'horloge est d'ajouter un peu de caractère aléatoire à notre équation. Les bits de séquence d'horloge aident à étendre l'horodatage et à s'adapter aux situations dans lesquelles plusieurs UUID sont générés avant même que l'horloge du processeur ne change. De cette façon, nous évitons de créer les mêmes identifiants lorsque l'horloge est reculée (l'appareil est éteint) ou que l'identifiant du nœud change. Si l'horloge a été reculée, ou aurait pu l'être (par exemple, alors que le système était arrêté) et que le générateur d'UUID ne peut pas être sûr que les identifiants ont été générés avec des horodatages plus récents que la valeur d'horloge spécifiée, alors la séquence d'horloge doit être modifiée. Si nous connaissons sa valeur antérieure, nous pouvons simplement l'augmenter;sinon, il doit être défini de manière aléatoire ou avec un PRNG de haute qualité.

Version 2 (sécurité d'un environnement informatique distribué)

La principale différence entre cette version et la précédente est qu'au lieu du "caractère aléatoire" sous la forme des bits les moins significatifs de la séquence d'horloge, un identifiant caractéristique du système est utilisé ici. Souvent, il ne s'agit que de l'ID de l'utilisateur actuel. La version 2 est moins utilisée, elle diffère très peu de la version 1, alors passons à autre chose.

Version 3 (nom + hachage MD5)

Si des identifiants uniques sont nécessaires pour les informations de nom ou de dénomination, l'UUID est généralement la version 3 ou la version 5.



Ils codent toutes les entités «nommées» (sites, DNS, texte brut, etc.) en une valeur UUID. Plus important encore, le même UUID sera généré pour le même espace de noms ou texte.



Notez que l'espace de noms lui-même est un UUID.

let namespace = “digitalbunker.dev”
let namespaceUUID = UUID3(.DNS, namespace)

// Ex: 
UUID3(namespaceUUID, “/category/things-you-should-know-1/”) 
4896c91b-9e61-3129-87b6-8aa299028058

UUID3(namespaceUUID, “/category/things-you-should-know-2/”) 
29be0ee3-fe77-331e-a1bf-9494ec18c0ba

UUID3(namespaceUUID, “/category/things-you-should-know-3/”) 
33b06619-1ee7-3db5-827d-0dc85df1f759

Dans cette implémentation, l'espace de noms UUID est converti en une chaîne d'octets concaténée avec le nom d'entrée, puis haché avec MD5, ce qui donne 128 bits pour l'UUID. Nous réécrivons ensuite certains des bits pour reproduire fidèlement la version et les informations de version, et laissons le reste intact.



Il est important de comprendre que ni l'espace de noms ni le nom d'entrée ne peuvent être calculés en fonction de l'UUID. C'est une opération irréversible. La seule exception est la force brute lorsque l'une des valeurs (espace de nom ou texte) est déjà connue de l'attaquant.



Avec la même entrée, les UUID générés des versions 3 et 5 seront déterministes.

Version 4 (PRNG)

Implémentation la plus simple.



6 bits sont réservés pour la version et la variante, il reste 122 bits. Cette version génère simplement 128 bits aléatoires, puis en remplace 6 par des données de version et de version.



De tels UUID sont totalement dépendants de la qualité du PRNG (générateur de nombres pseudo-aléatoires). Si son algorithme est trop simple ou s'il manque de valeurs initiales, la probabilité de répéter les identificateurs augmente.



Dans les langues modernes, l'UUID version 4 est le plus souvent utilisée.



Son implémentation est assez simple:

1. Nous générons 128 bits aléatoires.
2. Réécrivez certains bits avec la version et les informations de version correctes:
   
   
   
   
   1. Prenez le septième bit et 0x0FET pour effacer le grignotage élevé. Et puis 0x40OR est utilisé pour attribuer la version 4.
   2. Ensuite, nous prenons le neuvième octet, effectuons une 0x3Fopération AND sur c et une 0x80opération OR sur celui-ci.
3. Convertissez 128 bits en hexadécimal et insérez des tirets.

Version 5 (nom + SHA-1-hash)

La seule différence par rapport à la version 3 est que nous utilisons l'algorithme de hachage SHA-1 au lieu de MD5. Cette version est préférée à la troisième (SHA-1> MD5).

Entraine toi

L'un des avantages importants des UUID est que leur caractère unique ne dépend pas d'une autorité d'autorisation centrale ou d'une coordination entre différents systèmes. N'importe qui peut créer un UUID avec une certaine certitude que personne d'autre ne générera cette valeur dans un avenir prévisible.



Cela permet de combiner des identifiants créés par différents participants dans une base de données, ou de déplacer des identifiants entre des bases de données avec une probabilité de collision négligeable.



Les UUID peuvent être utilisés comme clés primaires dans les bases de données, comme noms uniques pour les fichiers téléchargés, comme noms uniques pour toutes les sources Web. Vous n'avez pas besoin d'une autorité d'autorisation centrale pour les générer. Mais c'est une solution à double tranchant. En raison de l'absence de contrôleur, il est impossible de suivre les UUID générés.



Il y a quelques autres inconvénients qui doivent être traités. Le caractère aléatoire inhérent augmente la sécurité, mais rend le débogage plus difficile. En outre, l'UUID peut être redondant dans certaines situations. Disons que cela n'a pas de sens d'utiliser 128 bits pour identifier de manière unique les données dont la taille totale est inférieure à 128 bits.

Unicité

Il peut sembler que si vous disposez de suffisamment de temps, vous pouvez répéter une valeur. Surtout dans le cas de la version 4. Mais en réalité ce n'est pas le cas. Si vous deviez générer un milliard d'UUID par seconde sur 100 ans, la probabilité que l'une des valeurs se répète serait d'environ 50%. Ceci étant donné que le PRNG fournit une quantité suffisante d'entropie (vrai hasard), sinon la probabilité d'un double sera plus élevée. Un exemple plus illustratif: si vous avez généré 10 trillions d'UUID, la probabilité d'apparition de deux valeurs identiques est de 0,00000006%.



Et dans le cas de la version 1, l'horloge ne sera remise à zéro que dans 3603. Donc, si vous ne prévoyez pas de maintenir votre service opérationnel jusqu'en 1583, vous êtes en sécurité.



Cependant, la probabilité d'apparition d'un double demeure, et dans certains systèmes, ils essaient d'en tenir compte. Mais dans la grande majorité des cas, les UUID peuvent être considérés comme totalement uniques. Si vous avez besoin de plus de preuves, voici une simple visualisation de la probabilité de collision en pratique.