Pourquoi ne combinons-nous pas des générateurs de nombres aléatoires?

60

Il existe de nombreuses applications dans lesquelles un générateur de nombres pseudo aléatoires est utilisé. Ainsi, les gens en implémentent un qu’ils jugent bon de constater plus tard qu’il est défectueux. Quelque chose comme cela s’est passé récemment avec le générateur de nombres aléatoires Javascript. RandU beaucoup plus tôt aussi. Il existe également des problèmes d'ensemencement initial inapproprié pour quelque chose comme le Twister.

Je ne trouve pas d’exemples de personnes combinant au moins deux familles de générateurs avec l’opérateur xor habituel. Si la puissance de l'ordinateur est suffisante pour exécuter des opérations telles que les implémentations java.SecureRandom ou Twister, pourquoi les utilisateurs ne les combinent-ils pas? ISAAC xor XORShift xor RandU devrait être un assez bon exemple, et vous pouvez voir la faiblesse d'un seul générateur atténuée par les autres. Cela devrait également aider à répartir les nombres dans des dimensions plus élevées car les algorithmes intrinsèques sont totalement différents. Existe-t-il un principe fondamental selon lequel ils ne devraient pas être combinés?

Si vous deviez créer un véritable générateur de nombres aléatoires, les gens vous conseilleraient probablement de combiner deux sources d'entropie ou plus. Mon exemple est-il différent?

J'exclus l'exemple typique de plusieurs registres à décalage à retour linéaire fonctionnant ensemble car ils appartiennent à la même famille.

Paul Uszak
la source
La réponse peut dépendre de l'application. Pourquoi voulez-vous utiliser la séquence pseudo-aléatoire?
Yuval Filmus
1
Avez - vous trouvé Fortuna ( en.wikipedia.org/wiki/Fortuna_%28PRNG%29 ) , il ressemble à son proche de ce que vous décrivez que agrège différentes sources au hasard en un seul.
Little Code
1
@ LittleCode En fait, ça sonne complètement différent. Fortuna sort les données d'une seule fonction de hachage. Cela perturbe juste avec beaucoup de mécanismes de collecte d'entropie faible avant de (re) le hacher via une seule fonction de sortie. Ma question concernait la sortie de plusieurs fonctions (pourquoi pas 10 d’entre elles)? S'il s'agit d'un dispositif de remplissage, la vitesse importe quand même.
Paul Uszak
1
Le regretté George Marsaglia, un chercheur renommé dans le domaine des PRNG qui a inventé de nouveaux types de PRNG tels que le multiply-with-carry et le xor-shift, l’a fait précisément lorsqu'il a proposé le générateur KISS dans les années 1990, qui est une combinaison de trois PRNG de type différent. J'utilise KISS avec succès depuis vingt ans, pas pour la cryptographie, bien sûr. Une source secondaire utile en ce qui concerne KISS est cet article de Greg Rose de 2011 dans lequel il souligne un problème avec l'un des PRNG constitutifs, qui n'invalide pas le concept de combinaison
njuffa
4
Knuth rapporte le résultat de la combinaison naïve de générateurs de nombres pseudo-aléatoires (utilisant un nombre aléatoire pour choisir le générateur à utiliser) a abouti à une fonction qui converge vers une valeur fixe! Donc, à l'époque juste avant la révolution des micro-ordinateurs, il nous a avertis de ne jamais mélanger les générateurs aléatoires.
JDługosz

Réponses:

7

IIRC (et cela vient de mémoire), le best-seller de 1955 Rand, A Million Random Digits, a fait quelque chose comme ça. Avant que les ordinateurs soient bon marché, les gens choisissaient des nombres aléatoires dans ce livre.

Les auteurs ont généré des bits aléatoires avec du bruit électronique, mais cela s’est avéré être biaisé (il est difficile de faire une bascule dépensant exactement le même temps sur la bascule et sur le flop). Cependant, la combinaison de bits a rendu la distribution beaucoup plus uniforme.

