From ba8ddce7435dc2857d35852963342a2a3439ab0c007e507aa14c063553851991 Mon Sep 17 00:00:00 2001 From: Nicholas Johnson Date: Tue, 14 Feb 2023 00:00:00 +0000 Subject: Convert refs: remote-fair-coin-flipping-with-friends --- .../remote-fair-coin-flipping-with-friends.md | 46 +++++++--------------- 1 file changed, 14 insertions(+), 32 deletions(-) (limited to 'content') diff --git a/content/entry/remote-fair-coin-flipping-with-friends.md b/content/entry/remote-fair-coin-flipping-with-friends.md index 2199229..c1fffe4 100644 --- a/content/entry/remote-fair-coin-flipping-with-friends.md +++ b/content/entry/remote-fair-coin-flipping-with-friends.md @@ -2,23 +2,22 @@ title: "Remote Fair Coin Flipping with Friends" date: 2020-11-19T00:00:00 draft: false -makerefs: false --- -Suppose you and some friends want to flip a coin without meeting up. It has to be done over an authenticated communication channel[1] 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://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. # 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[2] 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[3]): echo -n "1 munxpawrqoivzhujfxbxwcang" | sha256sum +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 +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[4] 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://www.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 +25,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[5] 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[6]): echo -n "01010 yabynkgpbfnagntyzvgvgmwaa" | sha256sum +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 +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[7] 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://www.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[8] 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://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: 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[9] 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[10]): echo -n "1 munxpawrqoivzhujfxbxwcang" | sha256sum +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 +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[11] all results. +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. 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[12] 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[13]): echo -n "01010 yabynkgpbfnagntyzvgvgmwaa" | sha256sum +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 +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[14] all results. +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. 10. Convert the values from step 9 back to heads or tails as defined in step 1. # Rationale @@ -86,20 +85,3 @@ You might be thinking more democratically though. Instead of having a single lea # Why You Don't Roll Your Own Crypto By now you should have begun to see why a more advanced "common coin" algorithm is needed. This is a cryptosystem that doesn't have a good way to prevent an attacker from compromising the integrity of the coin flip, or forever stalling it. Any attempt to solve this problem just ends up pushing it back a step. In other words, this cryptosystem I've created is hopelessly broken and the only way to fix it is a completely different algorithm. But I can get away with it because I can say it's just a toy cryptosystem for fun. It should never be used for any real-world application. Use a common coin instead. And it's also an example of why you should never roll your own crypto. Even when it seems foolproof, there's always weird edge cases that ruin everything. This post shows a neat thing you can do with friends and also demonstrates why you should always use established cryptosystems rather than inventing your own. I hope you enjoyed it. - - -Link(s): -[1: https://www.wikipedia.org/wiki/Secure_channel](https://www.wikipedia.org/wiki/Secure_channel) -[2: https://www.wikipedia.org/wiki/Cryptographic_nonce](https://www.wikipedia.org/wiki/Cryptographic_nonce) -[3: https://www.gnu.org/software/bash/](https://www.gnu.org/software/bash/) -[4: https://www.wikipedia.org/wiki/Exclusive_or](https://www.wikipedia.org/wiki/Exclusive_or) -[5: https://www.wikipedia.org/wiki/Cryptographic_nonce](https://www.wikipedia.org/wiki/Cryptographic_nonce) -[6: https://www.gnu.org/software/bash/](https://www.gnu.org/software/bash/) -[7: https://www.wikipedia.org/wiki/Exclusive_or](https://www.wikipedia.org/wiki/Exclusive_or) -[8: https://www.wikipedia.org/wiki/Replay_attack](https://www.wikipedia.org/wiki/Replay_attack) -[9: https://www.wikipedia.org/wiki/Cryptographic_nonce](https://www.wikipedia.org/wiki/Cryptographic_nonce) -[10: https://www.gnu.org/software/bash/](https://www.gnu.org/software/bash/) -[11: https://www.wikipedia.org/wiki/Exclusive_or](https://www.wikipedia.org/wiki/Exclusive_or) -[12: https://www.wikipedia.org/wiki/Cryptographic_nonce](https://www.wikipedia.org/wiki/Cryptographic_nonce) -[13: https://www.gnu.org/software/bash/](https://www.gnu.org/software/bash/) -[14: https://www.wikipedia.org/wiki/Exclusive_or](https://www.wikipedia.org/wiki/Exclusive_or) -- cgit v1.2.3