Est-il acceptable de compter sur des intrants aléatoires uniques?

Je suis en train d'implémenter un protocole réseau et j'ai besoin que les paquets possèdent des identifiants uniques. Jusqu'à présent, je viens de générer des entiers aléatoires sur 32 bits, en supposant qu'il est astronomiquement peu probable qu'il y ait une collision pendant la durée de vie d'un programme / d'une connexion. Est-ce généralement considéré comme une pratique acceptable dans le code de production ou faut-il concevoir un système plus complexe pour éviter les collisions?

Attention au paradoxe de l' anniversaire .

Supposons que vous générez une séquence de valeurs aléatoires (uniformément, indépendamment) à partir d'un ensemble de taille N (N = 2 ^ 32 dans votre cas).

Ensuite, la règle empirique pour le paradoxe de l'anniversaire stipule qu'une fois que vous avez généré environ des valeurs sqrt (N), il y a au moins 50% de chances qu'une collision se soit produite, c'est-à-dire qu'il existe au moins deux valeurs identiques dans le champ. séquence générée.

Pour N = 2 ^ 32, sqrt (N) = 2 ^ 16 = 65536. Ainsi, après avoir généré environ 65k identifiants, il est plus probable que deux d’entre eux se heurtent! Si vous générez un identifiant par seconde, cela se produirait en moins d'un jour. Il va sans dire que de nombreux protocoles de réseau fonctionnent bien plus rapidement que cela.

Il est largement considéré comme acceptable de s’appuyer sur des nombres aléatoires uniques si ces nombres ont suffisamment de bits. Il existe des protocoles cryptographiques dans lesquels la répétition d'un nombre aléatoire annule toute la sécurité. Et tant que le générateur de nombres aléatoires utilisé ne contient pas de vulnérabilités sérieuses, cela ne pose pas de problème.

L'un des algorithmes de génération d'identificateurs UUID générera efficacement un identifiant composé de 122 bits aléatoires et supposera qu'il sera unique. Et deux des autres algorithmes reposent sur le fait qu'une valeur de hachage tronquée à 122 bits est unique, ce qui présente à peu près le même risque de collision.

Il existe donc des normes qui supposent que 122 bits suffisent pour créer un identifiant aléatoire unique, mais 32 bits ne suffisent certainement pas. Avec les identifiants 32 bits, il ne faut qu'environ 2¹⁶ ID avant que le risque de collision n'atteigne 50%, car avec 2¹⁶ ID, il y aura près de 2³¹ paires, chacune pouvant être une collision.

Même 122 bits est inférieur à ce que je recommanderais dans tout nouveau design. Si le respect de certaines normes est important pour vous, utilisez des UUID. Sinon, utilisez quelque chose de plus grand que 122 bits.

La fonction de hachage SHA1 avec une sortie de 160 bits n'est plus considérée comme sécurisée, en partie parce que 160 bits ne suffisent pas pour garantir l'unicité des sorties. Les fonctions de hachage modernes ont des sorties de 224 à 512 bits. Les identifiants générés aléatoirement doivent viser les mêmes tailles pour garantir l'unicité avec une marge de sécurité suffisante.

J'appellerais cela une mauvaise pratique. Les nombres aléatoires générés ne créent simplement pas des nombres uniques, ils créent simplement des nombres aléatoires. Une distribution aléatoire est susceptible d'inclure quelques doublons. Vous pouvez rendre cette circonstance assez improbable en ajoutant un élément de temps. Si vous obtenez l'heure actuelle de l'horloge système en millisecondes. Quelque chose comme ça:

parseToInt(toString(System.currentTimeMillis()) + toString(Random.makeInt()))

Ira un long chemin. De toute évidence, pour garantir réellement l'unicité, vous devez utiliser UUID / GUID. Mais ils peuvent être coûteux à générer, ce qui précède est probablement suffisant, car la seule possibilité de chevauchement est que si le générateur aléatoire ait un doublon dans la même milliseconde.

Cela dépend à la fois de la probabilité d'échec et des conséquences d'un échec.

Je me souviens d'un débat opposant des personnes travaillant sur les logiciels et le matériel. Les personnes travaillant sur le matériel considéraient qu'un algorithme avec une faible probabilité de résultats erronés (environ 1 défaillance sur 100 ans) était acceptable et que les personnes travaillant sur les logiciels pensaient que c'était un anathème. Il s’est avéré que les spécialistes du matériel calculaient régulièrement les taux de défaillance attendus et étaient très habitués à l’idée que tout donnerait de temps en temps des réponses erronées, par exemple en raison de perturbations causées par les rayons cosmiques; ils ont trouvé étrange que les logiciels s’attendent à une fiabilité à 100%.

Bien sûr, vous avez de très faibles probabilités que deux entiers aléatoires de 32 bits soient séquentiels, mais ce n'est pas complètement impossible. La décision technique appropriée est basée sur les conséquences des collisions, une estimation du volume de nombres que vous générez, la durée de vie pour laquelle l'unicité est requise et ce qui se passe si un utilisateur malveillant tente de provoquer des collisions.

