Secure Dice Rolling Protocol

[iago]

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.

I think the problem with stacking the list is that the list would be 6 *different* numbers, no repeats.  So it has exactly one 1, one 2, one 3, etc.

[herzog_zwei]

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).

This is also somewhat flawed.  With such a system, the server can generate keys that would decrypt the randomized list into a different list than it had originally intended.  Since there aren't that many possible outcomes of a die, you could come up with multiple keys beforehand for certain encrypted messages that would give you multiple answers that would pass sanity checks for B.  Since your encrypted data is so small (likely only 6 bytes long), encryption wouldn't be as effective no matter how long your key is.  To make it more effecitve, you'd want to add extra junk to the data (which would need more bandwidth requirements) and include some sort of hash/checksum (on the key and message) to lessen the chances of finding keys that decrypt it into multiple lists.

An easier approach (for more than two rollers) would be to have the server generate a random number and distribute it to all clients.  Each client will then send back a random number to the server.  Once the server receives a number back from all clients, it will send all clients the random numbers generated by all clients.  Each client will have to verify that the number it sent the server is indeed what the server said it is; if so and no other clients object to their numbers, it can add all the numbers up and mod 6 it to get a final answer.  The protocol is fairly easy to do but it'd require more fault tolerance for when clients get disconnected.

With the proposed approach (and possibly many other ones), you'd have to make sure that the one running the server doesn't also have some accomplice/non-existant client that'd influence the resulting answer, or that the server is kicking certain clients off to come up with a favorable roll.  This would be impossible to guarantee but precautions can be made to alleviate the problem.  For example, to combat the server kicking clients to come up with a favorable roll, you could nullify that roll.  To combat servers that stack the results with its own clients, one solution would be to maintain a list of cheating servers/clients on a central server (but if you're going to do that, why not just make a central die rolling server that all clients connect to (clients are grouped together so all rolls from a client will cause the server to send the roll to all clients in the group), thereby eliminating having to come up with elaborate schemes to try to prevent cheating).

[herzog_zwei]

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.

This isn't quite the same as what St0rm.iD's; it's weaker since all clients have the potential to cheat in your solution while in the other, the server has an easier time cheating (clients may be able to cheat if they can guess the contents of the message based upon the key, which might not be too difficult for a small message with a known set of ranges on the data).

