P2P random numbers

[Viliam]

I do not know if this would be useful for Wesnoth, but there is an algorithm for generating random numbers between two players, which:
a) prevents cheating;
b) does not require help of third party.


If the two players could communicate simultaneously -- that is "A speaks to B at the same time as B speaks to A, so no one can change their message according to what the other one has said", it is possible to generate random numbers using the following strategy:

A chooses a random number X in given range
B chooses a random number Y in given range
both exchange their numbers
the random number is R = (X + Y) mod range

It is not possible to cheat, because it is sufficient for player A to choose number X randomly, and then R is also random. It does not matter if B tries to use any strategy for using non-random Y. (The situation is symmetrical for the other player.)


Now the only problem is that simultaneous communication is impossible. But we can achieve a similar effect by using a one-way hash function F. The improved algorithm is:

A chooses a random number X in given range
A sends F(X) to B
B chooses a random number Y in given range
B sends Y to A
A sends X to B
B verifies that the previously received F(X) was correct
the random number is R = (X + Y) mod range

In this situation A cannot cheat if B chooses Y randomly. But also B cannot cheat, because with a good hash function it is impossible to calculate X from F(X), therefore X remains unknown to B.


So this could make it possible to communicate random numbers without possibility to cheat, but it would not be necessary to generate them at server.

[Glass Pearl Player]

For anyone interested, the search term is "Commitment scheme".

I'll slightly change notation and make the protocol more symmetric:

Alice chooses a random number X in given range
Alice computes f=F(X) and sends f to Bob
Bob chooses a random number Y in given range
Bob computes g=F(Y) and sends g to Alice
Alice sends X to Bob
Bob sends Y to Alice
Alice verifies that g=F(Y)
Bob verifies that f=F(X)
the random number is R = (X + Y) mod range

First, I'd like to ask for two clarifications:
a) Assume Bob finds that f does not equal F(X). What should he do?
b) Assume Alice plays fair, and just has sent X to Bob. Instead of sending Y, however, Bob replies with a harsh protest note claiming that f != F(X). What should she do?
(Finding that there is a cheater is easy. Identifying the cheater requires involvement of a third party, exactly what we wanted to avoid.)

Second, using a hash function (where the output has fewer bits than the input) might leave us open to attack:
Assume Alice wants to cheat, and that a particular F has been agreed upon long in advance. She may then search for collisions, that is, pairs X1, X2 with F(X1)=F(X2)=:f. Once she knows which Y Bob committed, she then chooses to send either X1 or X2, depending on which gives her an advantage.
We have a strict upper limit on how computationally expensive F can be (it must not slow down gameplay too much), but to prevent such a birthday attack, the output must have "many" bits, we might be a bit in a bind here.
We also can't make the range too small, or else whoever commits last can simply run a brute force attack on F.

In short: I think that would be an interesting coding project that would deter most less skilled cheaters, but whether the devs consider it important enough, I do doubt.

[Zarel]

A chooses a random number X in given range
A sends F(X) to B
B chooses a random number Y in given range
B sends Y to A
A sends X to B
B verifies that the previously received F(X) was correct
the random number is R = (X + Y) mod range

Note that "given range" in Villiam's cryptosystem above should be in the trillions range, or else the hash function is useless.

First, I'd like to ask for two clarifications:
a) Assume Bob finds that f does not equal F(X). What should he do?
b) Assume Alice plays fair, and just has sent X to Bob. Instead of sending Y, however, Bob replies with a harsh protest note claiming that f != F(X). What should she do?
(Finding that there is a cheater is easy. Identifying the cheater requires involvement of a third party, exactly what we wanted to avoid.)

a) Bob should accuse Alice of cheating.
b) Alice should accuse Bob of cheating.

Identifying the cheater is trivial.

Second, using a hash function (where the output has fewer bits than the input) might leave us open to attack:
Assume Alice wants to cheat, and that a particular F has been agreed upon long in advance. She may then search for collisions, that is, pairs X1, X2 with F(X1)=F(X2)=:f. Once she knows which Y Bob committed, she then chooses to send either X1 or X2, depending on which gives her an advantage.
We have a strict upper limit on how computationally expensive F can be (it must not slow down gameplay too much), but to prevent such a birthday attack, the output must have "many" bits, we might be a bit in a bind here.
We also can't make the range too small, or else whoever commits last can simply run a brute force attack on F.

