diff options
Diffstat (limited to 'content/entry/remote-fair-coin-flipping-with-friends.md')
| -rw-r--r-- | content/entry/remote-fair-coin-flipping-with-friends.md | 20 |
1 files changed, 10 insertions, 10 deletions
diff --git a/content/entry/remote-fair-coin-flipping-with-friends.md b/content/entry/remote-fair-coin-flipping-with-friends.md index a95f3ca..cfce132 100644 --- a/content/entry/remote-fair-coin-flipping-with-friends.md +++ b/content/entry/remote-fair-coin-flipping-with-friends.md @@ -4,21 +4,21 @@ date: 2020-11-19T00:00:00 tags: ['computing'] draft: false --- -Suppose you and some friends want to flip a coin without meeting up. It has to be done over an [authenticated communication channel](https://www.wikipedia.org/wiki/Secure_channel) such as a secure messaging app. How can you do it such that nobody can predict the final result? I'll explain how to do it fairly. I'm well aware of common coin algorithms. This post is mostly just for amusement. It's my half-hearted attempt at designing a cryptosystem. More on that later. +Suppose you and some friends want to flip a coin without meeting up. It has to be done over an [authenticated communication channel](https://en.wikipedia.org/wiki/Secure_channel) such as a secure messaging app. How can you do it such that nobody can predict the final result? I'll explain how to do it fairly. I'm well aware of common coin algorithms. This post is mostly just for amusement. It's my half-hearted attempt at designing a cryptosystem. More on that later. # Coin Flipping ## Flipping a Coin with a Friend These are the steps for performing a single coin flip: 1. Flip a physical coin. Heads represents 0. Tails represents 1. -2. Append to the result of step 1 a space followed by a [nonce](https://www.wikipedia.org/wiki/Cryptographic_nonce) that your friend cannot easily guess. Never reuse the nonce. For tails, it will look like this: 1 munxpawrqoivzhujfxbxwcang +2. Append to the result of step 1 a space followed by a [nonce](https://en.wikipedia.org/wiki/Cryptographic_nonce) that your friend cannot easily guess. Never reuse the nonce. For tails, it will look like this: 1 munxpawrqoivzhujfxbxwcang 3. Calculate the SHA-256 hash of the string in step 2 (in [Bash](https://www.gnu.org/software/bash/)): echo -n "1 munxpawrqoivzhujfxbxwcang" | sha256sum 4. Publish the hash from step 3 onto the authenticated communication channel. 5. Pause until your friend completes step 4. 6. Publish the result from step 2 onto the authenticated communication channel. 7. Pause until your friend completes step 6. 8. Calculate the hash of your friend's step 2 result comparing it to their step 3 result. If it doesn't match, then one of you has incorrectly computed the hash. -9. If the hashes match, remove the space and nonce from both you and your friend's step 2 results. Then [XOR](https://www.wikipedia.org/wiki/Exclusive_or) both results. +9. If the hashes match, remove the space and nonce from both you and your friend's step 2 results. Then [XOR](https://en.wikipedia.org/wiki/Exclusive_or) both results. 10. Convert the value from step 9 back to heads or tails as defined in step 1. ## Flipping Multiple Coins with a Friend @@ -26,42 +26,42 @@ These are the steps for performing a single coin flip: If you want to flip multiple coins, you can repeat steps 1-10 of the single coin flip, but that's very cumbersome. There's an easier solution. Suppose you and your friend want to flip N coins: 1. Flip N physical coins. Heads represents 0. Tails represents 1. Concatenate the coin flip results. -2. Append to the result of step 1 a space followed by a [nonce](https://www.wikipedia.org/wiki/Cryptographic_nonce) that your friend cannot easily guess. Never reuse the nonce. For the sequence heads tails heads tails heads, it will look like this: 01010 yabynkgpbfnagntyzvgvgmwaa +2. Append to the result of step 1 a space followed by a [nonce](https://en.wikipedia.org/wiki/Cryptographic_nonce) that your friend cannot easily guess. Never reuse the nonce. For the sequence heads tails heads tails heads, it will look like this: 01010 yabynkgpbfnagntyzvgvgmwaa 3. Calculate the SHA-256 hash of the string in step 2 (in [Bash](https://www.gnu.org/software/bash/)): echo -n "01010 yabynkgpbfnagntyzvgvgmwaa" | sha256sum 4. Publish the hash from step 3 onto the authenticated communication channel. 5. Pause until your friend completes step 4. 6. Publish the result from step 2 onto the authenticated communication channel. 7. Pause until your friend completes step 6. 8. Calculate the hash of your friend's step 2 result comparing it to their step 3 result. If it doesn't match, then one of you has incorrectly computed the hash. -9. If the hashes match, remove the space and nonce from both you and your friend's step 2 results. Then [XOR](https://www.wikipedia.org/wiki/Exclusive_or) both results. +9. If the hashes match, remove the space and nonce from both you and your friend's step 2 results. Then [XOR](https://en.wikipedia.org/wiki/Exclusive_or) both results. 10. Convert the values from step 9 back to heads or tails as defined in step 1. ## Flipping a Coin with 3+ Friends -It is possible to perform a remote fair coin flip with 3 or more participants, but there are 3 caveats. One caveat is depending on how many participants you have, it could take quite a bit longer than the previous cases where you only have 1 other person. This is because everyone has to participate in the coin flip if everyone wants to ensure fairness. Otherwise the other participants can collude to manipulate the coin flip. The second caveat is you need to have a robust authenticated group communication channel resistant to [replay attacks](https://www.wikipedia.org/wiki/Replay_attack) and other funny business such as messages being edited/deleted without indication and out of order message receipt. But maybe that's taking my cryptosystem too seriously. The third caveat is increased complexity. All participants will need to know how to perform all the steps and there's a greater chance someone doesn't do step 3 right. Regardless, here's how you flip a coin with 3+ friends: +It is possible to perform a remote fair coin flip with 3 or more participants, but there are 3 caveats. One caveat is depending on how many participants you have, it could take quite a bit longer than the previous cases where you only have 1 other person. This is because everyone has to participate in the coin flip if everyone wants to ensure fairness. Otherwise the other participants can collude to manipulate the coin flip. The second caveat is you need to have a robust authenticated group communication channel resistant to [replay attacks](https://en.wikipedia.org/wiki/Replay_attack) and other funny business such as messages being edited/deleted without indication and out of order message receipt. But maybe that's taking my cryptosystem too seriously. The third caveat is increased complexity. All participants will need to know how to perform all the steps and there's a greater chance someone doesn't do step 3 right. Regardless, here's how you flip a coin with 3+ friends: 1. Flip a physical coin. Heads represents 0. Tails represents 1. -2. Append to the result of step 1 a space followed by a [nonce](https://www.wikipedia.org/wiki/Cryptographic_nonce) that your friends cannot easily guess. Never reuse the nonce. For tails, it will look like this: 1 munxpawrqoivzhujfxbxwcang +2. Append to the result of step 1 a space followed by a [nonce](https://en.wikipedia.org/wiki/Cryptographic_nonce) that your friends cannot easily guess. Never reuse the nonce. For tails, it will look like this: 1 munxpawrqoivzhujfxbxwcang 3. Calculate the SHA-256 hash of the string in step 2 (in [Bash](https://www.gnu.org/software/bash/)): echo -n "1 munxpawrqoivzhujfxbxwcang" | sha256sum 4. Publish the hash from step 3 onto the authenticated communication channel. 5. Pause until all your friends complete step 4. 6. Publish the result from step 2 onto the authenticated communication channel. 7. Pause until all your friends complete step 6. 8. Calculate the hashes of your friends' step 2 results comparing it to their step 3 results. If they don't match, then one of you has incorrectly computed the hash. -9. If the hashes match, remove the space and nonce from both you and your friends' step 2 results. Then [XOR](https://www.wikipedia.org/wiki/Exclusive_or) all results. +9. If the hashes match, remove the space and nonce from both you and your friends' step 2 results. Then [XOR](https://en.wikipedia.org/wiki/Exclusive_or) all results. 10. Convert the value from step 9 back to heads or tails as defined in step 1. ## Flipping Multiple Coins with 3+ Friends This is the most difficult coin flip: multiple coins with more than 2 participants. I think you get the gist of it by now and I don't really need to type all this out, but I will for completeness sake. Not much will be changed from the above steps though. 1. Flip N physical coins. Heads represents 0. Tails represents 1. Concatenate the coin flip results. -2. Append to the result of step 1 a space followed by a [nonce](https://www.wikipedia.org/wiki/Cryptographic_nonce) that your friends cannot easily guess. Never reuse the nonce. For the sequence heads tails heads tails heads, it will look like this: 01010 yabynkgpbfnagntyzvgvgmwaa +2. Append to the result of step 1 a space followed by a [nonce](https://en.wikipedia.org/wiki/Cryptographic_nonce) that your friends cannot easily guess. Never reuse the nonce. For the sequence heads tails heads tails heads, it will look like this: 01010 yabynkgpbfnagntyzvgvgmwaa 3. Calculate the SHA-256 hash of the string in step 2 (in [Bash](https://www.gnu.org/software/bash/)): echo -n "01010 yabynkgpbfnagntyzvgvgmwaa" | sha256sum 4. Publish the hash from step 3 onto the authenticated communication channel. 5. Pause until all your friends complete step 4. 6. Publish the result from step 2 onto the authenticated communication channel. 7. Pause until all your friends complete step 6. 8. Calculate the hashes of your friends' step 2 results comparing it to their step 3 results. If they don't match, then one of you has incorrectly computed the hash. -9. If the hashes match, remove the space and nonce from both you and your friends' step 2 results. Then [XOR](https://www.wikipedia.org/wiki/Exclusive_or) all results. +9. If the hashes match, remove the space and nonce from both you and your friends' step 2 results. Then [XOR](https://en.wikipedia.org/wiki/Exclusive_or) all results. 10. Convert the values from step 9 back to heads or tails as defined in step 1. # Rationale |