You'd have to add some sort of challenge to it or else the hash will basically be the same as the number (after doing a reverse lookup from a precomputed table, which would likely only be the size of 0..5 or 0..INT_MAX, an amount that'd be easy to store in memory or on disk, or possibly be produced on the fly (0-5)).  Clients can just wait for others to answer or some maximum amount of time (so if there were 2 cheating clients with the same approach, it wouldn't be obvious that there are cheating clients waiting for others to answer) before sending out a hash of a number that would influence the roll.

[Adron]

This isn't quite the same as what St0rm.iD's; it's weaker since all clients have the potential to cheat in your solution while in the other, the server has an easier time cheating (clients may be able to cheat if they can guess the contents of the message based upon the key, which might not be too difficult for a small message with a known set of ranges on the data).

Ah, the random number wouldn't be in the range 1-6, it would be a large, say 128-bit random number. With that design, noone has the potential to cheat as far as I can see. The properties of the random number and the hash function must be such that the random number cannot be determined from the hash you receive in the first step.

[herzog_zwei]

Ah, the random number wouldn't be in the range 1-6, it would be a large, say 128-bit random number. With that design, noone has the potential to cheat as far as I can see. The properties of the random number and the hash function must be such that the random number cannot be determined from the hash you receive in the first step.

Be careful that you don't overdo it.  If you're going to use a 128-bit hash like MD5, you wouldn't want a 128-bit number since it raises the possibility of having collisions.  Also, adding more bits might not change the result (such as if you do something stupid like use say mod 8 to figure out a random number between 1 and 8 ).  If someone does find out collisions for it, they could delay their final response for the random number until it receives the answers from the other clients and send out the number that would benefit it more.

What really should be done is to present a challenge for each roll.  The challenge would make it so collisions can't be predetermined so they'd have to be figured out on the fly.  If the hashing algorithm used can do 100 hashes/sec, choose a range on the numbers that would require minutes/hours to hash a small percentage of that range.  So using MD5 on numbers with a 31 bit range would probably work as long as you present different challenges for each roll.  You'd have to make sure clients don't try to reuse the same challenge multiple times and you'd probably want a challenge be sent by a different client each time and isn't the roller.  You could make it a feedback based challenge that would be updated with the summation of numbers from the previous roll so no client can easily force a particular challenge (except on the very first roll).  You should also impose a reasonable timeout period (factoring in latency, packet loss, etc) so anything received later than say 15 seconds would be invalid and needs to be rerolled.  

You probably wouldn't want to use the resulting number as a seed for a psuedo-random number generater for all subsequent rolls (though it could be used for the x rolls (where x should be a low number, with 1 being preferred)) since a cheater could determine what the next roll(s) will be so they'll be able to bid less if they're gambling and has no chance of winning...  or they could enter a defense mode because if an enemy client were to attack on the next move, they'd do major damage to whomever they chose to attack.

[Adron]

The risk of having collisions isn't something you'll typically have to worry about. They'll be few and far between. If that was an issue, you'd want to never type a longer message than 16 characters if it was going to be signed with an algorithm using a 128-bit message digest. This way, you cannot change your random number based on knowledge of the random numbers chosen by other people.

And yes, the issue about a cheater using predictions of the prng to make decisions was what I wanted to counter with "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."

[herzog_zwei]

The risk of having collisions isn't something you'll typically have to worry about. They'll be few and far between. If that was an issue, you'd want to never type a longer message than 16 characters if it was going to be signed with an algorithm using a 128-bit message digest. This way, you cannot change your random number based on knowledge of the random numbers chosen by other people.

Yes, it's not typically what you need to worry about, but in this case, it would be something you should avoid.  Since you are not presenting any sort of challenge, a hash of X will always mean it can be N1, N2, N3, etc (though hopefully it will stop at just N1).  With a challenge, X can represent N1, N2 on the first roll, but the same hash of X in the next roll with a different challenge would likely mean it's not N1 nor N2.  With enough incentive, someone can brute force 1024 bit numbers (or whatever the range you choose) until they come up with a list of say 20 collisions and use those hashes sparingly to lessen the chances of being caught.  If you use a 128-bit number with a 128-bit digest, you weaken it further since there's a better chance of finding collisions.  If the range of the final answer will end up being from 1 to 6, having 2 possible outcomes could give you a big advantage.  The better choice would not be a bigger range on the random number but to present challenges for each roll while using a reasonable range for the number.

"... you will probably also want to include each players choice/move/whatever in the hash that is shared with every other player...."

(Taking it out of context since you're using it to make the PRNG better; I'll use it in this discussion to mean it's a challenge).  That'd help out a bit more though you could still brute force the space based upon number (choice/move) concatenate number.  Usually the scenario you'd want to cheat in will only be of 1 or a small set of choices so adding that to the hash is still weak.  Use a new challenge for each roll; it's simple to do and would improve it significantly.

I don't quite understand what you're trying to say with it taken in context.  I thought you meant all clients negotiate a seed at the beginning of the session to feed into a global (meaning all clients use the same seed in the game's PRNG, hence the parallelism) PRNG when taken along with the other parts of the method you suggested, though the "and then share your move with the others upon receipt of their move+number hashes" part seems to suggest it's done for each roll.  I'll take it that I misinterpreted it earlier and it's not being used as a global seed for all future rolls (which is probably why you quoted it back).

If you're worried about a weak PRNG from each client, it's easy enough to add entropy from other sources to the PRNG (amount of network traffic you've received, where your mouse is, etc) so prediction of the next number from a client shouldn't be as big an issue.

[Adron]

If players can cheat by having knowledge of the random numbers that will be generated, then you have to repeat this procedure for each roll. You cannot use a PRNG because then a player could run it ahead of time and pick a good move. If on the other hand players can't make such choices, you can use this procedure only at the beginning of the game.

Your statement of the possibility to brute force numbers that match a hash is a weakness of every system like this, including virtually every system for signing electronic messages. The assumption you'll have to make for a cryptographically secure message digest algorithm (which is what you need here) is that it's unfeasible to produce two messages that hash to the same value.

I doubt that people will actually be able to do that, since the complexity of brute forcing a 128-bit message is 2**64 which should be more than anyone is willing to spend on hacking a game. If it becomes an issue, you can switch to a 160-bit or longer hash. I'd be much more concerned about the possibility of brute forcing a legal document with a valid legally binding electronic signature though, if brute forcing was feasible.

[herzog_zwei]

Your statement of the possibility to brute force numbers that match a hash is a weakness of every system like this, including virtually every system for signing electronic messages. The assumption you'll have to make for a cryptographically secure message digest algorithm (which is what you need here) is that it's unfeasible to produce two messages that hash to the same value.

It is not feasible to do it in real-time, but it is feasible to have machines crunching numbers for months to get a few collisions that could be used later on to cheat the system.  Use a challenge/salt and you will solve multiple problems.  It'd take 10 minutes to modify what you have to make it magnitudes more secure than what it is now, yet you're against such a change.  Why?  If you've ever been to a casino, any visible marks on any card in any deck is tossed out because it has an identifying feature that you can correlate with a card value.  No matter how remote the chances of getting that card is, people can still figure out that the card with a torn corner on the top right edge is the king of hearts.  What you're suggesting w/o a challenge poses the exact same problem (though the chances of getting the card is even less likely); if someone sends hash H1, it will always represent N1 (or possibly others as well).  Add the challenge and you'll prevent precomputation of collisions and knowing what someone else's number is before it's given to you because H1 will only represent N1 once in a long while, N2 once in a long while, etc, rendering knowledge of H1 useless for all practical purposes with today's computers.  Unix and many other systems have salts on passwords to lessen the chances of password correlation for users that have the same passwords; it wasn't done to add more bits to the hash because adding more bits won't help any more, though it could make the hash less effective.

Would someone be willing to spend time to exploit that flaw?  Not likely if a good digest was used.  However, if money or access into a system were at stake, don't underestimate what others might do just because you're not willing to do it.

BTW: your method is probably the best one mentioned in this thread since it has the promise of rendering accomplice clients meaningless.  You just need to throw in a new challenge to it with each roll (you've already spent hours developing it, what's a few more minutes?).

[Skywing]

Yes, of course it would be wise to go the extra step for things such as monetary transactions.  However, it is probably not worth the trouble for the requirements of this particular system.

[Adron]

I still think someone producing collisions for a 128-bit hash is very unlikely to happen. I base that on my personal experience with cracking des (56-bit) keys for personal somewhat financial gain. Consider the amount of time and memory you'd have to spend...

But, I suppose adding a challenge is a good idea anyway since the cost is so low

Also, every client should generate a piece of the challenge, so the server + a client can't conspire to use hashes with collisions.

[K]

Storm's idea seems to be an adaptation of the simple coin flipping problem:  how do two remote clients agree on a random coin flip?

Player 1 chooses a random number N and sends its hash to Player 2.
Player 2 guesses whether N is odd or even and sends his guess to Player 1.
Player 1 Now sends N to Player 2 who verifies that this is is the correct number by checking it against the hash.
If Player 2 guessed correctly, the coin is heads.  Otherwise it is tails.

[herzog_zwei]

K: That sounds more like Adron's adaptation than Storm's: Storm's used symmetric key encryption with all parts of the key and message generated by the same client.

I still think someone producing collisions for a 128-bit hash is very unlikely to happen. I base that on my personal experience with cracking des (56-bit) keys for personal somewhat financial gain. Consider the amount of time and memory you'd have to spend...

Also, every client should generate a piece of the challenge, so the server + a client can't conspire to use hashes with collisions.

You could feed back the resulting random number chosen by all clients back into the challenge so no one client will have absolute say over what the challenge is.  The very first roll will need to be thrown out since it'd probably be seeded by one of the clients or set to an initial value (to keep the protocol simple).

As impossible as it might seem, someone with lots of cryptography knowledge might be able to produce a good attack on it.  You're also looking for colliisions of any hash in the number space, not just for a specific hash, which was probably what you were doing with DES.  Also, to conserve memory, you don't have to store all of the hash; just enough to recognize that there might be a match so you can redo the calculation again to see if there really was one.

There was a seemingly impossible challenge I had years back when 286/386 machines were top of the line, 20-80MB HD space was godly, and 640K of memory was typical.  The challenge was to come up with all solutions of the combination of N numbers ranging from 1 to x that added up to S.  For some sums of S, there were millions of solutions which would take many MBs to store on disk.  Typical bruteforcing of it would have taken months and consume lots of memory.  However, my intuition told me ther was a much better way of bruteforcing it than the traditional one so I had a go at it and was able to come up with something that could produce all solutions (even if there were millions) in maybe 40 seconds at worst and store all of it in under 500K (not sure how much memory it really took up since I never checked but it definitely didn't use up all of the 640K).  I did this by saving part of the state at every i iterations and since what I was doing could be computed fast, I could come up with the next j iterations in real-time.  I implemented it in ASM, C, and interpreted BASIC (the BASIC version ran much faster than the typical bruteforcing method done in C).  Bruteforcing cryptography is orders of magnitudes harder than this but it shows that just because most people think something is not feasible doesn't mean it really is; it might just require a different look at the problem.  An example is 512-bit RSA was once thought secure but later on found that 2048-bit should be used, not because computers have gotten faster but because there was an attack on it that could weaken it greatly.

[Adron]

You're also looking for colliisions of any hash in the number space, not just for a specific hash, which was probably what you were doing with DES.  

True, which reduces the complexity to half the number of bits, if you can store so many hashes. For a 128-bit hash, you'd have to calculate and store 2**64 results. That requires a *lot* of memory as well as a lot of time. Look at this page for info on this "birthday attack".

[herzog_zwei]

Nice info.  I don't disagree with you that it's improbable to do for almost (maybe even all) 100% of the population with today's technology.  However, adding the challenge at minimal cost to your time will make it improbable for many future technologies to come.  If it took weeks to add in the challenge, it wouldn't be worth the effort for a simple game.

That page did mention that differential cryptanalysis was effective against 1 of the MD5 rounds.  Perhaps a better brute forcer will do it based upon analysis of the rounds and not the finalized digest (it probably wouldn't be that easy otherwise people would have come up with it by now, but it's something to consider).

Off topic, but if the need arises, md5sum is a great tool to use for finding duplicate files (mainly email attachments) under different file names on corporate file servers.