10
$\begingroup$

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.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Michael Slade
    Commented Apr 30, 2012 at 15:24
  • 5
    $\begingroup$ 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. :) $\endgroup$
    – Ilmari Karonen
    Commented Apr 30, 2012 at 15:27
  • $\begingroup$ 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. $\endgroup$
    – Michael Slade
    Commented Apr 30, 2012 at 15:40
  • $\begingroup$ Yes, that's a possible optimization. More generally, if you do this with $n$ peers, only $n-1$ of them need to publish commitments. $\endgroup$
    – Ilmari Karonen
    Commented Apr 30, 2012 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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