Jeux en ligne – Bonnes pratiques et erreurs fréquentes

/, Technique/Jeux en ligne – Bonnes pratiques et erreurs fréquentes

Jeux en ligne – Bonnes pratiques et erreurs fréquentes

Par | 2014-07-21T16:55:36+01:00 juillet 21st, 2014|Actualité, Technique|

Depuis juin 2010 et l’ouverture des jeux et paris en ligne, les opérateurs de jeux en ligne doivent garantir la sécurité de leurs logiciels de jeux, des joueurs et des transactions effectuées sur leurs sites Internet. Dans ce but, les opérateurs doivent obtenir une certification basée sur des contraintes techniques, juridiques et financières auprès de L’Autorité de Régulation des Jeux En Ligne (ARJEL).

L’ARJEL a officiellement référencé ITrust comme Organisme Certificateur (Organismes certificateurs). L’organisme certificateur est en charge de vérifier le respect de ces contraintes en vue de délivrer la certification à l’opérateur de jeux.

 

Retour d’expérience

Nos différents audits dans ce domaine nous ont fait remonter deux erreurs fondamentales systématiquement constatées dans les algorithmes de jeux de carte en ligne. Ces erreurs sont dues à un effet de mimétisme basé sur une information initiale biaisée. Notre but est donc de fournir un démenti à ces pratiques largement usitées dans le domaine des jeux en ligne pour aider à prévenir leur future utilisation.

 

L’algorithme de battage

Le premier des problèmes constaté concerne l’algorithme de battage des cartes, celui qui permet de mélanger aléatoirement le paquet de carte (deck) pour obtenir un jeu équitable et imprévisible.
Un algorithme tout-fait est largement proposé sur Internet et repris par de nombreux opérateurs de jeux.
Voici son principe :

  • Les cartes sont réparties dans un tableau et sont triées dans l’ordre
  • Pour chaque case A de ce tableau, on tire au sort une case B et on intervertit A et B
  • Quand on a fait ceci pour toutes les cases du tableau, cela constitue une « passe »
  • On effectue 1000 passes

Un exemple d’implémentation serait :

for(int i = 0; i < 1000; i++){
for(int j = 0; j < tableau.size(); j++){
tableau.echange(this, j, aleatoire.get(0, tableau.size()-1));
}
}

Voici l’exemple d’une passe avec un tableau de 5 éléments :

articlejeuxenligne

Cette étape est donc répétée 1000 fois. A première vue, cet algorithme semble vraiment bien brasser le jeu.
Sur un jeu de 32 cartes (poker), en moyenne une carte changera donc de place 969 fois (chiffre calculé sans probabilités conditionnelles).

Et pourtant

Imaginons, pour simplifier, que nous avons un jeu de seulement 3 cartes, numérotées 1, 2 et 3. Étudions maintenant l’arbre des permutations possibles avec cet algorithme sur une seule passe :

articlejeuxenligne1

Le schéma montre le champ des possibles à chaque étape. Il commence par un tableau trié : 123. Au second niveau, on observe les possibilités d’inversions pour la première case : elle peut être inversée avec elle-même : 123, avec la deuxième : 213 ou avec la troisième : 321. Et ainsi de suite.

Il s’en suit que les probabilités d’apparition des différents paquets ne sont pas uniformes :

articlejeuxenligne2

Cet algorithme est en fait une variante biaisée de la version moderne de l’algorithme Fisher-Yates introduite par Durstenfeld et Knuth, aussi connue sous le nom de « Algorithme P » dans l’ouvrage : The Art of Computer Programming.

 

Pour corriger le biais induit par cette mauvaise variante de l’algorithme, une légère modification suffit. Au lieu de tirer une case au hasard parmi toutes les cases possibles, il faut la tirer parmi toutes les cases restantes à droite (plus la case actuellement traitée) :

articlejeuxenligne3