Il peut être acceptable de supposer que les nombres aléatoires seront uniques, mais vous devez faire attention.

En supposant que vos nombres aléatoires soient distribués de manière égale, la probabilité de collision est approximativement (n ^2/2 ) / k, où n est le nombre de nombres aléatoires que vous générez et k le nombre de valeurs possibles pouvant être prises par un nombre "aléatoire".

Vous ne mettez pas un chiffre astronomiquement improbable, alors prenons le chiffre 1 sur 2 ³⁰ (environ 1 milliard). Disons en outre que vous générez 2 à ³⁰ paquets (si chaque paquet représente environ un kilo-octet de données, cela signifie environ un téraoctet de données totales, mais sans que cela ne soit pas imaginable). Nous constatons que nous avons besoin d'un nombre aléatoire avec au moins 2 ⁸⁹ valeurs possibles.

Premièrement, vos nombres aléatoires doivent être suffisamment grands. Un nombre aléatoire de 32 bits peut avoir au plus 2 ³² valeurs possibles. Pour un serveur occupé qui est loin d'être assez élevé.

Deuxièmement, votre générateur de nombres aléatoires doit avoir un état interne suffisamment grand. Si votre générateur de nombres aléatoires a uniquement un état interne à 32 bits, quelle que soit la taille de la valeur que vous en générez, vous n'obtiendrez toujours que 2 ³² valeurs possibles au maximum.

Troisièmement, si vous souhaitez que les nombres aléatoires soient uniques dans toutes les connexions plutôt que dans une seule connexion, votre générateur de nombres aléatoires doit être bien amorcé. Cela est particulièrement vrai si votre programme est redémarré fréquemment.

En général, les générateurs de nombres aléatoires "normaux" dans les langages de programmation ne conviennent pas à une telle utilisation. Les générateurs de nombres aléatoires fournis par les bibliothèques de cryptographie sont généralement.

Certaines des réponses ci-dessus reposent sur l'hypothèse que le générateur de nombres aléatoires est bien «plat», c'est-à-dire que la probabilité que deux nombres soient générés est la même.

Ce n'est probablement pas vrai pour la plupart des générateurs de nombres aléatoires. La plupart d'entre eux utilisent un polynôme d'ordre élevé appliqué de manière répétée à une graine.

Cela dit, de nombreux systèmes dépendent de ce schéma, généralement avec des identificateurs UUID. Par exemple, chaque objet et élément de Second Life a un UUID 128 bits, généré de manière aléatoire, et ils se rencontrent rarement.

Beaucoup de gens ont déjà donné des réponses de grande qualité, mais je voudrais ajouter quelques points mineurs: tout d’abord, le point de @nomadictype sur le paradoxe de l’anniversaire est excellent .

Un autre point: le caractère aléatoire n’est pas aussi simple à générer et à définir que l’on pourrait supposer. (En fait, il existe des tests statistiques pour le caractère aléatoire disponibles).

Cela dit, il est important de connaître l’ erreur du joueur , qui est une erreur statistique selon laquelle les gens présument que des événements indépendants s’influencent mutuellement. Les événements aléatoires sont généralement statistiquement indépendants les uns des autres. Par exemple, si vous générez un "10" de manière aléatoire, cela ne change en rien votre probabilité future de générer plus de "10". (Peut-être que quelqu'un pourrait proposer une exception à cette règle, mais je m'attendrais à ce que ce soit le cas pour à peu près tous les générateurs de nombres aléatoires).

Donc, ma réponse est que si vous pouviez supposer qu'une séquence suffisamment longue de nombres aléatoires était unique, il ne s'agirait pas vraiment de nombres aléatoires, car ce serait un modèle statistique clair. En outre, cela impliquerait que chaque nouveau nombre ne soit pas un événement indépendant, car si vous générez, par exemple, un 10, cela signifierait que la probabilité de générer des 10 à venir serait de 0% (cela ne pourrait probablement pas arriver), plus cela signifierait que vous augmenteriez les chances d'obtenir un nombre autre que 10 (c'est-à-dire que plus vous générez de nombres, plus la probabilité de chacun des nombres restants augmente).

Une dernière chose à considérer: la chance de gagner le Powerball en jouant un seul jeu est, si je comprends bien, d’environ 1 sur 175 millions. Cependant, les chances de quelqu'un gagner sont considérablement plus élevés que cela. Vous êtes plus intéressé par les chances de quelqu'un « gagnant » (c. -à- Etre un double) que dans les chances de tout nombre particulier « gagnant » / étant un doublon.

Peu importe le nombre de bits que vous utilisez - vous ne pouvez PAS garantir que deux nombres "aléatoires" seront différents. Au lieu de cela, je vous suggère d'utiliser quelque chose comme l'adresse IP ou une autre adresse réseau de l'ordinateur et un numéro séquentiel, de préférence un nombre séquentiel HONKIN 'BIG - 128 bits (évidemment non signé) sonne comme un bon début, mais 256 serait meilleur.

Non bien sûr que non. Sauf si vous utilisez des échantillons sans remplacement, les chances de duplication sont minimes.