Amateur
la source
45

Bien sûr, vous pouvez combiner les PRNG comme celui-ci, si vous le souhaitez, en supposant qu’ils soient semés indépendamment. Cependant, ce sera plus lent et cela ne résoudra probablement pas les problèmes les plus pressants que les gens rencontrent.

En pratique, si vous avez besoin d'un PRNG de très haute qualité, vous utilisez un PRNG de qualité cryptographique bien testé et vous l'ensemencez avec une véritable entropie. Si vous procédez ainsi, votre mode de défaillance le plus probable ne constitue pas un problème avec l'algorithme PRNG lui-même; le mode de défaillance le plus probable est le manque d'entropie adéquate (ou peut-être des erreurs de mise en œuvre). L'utilisation de plusieurs PRNG n'aide pas avec ce mode d'échec. Donc, si vous voulez un PRNG de très haute qualité, il n’ya probablement aucun intérêt à les analyser.

Alternativement, si vous voulez un PRNG statistique assez bon pour la simulation, le principal souci est la rapidité (générer des nombres pseudo-aléatoires très rapidement) ou la simplicité (ne voulez pas consacrer beaucoup de temps de développement à la recherche ou à la mise en oeuvre). Xor-ing ralentit le PRNG et le rend plus complexe, de sorte qu'il ne répond pas non plus aux besoins principaux dans ce contexte.

Tant que vous faites preuve d'un soin et d'une compétence raisonnables, les PRNG standard sont plus que suffisants. Il n'y a donc aucune raison pour que nous ayons besoin de quelque chose de plus sophistiqué (pas besoin de xor-ing). Si vous n'avez pas même le minimum de soins ou de compétences, vous n'allez probablement pas choisir quelque chose de complexe comme le xor-ing, et la meilleure façon d'améliorer les choses est de vous concentrer sur plus de soin et de compétence dans la sélection du PRNG. plutôt que sur xor-ing.

Conclusion : le truc xor ne résout pas les problèmes généralement rencontrés par les utilisateurs lorsqu'ils utilisent des PRNG.

DW
la source
3
"Le manque d'entropie adéquate ... Stocker plusieurs PRNG n'aide en rien" - en effet, cela peut nuire au fait que vous augmentez la quantité d'entropie nécessaire pour ensemencer vos PRNG. C’est la raison pour laquelle vous ne souhaitez pas que la pratique courante consiste à combiner des PRNG bien contrôlés, même si cela vous protège effectivement contre l’un de ces PRNG bien vérifiés qui se révèlent être un déchet total (dans la mise en œuvre que vous utilisez). .
Steve Jessop
Une autre raison est que les bogues d’implémentation sont beaucoup, beaucoup, beaucoup plus courants que les problèmes fondamentaux avec les algorithmes. Un algorithme standard peut au moins être testé par rapport à une autre implémentation ou à des valeurs de référence, un xor personnalisé ne le peut pas.
Gilles, arrête de faire le mal.
1
@DW Pourquoi "semé de façon indépendante?" Comme ma question concerne des combinaisons de différentes familles de générateurs, chaque famille doit produire une séquence de sortie unique à partir de semences identiques. Par exemple, java.SecureRandom et RC4 pourraient facilement être créés à partir de la même clé, puis combinés.
Paul Uszak
1
@DW La grande hypothèse que vous énoncez est "utilisez un PRNG crypté de qualité éprouvée". La réalité est qu’il est pratiquement impossible de s’en assurer, comme c’est le cas de la plupart des chiffrements cryptographiques, des hachages, etc. Ils ont été "bien contrôlés" pour la connaissance d'hier ou d'antan.
Shiv
1
@PaulUszak, je ne pense pas avoir jamais soutenu que xor-ing deux générateurs le rend plus enclin aux bugs. Je dis que, si vous choisissez un bon PRNG (un seul), l'un des modes de défaillance les plus probables est un échec de l'ensemencement ou une mise en œuvre, et xor-ing deux générateurs n'aident en rien. (Bien sûr, si le seul PRNG n'échoue pas, xor-ing deux générateurs n'est pas utile non plus.) Donc, fondamentalement, il s'agit de résoudre le mauvais problème. En d'autres termes, les générateurs de xor-ing n'augmentent pas beaucoup la certitude, car ils ne traitent pas les causes d'incertitude les plus importantes.
DW
19