On a donc au départ le paquet trié 123. Sur la première case on est dans le même cas que l’algorithme précédent. Au niveau de la deuxième case, des cas sont éliminés. Ainsi depuis le paquet 213 par exemple, il n’est plus possible d’obtenir le paquet 123, puisque ça nécessiterait d’inverser le deuxième chiffre avec le premier (qui se trouve à gauche).

 

On peut voir que cet algorithme produit les mêmes paquets que le précédent (qui sont au nombre de 6) mais de façon plus simple et surtout équiprobable.
Ainsi la répartition des paquets est :

articlejeuxenligne4

Soit une distribution uniforme des paquets possibles. La correction de l’algorithme est donc très simple :

for(int i = 0; i < 1000; i++){
for(int j = 0; j < tableau.size(); j++){
tableau.échange(this, j, aleatoire.get(j, tableau.size()-1));
}
}

 

La Graine

L’autre faiblesse fondamentale que l’on retrouve régulièrement concerne l’utilisation du générateur de nombres pseudo-aléatoires (GNPA).

Celui-ci est trop souvent considéré comme une fin en soi sans que l’on s’attarde sur son fonctionnement et son utilisation. Or la qualité du produit d’un GNPA dépend intrinsèquement de son mode d’utilisation. Un des éléments majeurs de cette utilisation est la graine.
Pour comprendre ce qu’est une graine, il est nécessaire de savoir distinguer un GNA (générateur de nombres aléatoires) et un GNPA (générateur de nombres pseudo-aléatoires).

Le premier produit du chaos de façon imprédictible (comme les décimales de PI), il est extrêmement difficile de reproduire un tel générateur. On utilise souvent pour cela des dispositifs qui observent des évènements imprévisibles (vitesse d’écriture du disque dur, évènement quantique, etc.) qui se rapprochent d’un comportement chaotique mais sans qu’on ne puisse tout à fait prouver qu’il soit arbitraire. Les GNA que l’on utilise répondent donc au critère d’imprédictibilité de par notre propre limitation technique (nous n’avons actuellement pas les moyens techniques de connaitre la température qu’aura un processeur à un temps donné, pourtant celle-ci résulte logiquement d’évènements mesurables).

Le GNPA répond à la nécessité de pouvoir générer de l’aléa informatiquement en s’affranchissant de dispositifs physiques (couteux et encombrants). Seulement il n’est pas possible de créer d’évènement arbitraire à partir d’un système totalement déterministe, or dans un ordinateur, une même opération entraine systémiquement le même résultat (bien que Windows n’ait pas énormément contribué à rendre cette assertion intuitive). On utilise à la place des fonctions mathématiques complexes ayant des résultats très disparates et imitant en cela le caractère chaotique. On qualifie donc ces nombres de « pseudo-aléatoires ». Ces fonctions partent d’un nombre initial et le dégradent en une multitude d’autres nombres via des opérations complexes. Ce nombre initial est appelé « graine ». Or une même graine produira toujours la même suite de nombres pseudo-aléatoires, il est donc important que cette graine soit imprédictible et non divulguée.

On considère qu’une bonne utilisation d’un GNPA consiste à tirer au sort la graine grâce à un GNA (opération plutôt longue mais ayant une bonne qualité d’aléa). Cette graine est ensuite passée au GNPA qui peut produire tous les nombres pseudo-aléatoires qui en découlent (opération rapide).

 

C’est là que le bât blesse

Prenons l’exemple d’un jeu de poker de 32 cartes. Le nombre de paquets possibles est alors 32!, soit :

>>> Factoriel(32)
263130836933693530167218012160000000

Lequel de ces paquets sera utilisé pour une partie est décidé au moment du battage des cartes, grâce à l’algorithme que nous avons vu précédemment et qui utilise le GNPA pour tirer au sort la case à échanger.
Théoriquement tous les paquets possibles devraient avoir la même chance d’être produits. Or comme nous l’avons expliqué, deux graines identiques produisent la même séquence de nombres pseudo-aléatoires. Et si l’algorithme de battage utilise la même séquence, il mélangera les cartes de la même façon. Donc il y a autant de paquets différents possibles qu’il n’y a de graines possibles.

