7
\$\begingroup\$

Though it should be a pretty basic problem, I did not find a solution for it: How to play dice over a network without a trusted third party?

The M players shall roll N dice, one player after another. No player may "cheat", i.e. change the outcome to his advantage, or "look into the future" before the next roll.

Is that possible?


I guess the solution would be something like public key crypto, where each player turns in an encrypted message. After all messages were collected you exchange the keys to decode the messages. Then the sha1(joined string of all decrypted messages) mod 6 + 1 is used to determine the die.

The major problem I have: since the message [c/s]hould be anything, I don't know how to prevent tampering with the private keys. Esp. the last player to turn in his key could easily cheat (I guess).

The game should even stay fair, if all players "conspire" against one player.

\$\endgroup\$
  • \$\begingroup\$ Can't trust the client. Even though you may have a very nice strategy for sending the results securely, it doesn't mean they weren't modified before they were sent. \$\endgroup\$ – MichaelHouse Nov 6 '13 at 7:08
  • \$\begingroup\$ @Byte56, I don't trust the client. I want the algorithm to be "temper prove". But I don't know if that is possible at all. \$\endgroup\$ – kay Nov 6 '13 at 7:11
  • 2
    \$\begingroup\$ I feel like this might be a better question for a cryptology forum or research into zero knowledge protocols. I don't think this kind of problem is frequently dealt with by game developers; we just always have a trusted server. Also... "tamper proof" :) \$\endgroup\$ – Sean Middleditch Nov 6 '13 at 7:58
7
\$\begingroup\$

Combining Randomness

You need an algorithm that allows each player to contribute to the final random number in such a way that he can change the final outcome to every possible value, whatever the others have contributed to the random number. This way, even all other players may try to work together against a single player, but can not decide the outcome (or in any way influence it).

How to do that? Imagine we want simulate a dice of 6 sides. If we play alone, we use a random number generator that outputs a large random number r. Then we get the final value by calculating result = (r mod 6)+1. The same works for multiple players, that role their dice individually. Imagine you have a box (or urn). Every player runs its random number generator (concealed) and writes that number (r1, r2, r3, ... rn) on a sheet of paper and puts it into the box. Now the players take all the numbers out of the box and calculate their sum to generate the groups random number r = r1+r2+r3+r4+...+rn. This one is used to calculate the result using result = (r mod 6)+1. If the other players would cheat (by working together), a single player could still change the result to any value.

Why is that the case? Imagine we had 3 players. Player 1 and Player 2 try to cheats and work together against Player 3. Player 1 and Player 2 only contribute r1 and r2 to the sum r. So what they can decide is what the result of r1+r2. The value ((r1+r2+r3) mod 6) + 1 is the same as (((r1 mod 6) + (r2 mod 6) + (r3 mod 6)) mod 6) + 1. As Players 1 and 2 may decide r1 and r2 they can decide the part (r1 mod 6) + (r2 mod 6) let us call this one c. The final result is then ((c + (r3 mod 6)) mod 6) + 1.

So whatever players 1 and 2 are trying r3 can change the result to any value from 1 to 6 without changing the probabilities. If you do not believe it, try c = 0 and r3 = 0 .. 5, which gives you the result 1 to 6. Try c = 1 and r3 = 0 .. 5, it will give you the results 2,3,4,5,6,1. Try c = 2, r3 = 0 .. 5. You'll get: 3,4,5,6,1,2.

To depict this phenomena imagine a Wheel of Fortune of a game show. It has 6 zones (0, 1, 2, 3, 4, 5) that lock in "digitally". You can push a button to turn it one zone forward (from 0 to 1, from 1 to 2, from 2 to 3, ... from 5 to 0 and so on). The Game starts with the wheel at position "0" and each player is writing down (concealed) any positive number. Now they must put away the pencils, so anyone can change the number and each player must show all others his number. Now each player pushes the button as many times as he has written down on his sheet of paper. And we get our final random number (0..5). This game would take very long and would be very annoying, if we would not remember to following: each 6 times the button is pressed the wheel is again at the same position. So each player may just calculate his number "mod 6" and push the button and turn the wheel forward that many times. The result is obviously the same. Or as a formula: (r1+r2+r3) mod 6 = ((r1 mod 6) + (r2 mod 6) + (r3 mod 6)) mod 6.

