Multiplayer and RNG cheating

[Wintersmith]

As I understand it, it is currently possible to cheat in multiplayer by fixing the random number generation (RNG) in your favor. However, there exist cryptographic protocols to allow two people communicating over a network to securely generate random numbers; by following the protocol each person can be guaranteed that the other did not cheat to fix the result. The protocol does not require the assistance of any trusted third party, so it wouldn't impose any load on the official Wesnoth server, and it would work perfectly well in mulitplayer games which are not played using the official server.

(The above idea was originally posted here but I wanted to put it on the Dev. forum to ask some questions...)

Now, the questions. I have been looking through the Wesnoth source code to try to figure out how to implement this, but I am very confused. Could someone explain how multiplayer games work in Wesnoth? Is the game run entirely on one host computer, with the other players merely submitting their moves to the host? Or is it set up in some other fashion? Also, most of the source code seems to be rather sparsely commented; is there some documentation on how all the insides of the game work that I am unaware of?

[Wintersmith]

Here is how the protocol works; it doesn't really need much cryptography, just a good one-way hash function.

Suppose Alice attacks Bob's unit, and they need to generate a random number to determine the whether the attack hits. Here is how they can generate one random bit; this can easily be extended to generate as many random bits as they need.

(1) Alice chooses a random number X and computes Y=F(X), where F() is the one-way hash function.

(2) Alice sends Y to Bob.

(3) Bob guesses whether X is even or odd and sends his guess to Alice.

(4) If Bob's guess is correct, the random bit shall be a 1; if it was incorrect, the random bit shall be a 0.

(5) Alice tells Bob the result of his guess, and sends him the number X.

(6) Bob confirms that Y = F(X).

Because F() is a one-way hash function it should be impossible for Alice to find two numbers X and X' such that F(X)=F(X'). Consequentially, neither party can cheat.

There are actually a couple of subtleties in this, but that is the basic idea. The protocol I gave was straight from section 4.10 of Schneier's Applied Cryptography.

Essentially, to implement this in Wesnoth you just need the two players to conduct the brief chat outlined above to securely generate a random number.

[Dave]

Hi there,

I've been meaning to work on a way to make random numbers secure for a while, but haven't had time/compulsion/etc so far.

Thank you for raising the issue and a possible solution.

I think that we could actually simplify the process to generate a whole number in one go instead of generating only one bit at a time. Suppose we want a number in the range 0-99:

(1) machine A generates a random number X and sends the hash of X, F(X) to machine B.
(2) machine B replies with a number Y that it would like to have added to X
(3) machine A replies with the final number X+Y, and machine B can confirm the result of F(X). We take X+Y mod 100 to get our result.

This would take a little to implement. It's certainly a very good idea though.

David[/list]

[Wintersmith]

Glad you like it. I should probably go ahead and point out the subtleties.

First and foremost are the problems associated with using pseudo-random number generators. The sequences of PRNGs look statistically random, but they are, of course, completely deterministic. For a given seed value, a PRNG will always generate the same sequence. If Alice can determine, a priori, what Bob's guess will be (or in your version, what number Y he will generate) then she can subvert the protocol. Likewise, Bob may not be able to invert F(X) to determine the X Alice chose, but if Alice used a PRNG to generate X then Bob may have another method of finding X and breaking the protocol.

Secondly, a hash function, F, may produce certain statistical relationships between X and F(X). For example, if, having only seen F(X), Bob knew that there was say, an 80% chance that the most significant bit of X was a 1, then he could choose a number Y which would give him an unfair advantage. I'll try to read up on various hash functions to figure out if this problem is really a problem and what could be done about it if it is.

As for the PRNG issues, I'm not sure if there is a good way to deal with those besides ditching the PRNG and finding a source of real entropy.

[Elvish_Pillager]

Well, I know a source of real entropy you could use: mouse motion. The simplest way to do it is, whenever the mouse moves, to add the distance moved to your randomseed.

But I'm not sure how that would help you, because it can't be confirmed with the other machine.

[jonadab]