Généralement le GNPA est initialisé juste avant son utilisation, avec une graine générée au même moment. Cette méthode peut être problématique.

En effet la graine générée est souvent un entier basique de 32 bits, or un tel entier ne peut prendre que 4 294 967 296 valeurs différentes. La portion des paquets générables par rapport aux paquets possibles est donc :

>>> 4294967296.0/263130836933693530167218012160000000.0
1.632255400412188e-26

On ne peut donc produire que 0.000000000000000000000002% des paquets possibles

Le fait de réduire le champ théorique des possibles n’est pas problématique en soit, dans toute une vie, il n’aurait pas été possible de rencontrer une occurrence de chacun de ces paquets possibles, mais le fait de le réduire « autant » peut permettre à un attaquant possédant une main, de tenter de découvrir quel paquet a été généré.

 

Exemple d’exploitation

Le joueur possède dans sa main une portion du paquet (plus ou moins importante suivant le nombre de joueurs) qui sont les cartes qui lui ont été distribuées. Il sait où se trouvaient ses cartes dans le paquet, suivant la place où il se trouve sur la table.
Exemple: s’il y a 4 joueurs, le premier joueur sait que les 8 cartes qu’il a dans son jeu correspondent aux positions 1, 5, 9, 13, 17, 21, etc. dans le paquet initial (si les cartes sont distribuées une à une).
Il peut donc exclure tous les paquets, n’ayant pas ces cartes-là à ces positions précises, de l’ensemble des paquets générables.

Or sur l’ensemble des paquets possibles, il reste encore 24 cartes que le joueur ne connait pas (32 cartes au total moins ses 8 à lui qu’il connait), soit 24! combinaisons possibles (620 448 401 733 239 439 360 000 paquets). Donc si le joueur essaye de deviner quel paquet est utilisé dans le jeu actuel en se basant sur les cartes qu’il connait déjà (sa propre main), il doit en choisir un parmi les 24! possibles (infaisable).
Mais nous avons vu que seulement une infime partie des paquets possibles est générable, donc cela signifie que sur les 24! paquets possibles, le GNPA n’a pu en produire qu’une fraction, les autres peuvent donc être ignorés.

articlejeuxenligne5

La figure ci-dessus illustre la problématique : il s’agit d’identifier les points rouges et les points bleus qui se confondent. C’est-à-dire: parmi l’immensité des paquets possibles trouver lesquels sont à la fois générables par le GNPA ET compatible avec la main du joueur.

 

Calculons combien il reste alors de paquets « conciliables » avec la main du joueur, c’est-à-dire, ayant les mêmes cartes que le joueur aux mêmes positions. Sachant que les paquets générables représentent 1.632255400412188 x10⁻²⁴ % des paquets possibles :

>>> Factorielle(24)* 1.632255400412188e-26
0.010127302544061908

Ce chiffre peut également être trouvé en calculant la part de l’ensemble des permutations de 8 cartes sur 32 par rapport à l’étendue des paquets générables :

>>> power(2,32)/(Factorielle(32)/Factorielle(32-8))
0.010127302544061906

Il reste donc moins d’un seul paquet conciliable avec la main du joueur.

Statistiquement parlant, cela signifie que la très grande majorité des mains n’apparaitront jamais (99%), et pour les 1% qui apparaitront (dont la main du joueur fait, de facto, partie), dans environ 98% des cas, il n’y aura qu’un seul paquet conciliable.

Il en résulte que si le joueur a déjà généré une liste des 4 milliards de paquets générables, dès qu’il connait 8 cartes du jeu et leurs positions initiales dans le paquet, il connait le jeu en entier et donc les mains de ses adversaires.

Le tableau ci-dessous explicite les choix restants au joueur en fonction du nombre de carte qu’il a en sa possession.

articlejeuxenligne6

On peut constater que passé 7 cartes, la probabilité est très forte qu’il ne reste qu’un seul et unique paquet conciliable.

 

Mais que fait-on alors ?