Exchanging Values

Now over a network we don't have a "box" to put in the random values of the player (trusted third party). We also can't check the players have put their pencils away. So we need another algorithm for that.

Kolrabi already explained it. You can let calculate a hash value (e.g. SHA1 hash) of the random value by each player first. Then they all have to release their hash value to the others. If you do it correctly, nobody can just "quickly" calculate the random number from that. So nobody can just take the hash of the others to change the final result in a deterministic way (Imagine: he is the last player and he just spins the wheel forward by his number of times. But he doesn't know what the position of the wheel is when he starts to turn it - so he can not decide the outcome).

If everyone has got the hashes of all others, everyone checks that he got the same hashes from all the others. Don't know if this is really needed. But, afterwards everyone has the the same hashes.

Now, exchange the random numbers. Everyone checks, that the numbers match to the hash value (by calculating the hash values of all numbers and checking that they are equal to the hashes that the player had exchanged before).

If there was no problem above (all had exchanged the hashes correctly, hashes match the random values) you can calculate the result by summing up the random values and calculating "mod x" + 1, which gives you the result of a dice with x sides. This result should be (I'm not a cryptograph) random evenly distributed as long as at least one player used a random number generator that generates evenly distributed values.

What means "If you do it correctly"?

You must prevent that any player may calculate the random values from the hashes. There exist at least two ways how a player could do that:

  1. He just tries through all values 0, 1, 2, 3... and calculates the hashes. If the hash matches, he has found the value for the hash. To prevent this approach to have success, your random number range should be very large (not just 0 to 5 or 0 to 65535, which a player could just quickly check out within short time). A 32 bit number should be fine. This is why the players should exchange the raw random number generator output and not the value "mod 6". If your random number generator does not give you that huge values generate multiple random numbers and combine them to a single big number (use bit-shift operations to combine them; ask, if you need to do that and don't know how to do it... its important to do this right!). But, in most cases the random value range of the generator is big enough...

  2. The second method would be to use a lookup table. If you know that the numbers are within a special range you could calculate all the hashes in advance and store them into a database, sorted alphabetically. Later you could just look up the hash to get the value. To prevent this, you can do two things: a) the number range (as above) must be very large so that it becomes impossible to store such a database. b) exchange a random string (contributed in parts by all players, doesn't need to be concealed) in each new round. That random string is to be appended to all the values when calculating the hashes. So you can't build a database before you know this random string - or you had to build a database for any such random string, which would need even more computational power and storage.

Another possibility to cheat would be to "change" the random number to another number that matches has the same hash value. The approach would be the same as above. While in most cases it is very hard to find another number that has the same hash value, this could be pre-calculated, if you just use the hash of the number. Therefore, you should exchange that random prefix (or suffix) string that has to be added when calculating the hash value. I'm not 100%ly sure, but I remember there was some technique for the MD5 hashing algorithm to quickly calculate other matching values for the same hash, if you are given a value that results in that hash. So better don't use MD5. I don't know about this kind of attack for SHA1, but there might be one. At least make sure the hashing algorithm has no known weakness of that kind -or- the calculation at least takes very long.

If you have done the above right, you should further improve the security of the method by limiting the time for the exchange of the hashes and values. Only if the exchange is executed within some time limit, it should be valid. This ensures, that neither party has enough time to apply one of the above 'hacks'. If it takes too long the procedure must be repeated.

What still needs to be solved

One of the parties may still be able to influence the outcome by applying the above techniques. In most cases (e.g. 99,99999% of the cases depending on parameters) the time will be too short. But, given enough chances one party might be lucky to break the hashing. For example, a Player could just randomly try out numbers to find another "random" value with the same hash value he had send to the other players (last approach) for as long as possible (to not let the timeout catch him). Especially, if the player lets all the others send him their random values first, he would know what kind of values would give him the biggest win. So he could just try these ones. The evil player then would either let everything time out and restart (to get another chance without loosing) or just lets the game go on and use the next dice round for another try. You could decide, that if a player doesn't deliver its hash or random value within the timeout would automatically loose. So this reduces the problem, but it still increases the chance of a player by some very very small amount.

This weakness is especially critical, if this very small amount of additional chance is enough to disturb... For example if one player could this way decide a complex outcome and wins a lot of money. For imagination, assume you apply this algorithm to a lottery game where one of the "players" is the Bank-Server. We ignore for the moment that if we have a lot of players the amount of data transfer would be not realistic (each person had to tell all other person, its hash and random value; which resulted in N*(N-1)/2 messages needed to be exchanged, which is over 1 Million for just N=2000 players and increases quadratically). Okay, back to the issue. If just one player would "break" his hash and is able to decide the outcome, he could illegally win some Million Dollars from the Jack Pot... Got it?

If you have such a critical application, you must calculate the chance, that at least one player cracks his hash code within the time. Then multiply this by the maximum possible win of all players, not under your control (e.g. the bank player is trustworthy). This would give you the maximum loss per round. In the lottery example, the lottery bank would loose this much money per round, if all players would try to cheat. The lottery chances therefore would need to be adapted in a way -or- the probability of a successful 'hack' must be further reduced.

To reduce the probability you can: a) reduce the timeout time, b) use a more complicated hashing function, c) use longer numbers, OR: d) distribute the outcome over multiple rounds.

