Secure Dice Rolling Protocol

[Yoni]

This isn't for something I'm working on, just an interesting hypothetical programming situation I thought of, which sounds likely to arise in real projects. Here it is:

I program a multi-player game, where the players connect to a game server over a network - the server is either a "dedicated" server, or one of the players.
The game consists of players occasionally throwing dice.
The question is: How do I secure the dice against cheaters?

The two most obvious approaches to programming network-dice are:
1. The player who has to throw the dice sends the number. This is obviously flawed, as a cheater might program his own client (or use a hacked client) to let him/her pick the result.
2. The server sends the number. This is flawed for the same reason (the cheater operates a server that works to his advantage, or to others' disadvantage).

An approach I was thinking of is:
Whenever one player needs to throw the dice, all players contribute to the result. Each player sends a random number, and then everyone's numbers are mixed (using some hash/checksum algorithm probably) and a dice result is gathered from that.

A problem with this approach: Who gathers the numbers? The server? Again, the server may not be trusted with the final result!

Any comments are welcome.

Note: In my post I talked about a client-server implementation, but if a peer-to-peer one works better, comment on that as well.

[iago]

It seems like random chance is hard in a game like that.

Me and the guy I work with discussed there, and we came up with 2 potential solutions (either p2p or client-server could probably do this):

1) Each player generates a random number (0..INT_MAX) and sends it to every other player, each number is added up and then mod6.  You can still change what you send, but it wouldn't usually make a difference.  The downside to this, I think, is that it's possible to wait for the other players to send you theirs, then abuse it.

2) At the start of play, each player generates a random number (0..INT_MAX).  Each player takes everybody else's and hashes it (so that every player will end up with the same number, generated from everybody's).  This is used to seed a random number generator (probably a custom one shipped with the game, just so we know for sure that everybody's is implemented the same).

[Adron]

Use a fully interconnected peer-to-peer topology.

Everyone generates a random number.

Everyone generates a hash of their random number.

Everyone sends their hashes to everyone else.

Upon receipt of everyone elses hash, everyone sends their random numbers to everyone.

Everyone verifies that the received random numbers match the hashes received before.

A new hash generated from all the random numbers is either used as the resulting random number, or as a seed for a random number generator that runs in parallell on all machines.

Whether you can use a random number generator that runs in parallell or have to redo the procedure for each random number depends upon whether players can make better decisions (cheat) if they know what the next random numbers will be.

If players can make better decisions knowing more about the random numbers that will follow, you will probably also want to include each players choice/move/whatever in the hash that is shared with every other player first, and then share your move with the others upon receipt of their move+number hashes.

This is design is intended to mimic the functionality of putting everyones secret move/number into a sealed envelope in an urn and only opening them all when everyone has submitted theirs.

[Banana fanna fo fanna]

This was discussed on another forum I used to frequent. Here's the solution that was obtained.

Player A wants to roll the dice. Player B is his opponent. When A rolls, he randomizes a list of possible outcomes (1 through 6), encrypts them with a secret key K, and sends the list to B (B doesn't know the key). B replies with a random index on that list. A replies with the decryption key. A and B now know the result, and neither can control which one is picked. Of course, sanity checks on the list will be performed by B after he decrypts the list (to make sure the list doesnt say 6 6 6 6 6 6 for example).

[iago]

This was discussed on another forum I used to frequent. Here's the solution that was obtained.

Player A wants to roll the dice. Player B is his opponent. When A rolls, he randomizes a list of possible outcomes (1 through 6), encrypts them with a secret key K, and sends the list to B (B doesn't know the key). B replies with a random index on that list. A replies with the decryption key. A and B now know the result, and neither can control which one is picked. Of course, sanity checks on the list will be performed by B after he decrypts the list (to make sure the list doesnt say 6 6 6 6 6 6 for example).

Ah, so the list that A sends B has exactly one instance of each number from 1..6?  143235 would be an invalid list?

That actually sounds like a fairly simple, but also very good way of doing it.

How would this work with >2 players?

[o.OV]

Shouldn't Player A also send the randomized list along with the decryption key?

Add-On:
This prevents Player A from generating a new key to output a new list
that has index number pointing to the number he/she wants.

Add-On:
With more players.
Player A should send the list to every player.
More players may contribute to choosing of index number
by choosing number 0 - 5 then sending it to everyone else.
Each person upon recieving the index number should add it up.
When all has contributed.. Mod 5 and send to Player A the index number.
Then A replies to all with the key and randomized list.

Does that work?

[dxoigmn]

Shouldn't Player A also send the randomized list along with the decryption key?

No because Player B could decode the randomized list, then figure out the order of the numbers and send back an index of their liking.

[o.OV]

Shouldn't Player A also send the randomized list along with the decryption key?

No because Player B could decode the randomized list, then figure out the order of the numbers and send back an index of their liking.

Player B doesn't recieve the key and randomized list until AFTER Player B sends the index.

Note:
I said randomized list not encrypted list.
I think you misinterpreted me.

[iago]

Shouldn't Player A also send the randomized list along with the decryption key?

Add-On:
This prevents Player A from generating a new key to output a new list
that has index number pointing to the number he/she wants.

Add-On:
With more players.
Player A should send the list to every player.
More players may contribute to choosing of index number
by choosing number 0 - 5 then sending it to everyone else.
Each person upon recieving the index number should add it up.
When all has contributed.. Mod 5 and send to Player A the index number.
Then A replies to all with the key and randomized list.

Does that work?

I think it should be mod6, but besides that, it seems to make sense.

[o.OV]

I think you are right iago. Mod 6
Minor miscalc on my part.

[Yoni]

This was discussed on another forum I used to frequent. Here's the solution that was obtained.

Player A wants to roll the dice. Player B is his opponent. When A rolls, he randomizes a list of possible outcomes (1 through 6), encrypts them with a secret key K, and sends the list to B (B doesn't know the key). B replies with a random index on that list. A replies with the decryption key. A and B now know the result, and neither can control which one is picked. Of course, sanity checks on the list will be performed by B after he decrypts the list (to make sure the list doesnt say 6 6 6 6 6 6 for example).

Interesting approach. I wonder how secure that is, though, because if what you're rolling is really a dice (only 6 outcomes), you have 6! or 720 different options for the randomized list. It might be possible to do a quick bruteforce on that, depending on the algorithm that is used.

[dxoigmn]

Shouldn't Player A also send the randomized list along with the decryption key?

No because Player B could decode the randomized list, then figure out the order of the numbers and send back an index of their liking.

Player B doesn't recieve the key and randomized list until AFTER Player B sends the index.

Note:
I said randomized list not encrypted list.
I think you misinterpreted me.

Oh yes, I have misinterpreted you.  Sorry.

[Adron]

Seems similar to the solution I proposed. This too has to be fully interconnected - in a server solution, the server could lie about what the other players chose.

[Banana fanna fo fanna]

Player B doesn't recieve the key and randomized list until AFTER Player B sends the index.

Then player A could stack the list so it would generate a result in its favor.

Perhaps the list could be several hundred numbers long, and the requirement is simply that each number has an equal distribution in the list.

[o.OV]

Player B doesn't recieve the key and randomized list until AFTER Player B sends the index.

Then player A could stack the list so it would generate a result in its favor.

I just realized that sending the randomized list is pointless..
However.. I find it weird that you would be going against your own proposed solution  

Perhaps the list could be several hundred numbers long, and the requirement is simply that each number has an equal distribution in the list.

You lost me..
Wouldn't the odds still be the same?
And having that many equal distributions will
only make it a hassle when checking for um..
equal distributiions of each number?