En fait, une avancée décisive vient d’être annoncée précisément dans ce sens.

Le professeur d'informatique de l'Université du Texas, David Zuckerman, et le doctorant Eshan Chattopadhyay ont découvert qu'un nombre aléatoire "de haute qualité" pouvait être généré en combinant deux sources aléatoires de "basse qualité".

Voici leur article: Extracteurs explicites à deux sources et fonctions résilientes

NietzscheanAI
la source
8
Il s'agit d'un article purement théorique sur un sujet différent qui n'a absolument aucune pertinence pratique, malgré les efforts de relations publiques de l'UT.
Yuval Filmus
4
@Yuval Filmus - voudriez-vous développer ce commentaire?
NietzscheanAI
8
Il y a un grand fossé entre la théorie et la pratique. Habituellement, les praticiens ne se soucient pas de la théorie et vice versa. Dans ce cas, la branche des relations publiques de l’UT a décidé de s’appuyer sur un excellent document théorique, décrivant celui-ci comme pertinent, ce qui n’est pas le cas. Les problèmes examinés dans le document ne sont pas si intéressants du point de vue pratique et offrent des solutions simples qui fonctionnent assez bien, même s’il est impossible de prouver qu’ils le font.
Yuval Filmus
2
De plus, cet article n'est qu'un travail dans le domaine théorique des extracteurs. Vous pouvez facturer n'importe quel autre papier de la même manière. Ils visent tous à combiner des sources faibles pour créer une source forte. La différence est juste dans les paramètres.
Yuval Filmus
3
Enfin, la construction dans le document est très probablement exagérée, pas quelque chose que vous voudriez jamais mettre en œuvre. Il est difficile de déterminer des paramètres concrets pour ce type de construction, et ils sont généralement extrêmement mauvais, car les documents portent toujours sur le régime asymptotique et ignorent les constantes.
Yuval Filmus
9

Supposons que est une séquence binaire pseudo-aléatoire. Autrement dit, chaque est une variable aléatoire prise en charge sur et les variables ne sont pas nécessairement indépendantes. Nous pouvons imaginer que cette séquence est générée de la manière suivante: nous échantillonnons d’abord une clé uniformément aléatoire , puis nous utilisons une fonction pour générer la séquence pseudo-aléatoire.X1,,XnXi{0,1}X1,,XnKf(K)

