Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I found this question on the game programming site and was intrigued. I came up with an answer off the top of my head but I'm no cryptanalyst so it is probably not water-tight.

This is how my idea goes:

  1. each of the two peers generates a random number.
  2. each peer creates a salted hash of its number and sends it to the other peer.
  3. once both peers confirm reception of each other's hashes, each then sends the other its actual random number.
  4. each peer verifies that the hash sent by the other is actually a hash of the random number.
  5. the result of the coin flip is the XOR of the least significant bit of each number, i.e.

    (a & 1) ^ (b & 1)

So would it work? If not, how could it be made secure? Is there some conventional method for solving problems like this one?

The rules are, there are two untrusted parties with no intermediary. Assume the channel of communication is secure. Neither party must be able to unfairly win or lose.

share|improve this question
add comment

1 Answer

Yes, your basic idea is feasible. What you are describing is a distributed coin flip protocol based on a commitment scheme.

However, you protocol as described is vulnerable to replay attacks: after one peer receives the other's hash, they can send back the same hash, wait for the other peer to reveal their random bit and salt, and send back those as well. That way, they can force the outcome of the XOR operation to always be 0.

There are a number of ways to modify this protocol so that this attack won't work:

  • include a unique peer ID in the hash input,
  • abort (or restart) the protocol if two peers produce the same hash value, or
  • require the peer who revealed their hash last to be the first one to reveal their inputs.

Any one of these modifications would be enough to prevent this attack.

Edit: I thought this seemed familiar. Here's my earlier answer to essentially the same question.

share|improve this answer
    
How would a replay attack work? A peer that receives the exact hash it just sent can simply reject the exchange. Re-use of previous hashes provides no benefit to the sender, only the receiver. –  Michael Slade Apr 30 '12 at 15:24
3  
It can reject it, yes, but nothing in the protocol as you wrote it says it should do so. Remember that computers (which are what you'd use to implement this protocol in practice) only do what you tell them to, not what you want them to. :) –  Ilmari Karonen Apr 30 '12 at 15:27
    
Then AFAICT all I need to to is have each peer reject the hash it receives if it is identical to the one it sent. unique id's are covered by salt. Order is not important as long as one peer gets a hash before revealing its random number. In fact I think only one end needs to create a hash in the first place. –  Michael Slade Apr 30 '12 at 15:40
    
Yes, that's a possible optimization. More generally, if you do this with $n$ peers, only $n-1$ of them need to publish commitments. –  Ilmari Karonen Apr 30 '12 at 15:44
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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