Ce problème touche les GNPA qui sont systématiquement réinitialisés avant le battage des cartes. Dès lors que l’état du GNPA n’est plus forcément une des 4 294 967 296 valeurs possibles de la graine, le champ des paquets générables s’accroit et le problème s’atténue.

En effet les GNPA peuvent générer un grand cycle de nombres. Pour l’algorithme Mersenne Twister par exemple, il existe 2¹⁹⁹³⁷⁻¹ éléments générables (soit un nombre à plus de 6000 chiffres). Si le GNPA n’est pas réinitialisé avant le battage, il y a donc autant de paquets générables que de paquets possibles.

Attention cependant, réinitialiser périodiquement le GNPA demeure une bonne pratique. En effet, il est primordial que la graine qui a été utilisée pour l’initialisation du GNPA reste confidentielle, si elle est divulguée, il est alors possible de reproduire l’état interne du GNPA et de connaitre les futurs nombres qui seront produits.
Il existe également des attaques sur certains algorithmes (dont Mersenne Twister) qui peuvent permettre de retrouver l’état actuel du générateur dès lors que l’on a connaissance d’assez de nombres produits. On peut ensuite connaitre les futurs nombres qui seront générés.
Il est donc nécessaire de réinitialiser périodiquement le GNPA avec une nouvelle graine afin de rendre caduc les éventuelles attaques en cours.

La meilleure solution consiste donc à réinitialiser le GNPA régulièrement mais non pas systématiquement avant d’utiliser l’algorithme de battage. La graine utilisée doit être générée aléatoirement et ne pas dépendre d’éléments prédictibles ou devinables (horloge interne du serveur) comme c’est souvent le cas avec les fonctions basiques de génération de nombres aléatoires.

Une autre mesure à prendre consiste à utiliser une graine d’une taille plus importante que 32 bits. Des graines de 64 ou 128 bits compliquent exponentiellement la tâche d’un attaquant. Par exemple avec une graine de 64 bits, le joueur devrait connaitre au moins 14 cartes du paquet (et leur position dans celui-ci) pour qu’il ne reste statistiquement qu’un seul paquet conciliable.
De plus, si l’attaquant veut chercher ce paquet dans la liste des paquets générables, il lui aura fallu engendrer cette liste préalablement, or elle comportera non plus 4 294 967 296 paquets mais 18 446 744 073 709 551 616. La recherche dans cet espace sera donc considérablement plus lente (et peut excéder la durée d’une partie, d’où une perte d’intérêt pour l’attaquant).

Avec une graine de 128 bits, le joueur n’a tout simplement statistiquement plus aucune chance. En effet le nombre de paquets générables dépasse le nombre de paquets possible. Cette phrase peut paraitre incohérente mais elle se traduit simplement par le fait que tous les paquets possibles sont générables et qu’il existe plusieurs façons de produire un même paquet.

Notons également que cette attaque n’est possible que lorsque l’attaquant peut estimer la position initiale des cartes de sa main dans le paquet original. Or il se peut, suivant l’application du jeu, que le joueur se voit donné toutes ses cartes d’un coup, et triées par couleur, de sorte qu’il ne peut pas savoir dans quel ordre elles lui ont été distribuées (et donc leur position initiale dans le paquet).

 

L’accompagnement ITrust

ITrust mène des audits complets de sécurité et de robustesse sur les algorithmes et les implémentations de jeu en ligne. Vous permettant ainsi de détecter et de corriger les erreurs décrites ci-dessus et bien d’autres.
Que ce soit en vue d’obtenir l’accréditation de l’ARJEL (https://www.itrust.fr/certification-arjel/) ou bien de rassurer vos utilisateurs et vos investisseurs, ITrust peut vous apporter l’expertise technique et l’accompagnement adéquat tout au long de vos démarches.

Ainsi la présence du sceau ITrust Security Compliance, sur un site de jeux en ligne, vous assure qu’aucun joueur ne peut tirer avantage d’un biais statistique ou d’une faiblesse du générateur de nombres pseudo-aléatoires.

 

21 Juillet 2014 – Rédigé par David Soria – Expert Sécurité ITrust