Distributing the outcome over multiple rounds would work by only deciding -a part- of the "result" within one round and executing multiple rounds. For the lottery example, each number could have its own round. This way, a lucky cheater would only had the possibility to change one number each time he manages to break the hash. So he would have to have luck 6 times in a row (if the lottery is selecting 6 numbers) to illegally win the jackpot. WARNING: Each round should only influence one special part of the outcome (e.g. one of the numbers in the lottery). Do not just exchange multiple random values / hashes and sum them up, as before. If you do this a player having luck in the last round would be able to change the whole outcome (!). But, for example, you could do one round for each "bit" of a random number.

Another problem to take care of is, that one player may "disturb" the game by letting the whole thing time out over and over again. This might be a problem, if players are anonymous and you cannot just bann people who do not play fair.

OK, I hope this covers all problems and attacks ...

Good luck ;-)

\$\endgroup\$
  • \$\begingroup\$ Thank you very much for you well elaborated answer! Hehe, no, I won't create a million dollars lottery. :-) I just wanted to program a little game of Backgammon and wasn't sure how to do the dicing. Thinking further I came up with this question about M players and N dice. My code now looks as follows: dice.py. Esp. the timing that you spoke of I still have to implement. Thank you again! :-) \$\endgroup\$ – kay Nov 6 '13 at 17:35
  • 1
    \$\begingroup\$ You are welcome. I did it a bit more complete, as there might be other people with a similar problem who will actually find this article and should know about the critical sides of it. But, especially classic two player games like backgammon (or poker) could be played "for money" and would quickly become a target for hackers... How ever, good to know that I was able to solve your problems! \$\endgroup\$ – SDwarfs Nov 7 '13 at 12:43
  • 1
    \$\begingroup\$ I'd recommend something like bcrypt over traditional hashing algorithms, as it is built to be exactly as slow as you need it to be. If you find out it's not slow enough (people with newer computers break it or something), you can adjust it in the next release. \$\endgroup\$ – Nerdmaster Nov 7 '13 at 20:05
  • 1
    \$\begingroup\$ Also may be worth considering a "turn-based" message approach to minimize an individual cheater's options. If there are 5 players and they have to turn in their hashes and numbers in a certain order, they each are last only 20% of the time. Since cheating relies on being last, losing that ability at least slightly reduces the ability to attack the system. \$\endgroup\$ – Nerdmaster Nov 7 '13 at 20:07
  • 1
    \$\begingroup\$ One massively important point you forgot is the way you generate a random number. Many PRNGs seed with the time, which means that the timeframe of predicting random hashes is greatly reduced to 100000s of possibilities instead of 2^keyLength. On modern day hardware that'd be less than a second to process, and compromises any security you've put in place. \$\endgroup\$ – Aidiakapi Jan 11 '14 at 0:28
