Jouons au poker informatique, juste toi, moi et un serveur en qui nous avons confiance. Le serveur utilise un générateur de nombres pseudo-aléatoires qui est initialisé avec une graine de 32 bits juste avant de jouer. Il y a donc environ 4 milliards de jeux de cartes possibles.
J'ai cinq cartes en main - apparemment, nous ne jouons pas au Texas Hold 'Em. Supposons que les cartes soient distribuées une à moi, une à toi, une à moi, une à toi, et ainsi de suite. J'ai donc les première, troisième, cinquième, septième et neuvième cartes du jeu.
Plus tôt, j'ai lancé le générateur de nombres pseudo-aléatoires quatre milliards de fois, une fois avec chaque graine, et j'ai noté la première carte générée pour chacune dans une base de données. Supposons que ma première carte soit la reine de pique. Cette carte n'apparaît qu'une fois en tant que première carte dans un jeu sur 52 de ces jeux possibles. Nous avons donc réduit le nombre de jeux possibles de quatre milliards à environ 80 millions.
Supposons que ma deuxième carte soit le trois de cœur. Je lance maintenant mon RNG 80 millions de fois de plus en utilisant les 80 millions de graines qui produisent la reine de pique comme premier numéro. Cela me prend quelques secondes. Je note tous les jeux de cartes qui produisent le trois de cœur comme troisième carte - la deuxième carte de ma main. Cela ne représente à nouveau qu'environ 2 % des jeux de cartes, ce qui nous ramène à 2 millions de jeux de cartes.
Supposons que la troisième carte de ma main soit le 7 de trèfle. J'ai une base de données de 2 millions de jeux qui distribuent mes deux cartes ; je lance mon RNG 2 millions de fois de plus pour trouver les 2% de ces jeux qui produisent le 7 de trèfle comme troisième carte, et nous ne sommes plus qu'à 40 000 jeux.
Vous voyez comment ça se passe. Je fais tourner mon RNG 40000 fois de plus pour trouver toutes les graines qui produisent ma quatrième carte, ce qui nous amène à 800 jeux de cartes, puis je le fais tourner 800 fois de plus pour obtenir les ~20 graines qui produisent ma cinquième carte, et maintenant je viens de générer ces vingt jeux de cartes et je sais que vous avez une des vingt mains possibles. De plus, j'ai une très bonne idée de ce que je vais tirer ensuite.
Vous voyez maintenant pourquoi le véritable caractère aléatoire est important ? De la façon dont vous le décrivez, vous pensez que distribution est importante, mais la distribution n'est pas ce qui rend un processus aléatoire. Imprévisibilité est ce qui rend un processus aléatoire.
UPDATE
D'après les commentaires (maintenant supprimés en raison de leur nature non constructive), au moins 0,3 % des personnes qui ont lu cet article ne comprennent pas où je veux en venir. Quand les gens argumentent contre des points que je n'ai pas soulevés, ou pire, argumentent にとって points que je a fait faire sur la en supposant que je ne les ai pas faites, je sais alors que je dois m'expliquer plus clairement et plus soigneusement.
Il semble y avoir une confusion particulière autour du mot distribution Je tiens donc à rappeler les usages avec précaution.
Les questions qui se posent sont les suivantes :
- En quoi les nombres pseudo-aléatoires et les nombres réellement aléatoires diffèrent-ils ?
- Pourquoi cette différence est-elle importante ?
- Les différences ont-elles quelque chose à voir avec la distribution de la sortie du PRNG ?
Commençons par considérer le parfait pour générer un jeu de cartes aléatoire avec lequel jouer au poker. Nous verrons ensuite en quoi les autres techniques de génération de jeux de cartes sont différentes, et s'il est possible de tirer parti de cette différence.
Commençons par supposer que nous avons une boîte magique étiquetée TRNG . En entrée, nous lui donnons un nombre entier n supérieur ou égal à un, et en sortie, il nous donne un nombre vraiment aléatoire compris entre un et n, inclus. La sortie de la boîte est entièrement imprévisible (lorsqu'on lui donne un nombre différent de un) et que tout nombre compris entre un et n est aussi probable qu'un autre ; c'est-à-dire que les distribution es uniforme . (Il existe d'autres contrôles statistiques plus avancés du caractère aléatoire que nous pourrions effectuer ; j'ignore ce point car il n'est pas pertinent pour mon argument. TRNG est parfaitement statistiquement aléatoire par hypothèse).
Nous commençons avec un jeu de cartes non mélangé. Nous demandons à la boîte un nombre entre 1 et 52 -- c'est-à-dire, TRNG(52) . Quel que soit le nombre qu'elle donne en retour, nous comptons ce nombre de cartes de notre jeu trié et nous retirons cette carte. Elle devient la première carte du jeu mélangé. Ensuite, nous demandons TRNG(51) et faites de même pour sélectionner la deuxième carte, et ainsi de suite.
Une autre façon de voir les choses est la suivante : il y a 52 ! = 52 x 51 x 50 ... x 2 x 1 decks possibles, soit environ 2 226 . Nous avons choisi l'un d'entre eux au hasard.
Maintenant, nous distribuons les cartes. Quand je regarde mes cartes, j'ai aucune idée quelles cartes vous avez. (En dehors du fait évident que vous n'avez aucune des cartes que j'ai.) Il peut s'agir de n'importe quelles cartes, avec la même probabilité.
Permettez-moi donc de m'assurer que j'explique clairement la situation. Nous avons distribution uniforme de chaque sortie individuelle de TRNG(n) chacun choisit un nombre entre 1 et n avec une probabilité de 1/n. De plus, le résultat de ce processus est que nous avons choisi l'un des 52 ! jeux possibles avec une probabilité de 1/52 !, donc la distribution sur l'ensemble des jeux possibles es également uniforme.
Très bien.
Supposons maintenant que nous ayons une boîte moins magique, étiquetée PRNG . Avant que vous puissiez l'utiliser, il doit être semé avec un nombre non signé de 32 bits.
ASIDE : Pourquoi 32 ? Ne pourrait-on pas l'ensemencer avec un nombre de 64, 256 ou 10000 bits ? Bien sûr. Mais (1) en pratique, la plupart des PRNGs du commerce sont ensemencés avec un nombre de 32 bits, et (2) si vous disposez de 10000 bits d'aléa pour faire l'ensemencement, pourquoi utiliser un PRNG ? Vous disposez déjà d'une source de 10000 bits d'aléa !
Quoi qu'il en soit, revenons à la façon dont le PRNG fonctionne : une fois qu'il est ensemencé, vous pouvez l'utiliser de la même façon que vous utilisez TRNG . C'est-à-dire que vous lui passez un nombre, n, et il vous renvoie un nombre compris entre 1 et n, inclus. De plus, la distribution de cette production est plus ou moins uniforme. . C'est-à-dire que lorsque nous demandons PRNG pour un nombre compris entre 1 et 6, on obtient 1, 2, 3, 4, 5 ou 6 environ un sixième du temps, quelle que soit la graine.
Je tiens à insister plusieurs fois sur ce point car il semble être celui qui déroute certains commentateurs. La distribution du PRNG est uniforme de deux manières au moins. Premièrement, supposons que nous choisissions une graine particulière. Nous nous attendons à ce que la séquence PRNG(6), PRNG(6), PRNG(6)... un million de fois produirait une distribution uniforme de nombres entre 1 et 6. Et deuxièmement, si nous choisissions un million de graines différentes et appelions PRNG(6) 一旦 pour chaque graine, là encore on s'attendrait à une distribution uniforme de nombres de 1 à 6. L'uniformité du PRNG dans l'une ou l'autre de ces opérations n'est pas pertinente pour l'attaque que je décris. .
Ce processus est dit pseudo-aléatoire parce que le comportement de la boîte est en fait entièrement déterministe ; elle choisit entre 2 possibilités. 32 les comportements possibles en fonction de la graine. C'est-à-dire, une fois qu'il est ensemencé, PRNG(6), PRNG(6), PRNG(6), ... produit un séquence de nombres avec une distribution uniforme, mais cette séquence est entièrement déterminée par la semence. Pour une séquence donnée d'appels, disons PRNG(52), PRNG(51) ... et ainsi de suite, il n'y a que 2 32 séquences possibles. La graine choisit essentiellement celle que nous obtenons.
Pour générer un jeu, le serveur génère maintenant une graine. (Comment ? Nous reviendrons sur ce point.) Puis il appelle PRNG(52) , PRNG(51) et ainsi de suite pour générer le jeu, comme précédemment.
Ce système est sensible à l'attaque que j'ai décrite. Pour attaquer le serveur, nous commençons, à l'avance, par ensemencer notre propre copie de la boîte avec 0 et demandons PRNG(52) et écrivez-le. Puis on réensemence avec 1, on demande PRNG(52) et écrivez-le, jusqu'à 2. 32 -1.
Maintenant, le serveur de poker qui utilise le PRNG pour générer des jeux de cartes doit générer une graine d'une manière ou d'une autre. La manière dont ils le font n'a pas d'importance. Ils pourraient appeler TRNG(2^32) pour obtenir une graine vraiment aléatoire. Ou bien ils pourraient prendre l'heure actuelle comme graine, ce qui n'est pas du tout aléatoire ; je sais quelle heure il est autant que vous. Le point de mon attaque est que cela n'a pas d'importance, parce que j'ai ma base de données . Lorsque je vois ma première carte, je peux éliminer 98% des graines possibles. Lorsque je vois ma deuxième carte, je peux éliminer 98% de plus, et ainsi de suite, jusqu'à ce que je puisse finalement descendre à une poignée de graines possibles, et savoir avec une grande probabilité ce que vous avez en main.
Maintenant, encore une fois, je veux souligner que l'hypothèse ici est que si nous avons appelé PRNG(6) un million de fois, nous obtiendrions chaque nombre environ un sixième du temps. . Cette distribution est (plus ou moins) uniforme y si l'uniformité de cette distribution est tout ce qui vous intéresse. c'est très bien. Le but de la question était y a-t-il d'autres choses que la distribution de PRNG(6) dont nous nous soucions ? et la réponse est oui . Nous nous préoccupons de imprévisibilité également.
Une autre façon de voir le problème est que même si la distribution d'un million d'appels à PRNG(6) pourrait être bien, parce que le PRNG choisit parmi seulement 2 32 comportements possibles, il ne peut pas générer tous les jeux possibles. Il ne peut générer que 2 32 de la 2 226 decks possibles ; une fraction minuscule. Donc la distribution sur l'ensemble de tous les ponts est très mauvais. Mais encore une fois, l'attaque fondamentale ici est basée sur notre capacité à réussir prédire le comportement passé et futur de PRNG à partir d'un petit échantillon de sa production.
Je vais le dire une troisième ou quatrième fois pour être sûr que ça rentre dans le crâne. Il y a trois distributions ici. D'abord, la distribution du processus qui produit la graine aléatoire de 32 bits. Cela peut être parfaitement aléatoire, imprévisible et uniforme et l'attaque fonctionnera toujours . Deuxièmement, la distribution d'un million d'appels à PRNG(6) . Cela peut être parfaitement uniforme et l'attaque fonctionnera quand même. Troisièmement, la distribution des jeux choisis par le processus pseudo-aléatoire que j'ai décrit. Cette distribution est extrêmement pauvre ; seule une infime partie des jeux IRL possibles peut être choisie. L'attaque dépend de la prévisibilité du comportement du PRNG sur la base d'une connaissance partielle de sa sortie .
ASIDE : Cette attaque nécessite que l'attaquant connaisse ou soit capable de deviner l'algorithme exact utilisé par le PRNG. La question de savoir si cela est réaliste ou non reste ouverte. Cependant, lors de la conception d'un système de sécurité, vous devez le concevoir de manière à ce qu'il soit protégé contre les attaques, même si l'attaquant connaît tous les algorithmes du programme. . En d'autres termes, la partie d'un système de sécurité qui doit rester secrète pour que le système soit sûr est appelée la "clé". Si la sécurité de votre système dépend du fait que les algorithmes que vous utilisez restent secrets, alors votre clé contient ces algorithmes . C'est un extrêmement une position faible dans laquelle se trouver !
On avance.
Supposons maintenant que nous ayons une troisième boîte magique appelée CPRNG . Il s'agit d'une version cryptée de PRNG . Il prend une graine de 256 bits plutôt qu'une graine de 32 bits. Il partage avec PRNG la propriété que la graine choisit parmi l'une des 2 256 comportements possibles. Et comme nos autres machines, elle possède la propriété qu'un grand nombre d'appels à CPRNG(n) produisent une distribution uniforme de résultats entre 1 et n : chacun se produit 1/n du temps. Pouvons-nous exécuter notre attaque contre elle ?
Notre attaque originale nous oblige à stocker 2 32 les correspondances entre les graines et les PRNG(52) . Mais 2 256 est un nombre beaucoup plus grand ; il est totalement infaisable d'exécuter CPRNG(52) ce nombre de fois et stocker les résultats.
Mais supposons qu'il y ait autre manière de prendre la valeur de CPRNG(52) et en déduire un fait sur la graine ? Nous avons été assez stupides jusqu'à présent, en forçant brutalement toutes les combinaisons possibles. Peut-on regarder à l'intérieur de la boîte magique, comprendre comment elle fonctionne et déduire des faits sur la graine en se basant sur le résultat ?
Non. Les détails sont trop compliqués à expliquer, mais les CPRNG sont intelligemment conçus pour qu'il soit infaisable de déduire cualquier fait utile sur la graine à partir de la première sortie de CPRNG(52) ou de cualquier sous-ensemble de la sortie, quelle que soit la taille .
OK, supposons maintenant que le serveur utilise CPRNG pour générer des platines. Il a besoin d'une graine de 256 bits. Comment choisit-il cette graine ? Si elle choisit une valeur qu'un attaquant peut prédire puis soudainement l'attaque redevient viable . Si nous pouvons déterminer que parmi les 2 256 graines possibles, seuls quatre milliards d'entre eux sont susceptibles d'être choisis par le serveur, alors nous sommes de retour en affaires . Nous pouvons à nouveau monter cette attaque, en ne faisant attention qu'au petit nombre de graines qui peuvent être générées.
Le serveur doit donc faire en sorte que le nombre de 256 bits soit uniformément distribué -- c'est-à-dire que chaque graine possible est choisie avec une probabilité de 1/2 256 . En fait, le serveur devrait appeler TRNG(2^256)-1 pour générer la semence pour CPRNG .
Et si je pouvais pirater le serveur et y pénétrer pour voir quelle graine a été choisie ? Dans ce cas, l'attaquant connaît le passé et le futur complets du CPRNG. . L'auteur du serveur doit se prémunir contre cette attaque ! (Bien sûr, si je réussis à monter cette attaque, je pourrai probablement aussi transférer l'argent directement sur mon compte bancaire, ce qui n'est peut-être pas si intéressant. Le fait est que la graine doit être un secret difficile à deviner, et un nombre vraiment aléatoire de 256 bits est assez difficile à deviner).
Pour en revenir à mon point précédent sur la défense en profondeur, la graine de 256 bits est le meilleur moyen d'assurer la sécurité. clé à ce système de sécurité. L'idée d'un CPRNG est que le système est sécurisé tant que la clé est sécurisée Même si tous les autres faits concernant l'algorithme sont connus, tant que vous pouvez garder la clé secrète, les cartes de l'adversaire sont imprévisibles.
OK, donc la graine doit être à la fois secrète et uniformément distribuée car si elle ne l'est pas, nous pouvons monter une attaque. Nous avons par hypothèse que la distribution des sorties de CPRNG(n) est uniforme. Qu'en est-il de la distribution sur l'ensemble de tous les jeux de cartes possibles ?
Vous pourriez dire : il y a 2 256 séquences possibles produites par le CPRNG, mais il n'y en a que 2. 226 decks possibles. Il y a donc plus de séquences possibles que de jeux de cartes, donc tout va bien ; chaque jeu de cartes possible-IRL est maintenant (avec une forte probabilité) possible dans ce système. Et c'est un bon argument, sauf que...
2 226 est seulement un approximation de 52 ! Divisez-le. 2 256 /52 ! ne peut pas être un nombre entier car, d'une part, 52 ! est divisible par 3 mais aucune puissance de deux ne l'est ! Puisqu'il ne s'agit pas d'un nombre entier, nous nous trouvons maintenant dans la situation où tous les jeux de cartes sont possible mais certains jeux sont plus probables que d'autres .
Si cela n'est pas clair, considérez la situation avec des chiffres plus petits. Supposons que nous ayons trois cartes, A, B et C. Supposons que nous utilisions un PRNG avec une graine de 8 bits, il y a donc 256 graines possibles. Il existe 256 sorties possibles de PRNG(3) en fonction de la graine ; il est impossible qu'un tiers d'entre elles soient A, un tiers B et un tiers C, car 256 n'est pas divisible de façon égale par 3. Il doit y avoir un petit biais en faveur de l'une d'entre elles.
De même, 52 ne se divise pas en 2. 256 Il doit donc y avoir un parti pris pour certaines cartes en tant que première carte choisie et un parti pris pour d'autres.
Dans notre système original avec une graine de 32 bits, il y avait un biais massif et la grande majorité des jeux possibles n'étaient jamais produits. Dans ce système, tous les jeux peuvent être produits, mais la distribution des platines est toujours défectueuse . Certaines terrasses sont très légèrement plus probable que d'autres.
Maintenant la question est : avons-nous une attaque basée sur cette faille ? et la réponse est en pratique, probablement pas . Les CPRNG sont conçus de manière à ce que si la graine est vraiment aléatoire puis il est impossible, d'un point de vue informatique, de faire la différence entre CPRNG y TRNG .
OK, alors résumons.
En quoi les nombres pseudo-aléatoires et les nombres réellement aléatoires diffèrent-ils ?
Ils diffèrent par le niveau de prévisibilité qu'ils présentent.
- Les nombres véritablement aléatoires ne sont pas prévisibles.
- Tous les nombres pseudo-aléatoires sont prévisibles si la graine peut être déterminée ou devinée.
Pourquoi cette différence est-elle importante ?
Parce qu'il y a des applications où la sécurité du système repose sur imprévisibilité .
- Si un TRNG est utilisé pour choisir chaque carte, le système est inattaquable.
- Si un CPRNG est utilisé pour choisir chaque carte, le système est sûr si la graine est à la fois imprévisible et inconnue.
- Si l'on utilise un PRNG ordinaire avec un petit espace de semence, le système n'est pas sûr, que la semence soit imprévisible ou inconnue ; un espace de semence suffisamment petit est sensible aux attaques par force brute du type que j'ai décrit.
La différence a-t-elle quelque chose à voir avec la distribution de la sortie du PRNG ?
L'uniformité de la distribution ou son absence pour appels individuels a RNG(n) n'est pas pertinent pour les attaques que j'ai décrites.
Comme nous l'avons vu, les deux PRNG y CPRNG produisent de mauvaises distributions de la probabilité de choisir un jeu de cartes individuel parmi tous les jeux de cartes possibles. Le site PRNG est bien pire, mais les deux ont des problèmes.
Une dernière question :
Si TRNG est tellement meilleur que CPRNG, qui est à son tour tellement meilleur que PRNG, pourquoi quelqu'un utilise-t-il CPRNG ou PRNG ?
Pour deux raisons.
Premièrement : les dépenses. TRNG est coûteux . Il est difficile de générer des nombres véritablement aléatoires. Les CPRNGs donnent de bons résultats pour un nombre arbitraire d'appels avec seulement un appel à TRNG pour la semence. L'inconvénient est bien sûr que vous devez garder cette graine secrète .
Deuxièmement : parfois nous 欲する la prévisibilité et tout ce qui nous importe est une bonne distribution. Si vous générez des données "aléatoires" en tant qu'entrées de programme pour une suite de tests, et qu'elles révèlent un bogue, il serait bon que l'exécution de la suite de tests produise à nouveau le bogue !
J'espère que c'est maintenant beaucoup plus clair.
Enfin, si vous avez aimé cet article, vous apprécierez peut-être d'autres lectures sur le thème du hasard et des permutations :