Well, I know a source of real entropy you could use: mouse motion. The simplest way to do it is, whenever the mouse moves, to add the distance moved to your randomseed.

Would that have a perf impact on the responsiveness of the mouse? (My guess is not a user-noticeable one, but I wanted to raise the issue.)

But I'm not sure how that would help you, because it can't be confirmed with the other machine.

It is neither necessary nor desirable for Bob to be able to confirm or verify Alice's entropy per se when she transmits F(X). The one-way hash function, if it is cryptographically sound, allows Bob to verify ex post facto that the number Alice originally chose for X is the same as the number she now claims (after Bob specifies Y) that it was. (EDIT: So that allows Bob to detect whether Alice is cheating, _without_ knowing how she generates her entropy.)

A perhaps more interesting question is what Bob's copy of Wesnoth should do if it thinks Alice's copy of Wesnoth is rigged or cheating. Discard the result and start a new random number generation sequence? Abort the game? Warn Bob with a dialog box that Alice may be cheating?

Also, you speak of rigging attack/defense, but what about more subtle "slight advantage" cheating, like rigging trait selection so that e.g. mages are always resilient?

[Wintersmith]

Firstly, I envision the cryptographic protocol being used whenever anyone needs a random number for any purpose, including both combat and assigning traits for recruited units (and I think that's all -- are there any other points in the game where random numbers are needed?).

Secondly, you raise an excellent point, Jonadab: regarding what to do if cheating is suspected, we can't just do nothing and try again to generate a random number. Watch what happens if we do.

Alice and Bob start the protocol to generate a random number. After Bob sends Alice his number Y to be added to X, Alice knows the result of the random number generation; Bob doesn't learn the result until later when Alice sends him X.

Now suppose that Alice finds that the result is not in her favor. Instead of sending Bob X, she sends him some other number X'. Bob's computer will, of course, discover that F(X) != F(X'), but suppose it (foolishly) decides to give Alice the benefit of the doubt and redo the protocol from the beginning.

Alice has succeeded in getting an undesirable random number tossed out. In fact, she can keep tossing out bad results in this manner until she gets a random number she likes!! Note that because Bob learns the result after Alice does it is not possible for him to cheat in a similar fashion.

Here is my recommended solution: If Alice does not produce a valid X then Bob's computer should pop up a notification box on screen to tell him about this. Then we should switch the roles of Alice and Bob in the protocol; from now on it will be Bob who first learns the result of the random number generation, and Alice is precluded from trying this again. Of course Bob might now try the same trick that Alice pulled.

However, if at least one of the players is honest we have limited the damage the dishonest player can do. The dishonest player only manages to toss out one undesirable random number and get a re-roll, and the honest player is told about the suspicious behavior.

Lastly, switching roles in response to suspected cheating causes one new problem which we need to be aware of. If Alice (who, for the moment, is assumed to be honest) plays the part in the protocol which learns the result first, then Bob might claim that F(X) != F(X) in order to force a role swap and put himself in a position to try to cheat. Of course, Alice's computer will know that Bob is lying; we just need to make sure that her computer tells her about this.

[Wintersmith]

One note: the protocol I have outlined is designed to let either Alice or Bob know if the other is trying to cheat. It doesn't enable either of them to prove to a third party (say, hypothetically, the Wesnoth Official Ranking Service) that their opponent was cheating. If we want to run a ranking service then we will basically need Alice and Bob use a cryptographic digital signature algorithm to sign all of their messages to each other. This allows a third party to verify exactly what messages Alice and Bob's computers sent to each other in the course of the game; it allows a provable resolution to any arguments over who made what moves, who tried to subvert the RNG protocol, etc.

[Boucman]

AFAIK all OS use mouse/key movement to get entropy, + other stuff like disc spindown time etc...

no need to measure it ourself, just uset the OS RNG will be fine in that respect...

[Leonhard]

This is a very interesting thread to read! I'm not skilled in cryptography or in other any related question, but I try to understand a bit. I have to questions that will make me a fool for some minutes but let's go :
* How is it possible to find a one way function that the other cannot inverse? If it is a one way function, it is one way in the two directions, so imagine I want to cheat : if it takes time, I can prepare some big datas of what is the function's inverse before playing, so that my guess is right all the time. One way to solve this would be to change the function for each play, or smth like that? (hope I'm clear, but that's not sure.. )
*Second point : I don't know why there is a problem with decision if there is cheating. If you get notification, then it is clear that the other player has cheated. It is your matter how you react to that, whether you stop the play because it upsets you, or you wait one more turn, or you don't care... What do you think?

[scott]

This is a very interesting thread to read! I'm not skilled in cryptography or in other any related question, but I try to understand a bit. I have to questions that will make me a fool for some minutes but let's go :
* How is it possible to find a one way function that the other cannot inverse? If it is a one way function, it is one way in the two directions, so imagine I want to cheat : if it takes time, I can prepare some big datas of what is the function's inverse before playing, so that my guess is right all the time. One way to solve this would be to change the function for each play, or smth like that? (hope I'm clear, but that's not sure.. )
*Second point : I don't know why there is a problem with decision if there is cheating. If you get notification, then it is clear that the other player has cheated. It is your matter how you react to that, whether you stop the play because it upsets you, or you wait one more turn, or you don't care... What do you think?

First point: cryptography, I have heard, relies on the difficulty of factoring large polynomials. The polynomial size relates to the number of bits of encryption (128 bit, f.ex.). Try factoring a quintic (without Mathematica), then you'll see how a 64th order polynomial could be tough.

Second point: this is about cheating that the game cannot detect

[Darth Fool]

While this is an interesting discussion, it should be pointed out that what is needed is not only a system that verifies that the number is random between two players, but that it verifies it for all players(up to 9 currently). While an extension to the algorithem that would do this is obvious, it is not particularly pretty. You could, for example, pass the number around the loop of players until it gets back. This, however, could get ugly. An alternative is to have one trusted player, most likely the host, who does the RNG exchange with each player as necessary. Of course, then the host could cheat. One could also imagine having an RNG-server that would obviate the need for any cryptographic protocol between players, however, the RNG server might get loaded down, and anyways, we probably want to make sure that people can have games without a server where they still trust the RNG. Still, if the aim of having a trusted RNG is to head towards having a ranking system, you likely will need to have a server running things anyways, or eliminate both FOW and invisibility.

Now, one crypto tool that would be useful in both cases would be the ability to send an encrypted WML message. In particular I am thinking of what it would take to be able to have uniquely identified users. Also, having the ability to encrypt WML with standard public/private key algorithem would allow players to sign their RNG exchange.

[Dave]

While this is an interesting discussion, it should be pointed out that what is needed is not only a system that verifies that the number is random between two players, but that it verifies it for all players(up to 9 currently).

For the most important RNGs -- those generated during combat -- I think you could simply make the generation take place between the machine with the attacking player, and the machine with the defending player.

For traits you could probably do something simple like choose any machine which has a player that is an enemy to you.

David

[Invisible Philosopher]

Here is a possibility:

Make each player generate a random number with a given number of bits. Exchange these and bit-xor them all together to get the actual random number used. As long as a cheater can't deduce the random seed (and algorithm) of every other player (and as long as at least one is actually generating a [pseudo-]random number!), the result will be random and unpredictable to everyone.

IMO this should always involve all players so that even if two cheaters are enemies of each other, they can't make the game non-random, which would be against some honest participants' wishes. Of course a cheater can always make the game go out-of-sync....

[Elvish_Pillager]

Here is a possibility:

Make each player generate a random number with a given number of bits. Exchange these and bit-xor them all together to get the actual random number used. As long as a cheater can't deduce the random seed (and algorithm) of every other player (and as long as at least one is actually generating a [pseudo-]random number!), the result will be random and unpredictable to everyone.

But what if one player waits to recieve all the other numbers, and then decides his own number based on that knowledge? You would need a trusted server to collect all the numbers before releasing them to everyone.