3
\$\begingroup\$

It should be possible. At least the "tamper detection" part of it.

You will need:

  1. A good cryptography strength random number generator, creating random numbers that are hard to predict or to guess.
  2. A good hashing algorithm, relatively slow to bruteforce, hard to reverse.

Then I propose the following algorithm.

  1. Have every client commit to a random number. Make it a sufficiently long one so it is hard for an attacker to try every possible value. Maybe the length of the output of your hash algorithm.
  2. Have every client broadcast to every other client a hash of that number.
  3. Repeat steps 1 and 2 for how many dice rolls you need.
  4. Have every client broadcast to every other client their random numbers.
  5. If a client "changed their mind" about their number, the hashes won't match their numbers.
  6. Use only "good" numbers that match their hashes for generating the outcome of the rolls.

That way no client knows the result of a roll before sending their numbers, cannot predict what numbers would change the outcome. They can invalidate their own numbers but it won't do them any good.

If at least one client is honest and the random number generator is good, it will be possible to arrive at a fair roll. If everyone is cheating however, it will not be. But in that case nobody wants to play a fair game anyway.

What this cannot avoid, though, is a client pretending the outcome of a roll is a different one than it really is. If they are refusing reality there isn't really much you can do.

\$\endgroup\$
  • \$\begingroup\$ Regarding "client pretending the outcome of a roll is a different..."; You can use signed / encrypted communication. Especially let the other players sign a message which hashes they received. This message can then be used to proof that everyone had send exactly the given randomness to the others and the calculated result outcome results from this deterministically. \$\endgroup\$ – SDwarfs Nov 7 '13 at 12:49
0
\$\begingroup\$

When a random number needs to be generated, have each player generate a random string.

Each player creates a cryptographic signature of their strings, and sends it to all other players. After all players acknowledged that they received the signatures, the strings themself are sent to all players.

All players now verify the signatures, concatenate these strings, and create a hash of it using a cryptographically secure hash function.

This hash is then used to generate the random number.

As long as at least one player contributes an unpredictable string to the total hash, the result is unpredictable. The only possible attack scenario would be when one of the players can predict what random string the others will produce. That's the reason for exchanging the signatures first: When the signatures are exchanged beforehand, a player can't wait for the others to send their strings and then generate a string which would result in a favorable result.

\$\endgroup\$
  • \$\begingroup\$ Your answer is correct (and much shorter than others). But, the principle is the same, as other answers given already. Cryptographic signatures are actually using hash functions, as suggested already by others. \$\endgroup\$ – SDwarfs Nov 8 '13 at 11:13
-1
\$\begingroup\$

maybe let 2 clients have his own random seed the other clients don't know, when you need a new random number all the clients generate a number then you add all those for a shared seed make a the final random number.

\$\endgroup\$
  • \$\begingroup\$ Two (or any numbers of) players could work together. \$\endgroup\$ – kay Nov 6 '13 at 8:13
  • \$\begingroup\$ @Kay this is the most basic awnser you could very easely scale it to as much players as you would like \$\endgroup\$ – harrie Nov 6 '13 at 13:52
  • \$\begingroup\$ All players could work against one player. Your idea simply won't work. \$\endgroup\$ – kay Nov 6 '13 at 23:27
  • \$\begingroup\$ disliked for trying to help really nice guys \$\endgroup\$ – harrie Nov 7 '13 at 7:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.