Alban’s blog

Tetris est un «jeu vidéo de puzzle alliant simplicité, intelligence et adresse» d’après Wikipédia. GTetrinet permet d’y jouer à plusieurs. On peut gagner des bonus et des malus en faisant des lignes, puis envoyer les malus aux adversaires.

Mais GTetrinet est aussi un jeu de hasard. Le jeu choisit aléatoirement les pièces et les bonus-malus. Et le hasard se manipule, surtout sur un jeu avec une architecture client-serveur où les lancés de dés se font sur le client. Certains n’hésitent pas à écrire un patch pour pouvoir choisir eux-mêmes leurs bonus-malus au lieu de faire confiance au destin (j’ai hésité à mettre le lien vers le patch en question, mais finalement je ne le mets pas!).

Pour se protéger contre cela, on pourrait choisir aléatoirement les pièces et les bonus-malus sur le serveur. Car à priori, on fait plus confiance au serveur qu’aux clients, non? Dans le cas de Gtetrinet, cela impose de changer le protocole client-serveur, et donc de briser la compatibilité avec les autres clients existants sous Windows.

Et si on n’a pas confiance au serveur non plus, on fait quoi? Y a-t-il une solution si les deux clients communiquent directement entre eux sans passer par un tiers de confiance? C’est le même problème que jouer à pile ou face par téléphone. Il existe des solutions en utilisant un peu de cryptographie. Bruce Schneier reprend dans Cryptographie Appliquée (ISBN-10: 2841800369) une petite histoire de Uses of Randomness in Algorithms and Protocols de Joe Killian (ISBN-10: 0262111535):

Alice: Premièrement, tu penses à un bit aléatoire, ensuite je pense à un bit aléatoire. Ensuite, on prend le ou exclusif des deux bits.

Bernard: Mais que se passe-t-il si l’un de nous ne choisit pas aléatoirement?

Alice: Peu importe. Aussi longtemps que l’un des deux bits est vraiment aléatoire, le ou exclusif des deux bits doit être aléatoire.

Bernard: Ok, je parie sur 1. Mon bit aléatoire est 1. Et le tien?

Alice: Mon bit aléatoire est aussi 1. Le ou exclusif fait donc 0. Tu as perdu.

Ce protocole ne marche pas car Alice peut changer son bit si le choix de Bernard ne lui convient pas. Il faut modifier légèrement ce protocole pour mettre en gage un bit aléatoire en utilisant une fonction de hachage.

Il y a 9 bonus-malus différents dans GTetrinet. Pour choisir son prochain bonus-malus, Alice va effectuer les opérations suivantes:

1. Alice choisit deux nombres aléatoires quelconques R1 et R2.
2. Alice choisit son bloc B1 entre 0 et 8 aléatoirement.
3. Alice envoie HASH(R1, R2, B1) et R1 à Bernard
4. Bernard envoie un numéro de bloc B2 entre 0 et 8 aléatoirement.
5. Alice envoie en clair R1, R2, B1 à Bernard
6. Les deux joueurs calculent le bloc B obtenu par Alice: B = B1 + B2 modulo 9.

J’ai implémenté ce protocole en Ruby avec D-Bus: random_client.rb (pour Alice) et random_server.rb (pour Bernard). Les deux programmes doivent s’exécuter sur le même ordinateur sur la même session D-Bus pour communiquer, mais avec les tubes D-Bus de Telepathy, ça devrait pouvoir s’arranger.