Comment aléatoire est System.Guid.NewGuid ()? (Prendre deux)

Question

Avant de commencer le marquage ce comme un doublon, lisez-moi. L'autre question a un (le plus probable) d'une mauvaise accepté de répondre.

Je ne sais pas comment .NET génère son Guid, probablement que fait Microsoft, mais il y a une forte chance qu'il appelle simplement CoCreateGuid(). Cette fonction est cependant attesté que l'appel de UuidCreate(). Et les algorithmes pour la création d'un UUID sont assez bien documentée.

Longue histoire courte, être comme il en soit, il semble qu' System.Guid.NewGuid() , en effet, utilise la version 4 de l'UUID de l'algorithme de génération, parce que tout le Guid il génère correspond aux critères (voir par vous-même, j'ai essayé une couple de millions de Guid, ils sont tous jumelés).

En d'autres termes, ces Guid sont presque aléatoire, sauf pour quelques bits.

Ensuite, cela soulève de nouveau la question: comment aléatoire EST ce aléatoire? Comme tout bon petit programmeur sait, un nombre pseudo-aléatoire de l'algorithme est aussi aléatoire que sa graine (aka l'entropie). Alors, quelle est la graine de la UuidCreate()? Comment souvent est le GÉNÉRATEUR ré-ensemencées? Est-il à fort niveau de chiffrement, ou puis-je espérer le même Guid commence à sortir si deux ordinateurs accidentellement appel System.Guid.NewGuid() à la même heure? Et peut l'état du GÉNÉRATEUR de deviner si un nombre suffisant de façon séquentielle généré Guid sont réunis?

Ajouté: Pour être clair, je voudrais savoir comment aléatoire puis-je faire confiance à l'être, et donc - où puis-je l'utiliser. Donc, nous allons établir un rough "aléatoire" ici:

1. De base de l'aléatoire, de prendre le temps actuel comme la graine. Utilisable pour brouiller les cartes en Solitaire, mais rien d'autre que les collisions sont trop facile à trouver, même sans essayer.
2. Plus avancées de l'aléatoire, en utilisant non seulement le temps, mais d'autres spécifiques à la machine, les facteurs de semences. Peut-être aussi des graines qu'une seule fois au démarrage du système. Cela peut être utilisé pour générer des Identifiants dans une base de données parce que les doublons sont peu probables. Pourtant, il n'est pas bon pour la sécurité, car les résultats peuvent être prédits avec suffisamment d'efforts.
3. Cryptograhpically aléatoire, à l'aide du bruit de l'appareil ou d'autres sources de l'aléatoire pour les semences. Ré-ensemencées sur chaque invocation ou au moins assez souvent. Peut être utilisé pour les Id de session, remis aux parties non fiables, etc.

Je suis arrivé à cette question tout en pensant que si il serait OK pour les utiliser comme DB Id, et si le Guid.le peigne de l'implémentation de l'algorithme avec System.Guid.NewGuid() (comme NHibernate t-il) serait défectueux ou non.

Answer 1

La accepté de répondre à une question concernant les états:

Un GUID ne pas donner des garanties au sujet de l'aléatoire, il fait des garanties autour de l'unicité. Si vous voulez de l'aléatoire, de l'utilisation Aléatoire pour générer une chaîne de caractères.

Tout autre est un détail d'implémentation (et peut changer).

Mise à jour: que mon point De vue plus claire: Même si le courant .NET 3.5 mise en œuvre produit un vraiment aléatoire guid (qui n'est pas le cas) il n'y a aucune garantie que ce serait le cas dans le futur, ou pour d'autres implémentations de la BCL (par exemple, Mono, Silverlight, CF, etc)

Mise à jour 2: Le format de l'UUID est spécifié par RFC4122. L'article 6 fait une déclaration explicite sur la sécurité:

Ne présumez pas que les Uuid sont difficiles à deviner; ils ne doivent pas être utilisés comme les capacités de sécurité (identificateurs dont la simple possession de subventions l'accès), par exemple. Prévisible nombre aléatoire de la source aggraver la situation.

Answer 2

Certaines personnes ont déjà fait allusion à ça, mais je tiens à le répéter, car il semble y avoir un malentendu là:

L'aléatoire et l'unicité sont orthogonaux concepts.

Données aléatoires peut être unique ou redondantes, et de la même manière unique de données peut utiliser une source aléatoires ou déterministes source (pensez à un compteur global qui est verrouillé et incrémenté à chaque GUID jamais créé).

Guid ont été conçus pour être unique, et non pas aléatoire. Si l' .NET générateur apparaît à l'utilisation des entrées aléatoires, très bien. Mais ne comptez pas sur elle comme une source de hasard, ni pour cryptographiques majeures, ni à d'autres fins (en particulier, que la fonction de distribution attendez-vous à obtenir?). D'autre part, vous pouvez être raisonnablement sûr que les Guid de la créé par .NET, même dans de grands volumes, sera unique.

Answer 3

Api qui produisent des octets aléatoires, mais qui ne sont pas explicitement documentées pour produire de cryptage fort octets aléatoires ne peut pas faire confiance à produire cryptage fort octets aléatoires.

Si vous avez besoin de cryptage fort octets aléatoires, alors vous devriez être en utilisant une API qui est explicitement documentées pour les produire.

public Guid CreateCryptographicallyStrongGuid() {
    var rng = new System.Security.Cryptography.RNGCryptoServiceProvider();
    var data = new byte[16];
    rng.GetBytes(data);
    return new Guid(data);
}

Ces Guid sont tout simplement 128 bits de chiffrement aléatoire. Ils ne sont pas structurés, et ils ne seront pas en collision.

Voir cet article pour certains calculs. À l'aide de "La Générale d'Anniversaire Formule", en réorganisant les donne

n = sqrt(-2T * ln(p))

où n est le nombre d'éléments choisis, T est le nombre total d'éléments (2^128), et p est la probabilité cible que tous les n éléments choisis seront différentes. Avec p = .99, ce qui donne *n = 2.61532104 * 10^18*. Cela signifie que nous pouvons générer un milliard de vraiment aléatoire Guid par seconde au sein d'un système pour un milliard de secondes (32 ans), et ont mieux que 99% de chance à la fin que chacun est unique dans le système.

Answer 4

La définition de Random n'a aucun rapport avec la définition de Globally Unique.

Lancer une pièce deux fois et obtenir HH, HT, TH, TT sont tous aléatoires. HH est tout aussi aléatoire que HT.

Lancer une pièce "spéciale" deux fois et garantir que vous n'obtiendrez que HT ou TH est unique.

Answer 5

Ils sont aléatoires de sorte qu'il est mathématiquement prouvable que les collisions ne devraient pas se produire pendant très longtemps, de sorte que vous pouvez supposer qu'elles sont uniques à l'échelle mondiale. Cependant, ils ne sont pas cryptographiquement solides, car cela nécessiterait un véritable caractère aléatoire, ce qui n'est pas vraiment possible dans les ordinateurs sans matériel dédié.