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.
Answer
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:
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...
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 ;-)
No comments:
Post a Comment