This is simple to resolve.

First, let's call our hash function H, since really, who uses F for hash functions?

B chooses a random number Z in given range
B sends Z to A
A chooses a random number X in given range, and computes V=H(X,Z)
A sends V to B
B chooses a random number Y in given range
B sends Y to A
A sends X to B
B verifies that V=H(X,Z)
the random number is R = (X + Y) mod range

voila, now you can't pregenerate collisions. I mean, it's still not perfect. For "perfect", easy enough just to stick to something standard, like Diffie–Hellman key exchange. A summary of Diffie-Hellman:

Let g be a generator mod p. g and p are public. We're cryptographers, not programmers, so ^ means exponentiation, not bitwise xor.

B chooses a random number a, and calculates Ka = g^a
B sends Ka to A
A calculates K = Ka^b
A chooses a random number b, and calculates Kb = g^b
A sends Kb to B
B calculates K = Kb^a

The random number is K mod p.

[Viliam]

a) Assume Bob finds that f does not equal F(X). What should he do?

Throw a synchronization error. The same things that happens when any network communication fails.

b) Assume Alice plays fair, and just has sent X to Bob. Instead of sending Y, however, Bob replies with a harsh protest note claiming that f != F(X). What should she do?

Throw a synchronization error.

We are not trying to determine "who is guilty". It is enough to say whether this game was OK or not. (Maybe the other player uses a modified system. Maybe it a bug. Maybe something happened with network connection.) If there is not error, then you know you had a fair game. That's all.

Note that "given range" in Villiam's cryptosystem above should be in the trillions range, or else the hash function is useless.

Oh, yes...

Well, this shows how one should pay attention when designing secure systems. Just reading about some algorithm in book and then applying it blindly, is very dangerous.

So the numbers communicated should be big... and the "... mod range" should only be applied to the result. There is still a possibility of preparing F(X1)=F(X2) in advance...


Maybe the first question is "would a similar system (if designed without flaws) be useful?" If the answer is positive, then we can discuss how to make a secure system.

[Crab]

the question is: for Wesnoth, what is the problem with current approach of generating random numbers on server ?
Generating on server is secure and is faster than generating them using a P2P protocol (as network latency >> generation time), as Wesnoth's MP is server based (so, for P2P generation, the server would need to proxy all the exchanges)

[Zarel]

Generating on server is secure and is faster than generating them using a P2P protocol (as network latency >> generation time)

Either "faster" is a typo for "slower", or ">>" is a typo for "<<". Given the rest of your post, I assume the latter.

It's not so much that network latency < generation time (which I'm not even sure is true), but that network latency < network latency * 6, since Wesnoth doesn't use peer-to-peer.

[Boucman]

Crab's post makes perfect sense.


Wesnoth is not p2p and won't be in the forseeable future. P2p requires some advanced firewall piercing code if we want to get it to work for everybody (and we want that)

and fyi network latency >>> generation time.

generation time on most OS (all I know of) is pseudo RNG based, so an OS call + a small calculation, the overhead of sending a packet (not even mentionning the actual network transmission time) is much bigger than that

my guess is that server generation will always be faster than p2p based, and p2p based RNG are good for p2p games that can't rely on a server, but if you have a server and the server can handle the load, it seems to me that server based RNG are better than p2p on all aspect

[Crab]

Either "faster" is a typo for "slower", or ">>" is a typo for "<<".

no, no typos. I meant that, with current client-server architecture, the time we will lose by introducing extra network latency for p2p style of generation is a lot more than the time that we will win by offloading calculations from server.

[mistersheik]

I proposed something similar here: http://www.wesnoth.org/forum/viewtopic.php?f=10&t=29792

Good system, but once you're already exchanging and verifying the hashed value, you don't need to build a random number using numbers from both computers.

[Zerovirus]

How would this work for more than one person? What if a third party is manipulating the numbers somehow (such as in a 2v2 battle, to help the allied team)?

Of course, I have absolutely no clue how any of this works, so ignore me at your leisure.