Comment pouvons-nous mesurer la qualité de la séquence pseudo-aléatoire ? S'il est possible de mesurer la qualité d'une réalisation particulière (en utilisant la complexité de Kolmogorov, par exemple), je me concentrerai ici sur des mesures qui dépendent de la distribution entière de la variable aléatoire . L'entropie en est un exemple, mais nous n'aurons besoin que de deux propriétés de notre mesure : (un plus grand signifie une séquence plus aléatoire)X1,,Xn(X1,,Xn)LL()

  • Si est une séquence déterministe (c'est-à-dire une séquence fixe), alors . L ( X 1y 1 , ... , X ny n ) = L ( X 1 , ... , X n )y1,,ynL(X1y1,,Xnyn)=L(X1,,Xn)

  • Si sont deux séquences pseudo-aléatoires indépendantes, est un bit aléatoire indépendant et , puis .X0,X1T{0,1}Z=XTL(Z)min(X0,X1)

La première propriété signifie que la mesure est invariante lorsque vous inversez le ème bit. La deuxième propriété signifie que si nous mélangons deux distributions , le résultat est au moins aussi bon que le pire.iX,Y

Toute mesure aléatoire raisonnable satisfera la première propriété. La deuxième propriété est satisfaite par les mesures les plus courantes telles que l'entropie et min-entropie .HH

Nous pouvons maintenant énoncer et prouver un théorème montrant que XORing deux séquences pseudo-aléatoires est toujours une bonne idée.

Théorème. Soit deux séquences pseudo-aléatoires indépendantes de même longueur, et une mesure de caractère aléatoire admissible (une qui vérifie les deux conditions ci-dessus). PuisX,YL

L(XY)max(L(X),L(Y)).

Preuve. Supposons que . Ensuite est un mélange des distributions , mélangé en fonction de la distribution de . Puisque et qu'un mélange est au moins aussi bon que la distribution la plus défavorable, nous obtenons . L(X)L(Y)XYXyYL(Xy)=L(X)L(XY)L(X) 

Ce théorème signifie que si vous XOR deux séquences pseudo-aléatoires générées à l'aide de deux clés indépendantes , le résultat est toujours au moins aussi bon que la meilleure séquence étant XORed, en ce qui concerne toute mesure aléatoire aléatoire.

En pratique, pour utiliser deux clés indépendantes, nous étendons probablement une clé à deux de manière pseudo-aléatoire. Les deux clés ne sont alors pas indépendantes. Cependant, si nous utilisons une méthode "coûteuse" pour étendre une clé en deux, nous nous attendons à ce que les deux clés résultantes soient "indépendantes", et donc que le théorème soit "moralement". Dans la cryptographie théorique, il existe des moyens de rendre cette déclaration précise.


Devons-nous alors XOR deux générateurs de nombres pseudo-aléatoires? Si nous ne sommes pas limités par la vitesse, c'est une bonne idée. Mais en pratique, nous avons une limite de vitesse. Nous pouvons alors poser la question suivante. Supposons qu'on nous donne deux PRNG, chacun avec un paramètre qui contrôle le temps d'exécution (et donc la force) du générateur. Par exemple, pourrait être la longueur d'un LFSR ou le nombre de tours. Supposons que nous utilisions un PRNG avec le paramètre , l'autre avec le paramètre et XOR le résultat. Nous pouvons supposer que , de sorte que le temps total d'exécution est constant. Quel est le meilleur choix deTTT1T2T1+T2=tT1,T2? Ici, il y a un compromis auquel il est difficile de répondre en général. Il se peut que le réglage soit bien pire que ou .(t/2,t/2)(t,0)(0,t)

Le meilleur conseil ici est de s'en tenir à un PRNG populaire qui est considéré comme fort. Si vous pouvez consacrer plus de temps à la génération de votre séquence, effectuez XOR plusieurs copies, en utilisant des clés indépendantes (ou des clés générées en développant une clé unique à l'aide d'un PRNG coûteux).

Yuval Filmus
la source
Les commentaires ne sont pas pour une discussion prolongée; cette conversation a été déplacée pour discuter . Une fois que vous avez terminé de manière constructive, veuillez modifier la réponse pour incorporer les résultats de votre discussion.
Raphaël
4

Je vais essayer, car les conseils donnés dans certaines des réponses me dérangent suffisamment.

Soit des séquences binaires infinies générées par deux RNG (pas nécessairement des PRNG déterministes une fois l'état initial connu), et nous envisageons d'utiliser la séquence dans l’espoir d’améliorer un comportement dans un certain sens. Il y a beaucoup de différentes façons dont pourrait être considéré comme le meilleur ou pire par rapport à chacun des et ; En voici une petite poignée qui, à mon avis, est significative, utile et conforme à l’usage normal des mots «meilleur» et «pire»:X,YXYXYXY

  • (0) Probabilité que le vrai caractère aléatoire de la séquence augmente ou diminue
  • (1) Probabilité d’augmentation ou de diminution du caractère non aléatoire observable (probablement par rapport à un observateur qui applique un degré de contrôle donné)
  • (2) La gravité / l'évidence de la non-observabilité observable augmente ou diminue.

Pensons d’abord à (0), qui est le seul des trois à espérer être précisé. Notez que si, en fait, l'un des deux générateurs de signaux d'entrée est réellement aléatoire, impartial et indépendant de l'autre, le résultat XOR sera également réellement aléatoire et impartial. Dans cet esprit, considérons le cas où vous pensez que sont réellement des flux de bits isolés non aléatoires, mais vous n'êtes pas tout à fait sûr. Si sont les probabilités respectives que vous vous trompez sur chacune d'elles, alors la probabilité que ne soit pas vraiment aléatoire est alors , en fait beaucoup moins depuisX,YεX,εYXYεXεY<min{εX,εY}εX,εY sont supposés très proches de 0 ("vous les croyez vraiment aléatoires"). Et en fait, c’est encore mieux que cela, lorsque nous prenons également en compte la possibilité de étant réellement indépendant même quand aucun d’eux n’est vraiment aléatoire: Nous pouvons donc en conclure que dans le sens (0), XOR ne peut pas nuire et peut potentiellement beaucoup aider.X,Y

Pr(XY not truly random)min{Pr(X not truly random),Pr(Y not truly random),Pr(X,Y dependent)}.

Cependant, (0) n'est pas intéressant pour les PRNG, car dans le cas de ces derniers, aucune des séquences en question n'a de chance d'être réellement aléatoire.

Par conséquent, pour cette question, qui concerne en fait les PRNG, nous devons parler de quelque chose comme (1) ou (2). Puisque ce sont des propriétés et des quantités telles que "observable", "sévère", "évident", "apparent", nous parlons maintenant de la complexité de Kolmogorov, et je ne vais pas essayer de le préciser. Mais j'irai jusqu'à faire l'affirmation sans controverse, espérons-le, selon laquelle "01100110 ..." (période = 4) est pire que "01010101 ..." (période = 2), ce qui est pire que " 00000000 ... "(constante).

Maintenant, on peut supposer que (1) et (2) suivront la même tendance que (0) et que, par conséquent, la conclusion "XOR ne peut pas nuire" pourrait encore être valable. Cependant, notez la possibilité importante que ni ni soit visiblement non aléatoire, mais que leurs corrélations font que soit remarquablement non aléatoire. Le cas le plus grave en est évidemment lorsque (ou ), auquel cas est constant, le pire de tous les résultats possibles; en général, il est facile de voir que, indépendamment de la qualité de et de ,XYXYX=YX=not(Y)XYXYXet doivent être "proches" de l'indépendance pour que leur xor soit non-observable-non-aléatoire. En fait, être dépendant non-observable peut raisonnablement être défini comme étant étant non-observable-non-aléatoire.YXY

Une telle dépendance par surprise s'avère être un très gros problème.


Un exemple de ce qui ne va pas

La question dit "J'exclue l'exemple commun de plusieurs registres à décalage à retour linéaire fonctionnant ensemble car ils appartiennent à la même famille". Mais je vais exclure cette exclusion pour le moment, afin de donner un exemple très simple et réel du genre de choses qui peuvent mal tourner avec XORing.

Mon exemple sera une ancienne implémentation de rand () qui était sur une version d’Unix vers 1983. IIRC, cette implémentation de la fonction rand () avait les propriétés suivantes:

  • la valeur de chaque appel à rand () était de 15 bits pseudo-aléatoires, c'est-à-dire un nombre entier compris dans la plage [0, 32767).
  • valeurs de retour successives alternées pair-impair-pair-impair; c'est-à-dire que le bit le moins significatif a alterné 0-1-0-1 ...
  • le bit le moins significatif suivant avait la période 4, le suivant après la période 8, ... donc le bit de poids fort avait la période .215
  • Par conséquent, la séquence de valeurs de retour de 15 bits de rand () était périodique avec la période .215

Je suis incapable de trouver le code source d' origine, mais je devine de assemblant quelques messages de dans https://groups.google.com/forum/#!topic/comp.os.vms/9k4W6KrRV3A que il a précisément fait ce qui suit (code C), ce qui concorde avec ma mémoire des propriétés ci-dessus:

#define RAND_MAX 32767
static unsigned int next = 1;
int rand(void)
{
    next = next * 1103515245 + 12345;
    return (next & RAND_MAX);
}
void srand(seed)
unsigned int seed;
{
    next = seed;
}

Comme on pourrait l’imaginer, essayer d’utiliser ce rand () de différentes manières a été source de nombreuses déceptions.

Par exemple, à un moment donné, j’ai essayé de simuler une séquence de lancers de pièces aléatoires en prenant à plusieurs reprises:

rand() & 1

c'est-à-dire le bit le moins significatif. Le résultat a été une simple alternance tête-queue-tête-queue. C'était difficile à croire au début (ça doit être un bug dans mon programme!), Mais après m'être convaincu que c'était vrai, j'ai essayé d'utiliser le bit suivant le moins significatif. Ce n'est pas beaucoup mieux, comme indiqué précédemment - ce bit est périodique avec la période 4. Continuer à explorer successivement les bits les plus élevés a révélé le motif que j'ai noté précédemment: chaque bit de poids à cet égard, le bit de poids fort était le plus utile de tous. Notez cependant qu'il n'y avait pas de seuil noir et blanc "le bit est utile, le bit n'est pas utile" ici; tout ce que nous pouvons vraiment dire, c’est que les positions des bits numérotés présentaient divers degrés d’utilité / d’inutilité.ii1

J'ai aussi essayé des choses comme brouiller davantage les résultats ou XORing ensemble les valeurs renvoyées par plusieurs appels à rand (). XORing des paires de valeurs successives rand () était un désastre, bien sûr - il en résultait tous les nombres impairs! Pour mes besoins (à savoir produire une séquence "apparemment aléatoire" de retournements de pièces), le résultat de parité constante du XOR était encore pire que le comportement pair-impair alternatif de l'original.

Une légère variation place cela dans le cadre d'origine: c'est-à-dire que soit la séquence des valeurs de 15 bits renvoyées par rand () avec un germe donné , et la séquence d'un germe différent. . Encore une fois, sera une suite de nombres tous pairs ou tous impairs, ce qui est pire que le comportement original alternant pair / impair.XsXYsYXY

En d’autres termes, c’est un exemple où XOR a aggravé la situation au sens de (1) et (2), par toute interprétation raisonnable. C'est pire à plusieurs autres égards:

  • (3) Le bit le moins significatif XORed est évidemment polarisé, c'est-à-dire qu'il a des fréquences inégales de 0 et de 1, contrairement à toute position de bit numérotée dans l'une des entrées qui sont toutes non biaisées.
  • (4) En fait, pour chaque position de bit, il y a des paires de graines pour lesquelles cette position de bit est biaisée dans le résultat XOR, et pour chaque paire de graines, il y a (au moins 5) positions de bit qui sont biaisées dans le XOR. résultat.
  • (5) La période de la séquence complète des valeurs de 15 bits dans le résultat XOR est égale à 1 ou , comparée à pour les originaux.214215

Aucun de (3), (4), (5) n’est évident, mais ils sont tous facilement vérifiables.


Enfin, considérons la réintroduction de l’interdiction des GNRP de la même famille. Le problème ici, je pense, est qu'il n'est jamais vraiment clair si deux PRNG appartiennent "à la même famille", jusqu'à ce que / à moins que quelqu'un ne commence à utiliser le XOR et remarque (ou un attaquant remarque) que les choses ont empiré (1) et (2), c'est-à-dire jusqu'à ce que des modèles non aléatoires dans la sortie franchissent le seuil de non-remarqué à remarqué / embarrassant / désastreux et qu'à ce stade, il est trop tard.

Je suis alarmé par d’autres réponses ici qui donnent des conseils sans réserve «XOR ne peut pas faire de mal» sur la base de mesures théoriques qui me semblent faire un piètre travail de modélisation de ce que la plupart des gens considèrent comme «bon» et «mauvais». PRNG dans la vraie vie. Ce conseil est contredit par des exemples clairs et flagrants dans lesquels XOR aggrave la situation, tels que l'exemple de rand () donné ci-dessus. Bien qu'il soit concevable que des PRNG relativement "forts" puissent systématiquement afficher le comportement inverse lorsque XOR est identique à celui du jouet PRNG qui était rand (), faisant ainsi de XOR une bonne idée pour eux, je n'ai vu aucune preuve dans cette direction, théorique ou empirique, il me semble donc déraisonnable de supposer que cela se produit.

Personnellement, après avoir été mordu par XORing rand () s dans ma jeunesse et par d’innombrables corrélations surprises tout au long de ma vie, j’ai peu de raisons de penser que le résultat sera différent si j’essaie à nouveau une tactique similaire. C'est pourquoi, personnellement, je serais très réticent à l'idée de combiner plusieurs PRNG avec XOR à moins que des analyses et des vérifications très approfondies aient été effectuées pour me donner une certaine assurance que cela pourrait être fait en toute sécurité pour les GNR en question. En tant que traitement potentiel lorsque j'ai peu confiance en un ou plusieurs PRNGs, il est peu probable que XORing augmente ma confiance en moi, il est donc peu probable que je l'utilise à cette fin. J'imagine que la réponse à votre question est qu'il s'agit d'un sentiment largement répandu.

Don Hatch
la source
Alors, comment expliquez-vous l’utilisation de l’A5 / 1 par des milliards de personnes?
Paul Uszak
@PaulUszak Je n'en ai aucune idée. Est-ce que l'A5 / 1 utilisé par des milliards de personnes contredit ce que j'ai dit?
Don Hatch,
C'est trois prngs (en fait de la même famille) réunis pour en former un meilleur qui vous dérange et vous alarme ...
Paul Uszak
Ce qui me dérange et qui m'inquiète, c'est le conseil inconditionnel "si vous n'êtes pas sûr, allez-y et rassemblez une foule de VNR, cela ne peut pas aggraver les choses". Je ne voulais pas dire ou impliquer que XOR est mauvais dans tous les cas, et je n’ai aucune opinion du tout sur A5 / 1 ou sur l’utilisation de XOR dans celui-ci. Est-ce que cela aiderait si je changeais mon résumé final stupide pour clarifier cela?
Don Hatch,
1
J'ai remplacé le simpliste "juste dire non aux XORing RNGs" à la fin par quelque chose de plus réel et, espérons-le, moins trompeur.
Don Hatch
0

AVERTISSEMENT: Cette réponse est strictement sur "Nous ne le faisons pas" et non pas "voici la preuve mathématique pourquoi cela peut ou ne peut pas fonctionner". Je ne prétends pas que XOR introduit (ou non) des vulnérabilités cryptographiques. Ce que je veux dire, c’est que l’expérience nous montre que même les régimes les plus simples entraînent presque toujours des conséquences imprévues - et c’est pourquoi nous les évitons.

Le «caractère aléatoire» n’est que la partie visible de l’iceberg en ce qui concerne les GNA et les GNRP. Il existe d'autres qualités importantes, par exemple l'uniformité.

Imaginez un dés commun qui est un assez bon RNG en soi. Mais maintenant, supposons que vous ayez besoin d’une plage 1-5 au lieu de 1-6. La première chose qui me vient à l’esprit est simplement d’effacer le visage 6 et de le remplacer par un 1. Le «caractère aléatoire» subsiste (les résultats sont toujours vraiment aléatoires), mais l’uniformité en souffre énormément: maintenant, 1 est deux fois plus probable que d’autres résultats.

La combinaison des résultats de plusieurs GNA donne une pente similaire. Par exemple. ajouter simplement 2 dés jette complètement toute uniformité, puisque "7" est maintenant 6 fois plus probable que "2" ou "12". Je conviens que XOR a l’air meilleur qu’un ajout au premier coup d’œil, mais dans les PRNG, rien ne se passe comme au premier coup d’œil.

C'est pourquoi nous avons tendance à nous en tenir à des implémentations connues - parce que quelqu'un a consacré beaucoup de temps et d'argent à les rechercher et que toutes les lacunes sont bien connues, comprises et peuvent être contournées. Lorsque vous déployez les vôtres, vous créez potentiellement des vulnérabilités et vous devez déployer des efforts similaires pour le prouver. Comme le montre l'exemple d'ajout de dés, la combinaison peut ne pas être très différente de la création d'un nouveau à partir de zéro.

La sécurité est une chaîne, aussi forte que son composant le plus faible. Une règle de base en matière de sécurité: chaque fois que vous combinez deux choses, vous obtenez généralement une somme de défauts, pas une somme de forces.

Agent_L
la source
7
Fortement en désaccord. Si vous XOR une séquence vraiment aléatoire avec une séquence arbitraire, vous obtenez toujours une séquence vraiment aléatoire. De même, si vous XOR deux séquences pseudo-aléatoires indépendantes (c'est-à-dire générées avec des clés différentes), vous obtenez quelque chose au moins aussi fort que chacune individuellement.
Yuval Filmus
3
Cela me semble faux. Le cas habituel ici est que je pense avoir deux GRN de très haute qualité produisant des bits essentiellement vraiment aléatoires, mais il y a un risque minime que je puisse me tromper (peut-être de manière flagrante) sur l’un (ou beaucoup moins) des deux. Si je les combine ensemble, tant que j'ai raison pour au moins l'un d'entre eux, le résultat sera vraiment aléatoire et je vais bien. Donc, en les combinant, j'ai réduit mes chances d'avoir un mauvais RNG d'epsilon / 2 à epsilon ^ 2, ce qui est certainement une victoire. Je soupçonne une dynamique similaire, même dans les cas moins difficiles.
Don Hatch
2
Je ne suis toujours pas convaincu. Quand j'ai écrit "vraiment aléatoire" je voulais dire "uniformément aléatoire". Si vous XOR une séquence uniformément aléatoire avec une séquence arbitraire, vous obtenez une séquence uniformément aléatoire.
Yuval Filmus
2
@DonHatch Certainement, cela serait admissible. Supposons que votre PRNG génère une séquence de longueur 100, puis une version bruyante de la même séquence, etc. Supposons que la corrélation au niveau des bits de la seconde copie avec la première est . La séquence vérifie . Depuis, il est juste de dire que les corrélations n’ont pas été "grossièrement grossies", mais plutôt réduites. Z i = X iY i Pr [ Z i + 100 = Z i ] = ( 1 + ε 2 ) / 2 ε 2| e |Pr[Xi+100=Xi]=(1+ϵ)/2Zi=XiYiPr[Zi+100=Zi]=(1+ϵ2)/2ϵ2|ϵ|
Yuval Filmus
3
@YuvalFilmus Vous avez probablement raison de dire que la corrélation entre les éléments i et i + 100 a été considérablement réduite, mais ce n'est pas le problème. Pour un exemple très concret et réel: je me souviens que la vieille implémentation de rand () sur unix avait un comportement périodique dans le bit d’ordre le plus bas de chaque entier de 31 bits renvoyé, ce que la plupart des gens n’ont pas remarqué. Si cette séquence d’ints avec une copie décalée de lui-même (ce qui est ce que vous obtenez lorsque vous utilisez une graine différente) de taille de décalage déplorable, vous obtiendrez tous les nombres pairs. C'est bien pire que le problème de la séquence originale, dans la plupart des cas.
Don Hatch