4 ms·

Provably Fair Shuffling Through Cryptography (2012)

28 points by petrosagg 12y ago

vilhelm_s 12y ago
Revealing the deck after the game is over works for Blackjack, but it would be a problem for Poker. There, players who fold do not want anyone to know what cards they held. Is there a way to make a protocol that can reveal cheating while not revealing the actual cards?
fryguy 12y ago
This only works for games where one party can know the contents of the deck, and can be trusted not to reveal them to others. For instance, if you're in the last spot in blackjack, the players ahead of you can know the cards in the deck and hit/stay in order to force bad cards onto you if they are colluding with the house. Also, I'm assuming that the hash is revealed before you accept the client_seed, otherwise the server can trivially make any arbitray shuffle based on the client seed. There are several algorithms involving multi-party encryption that actually solve this problem fully. Google for "mental poker" to find more details. There are two classes that are pretty straightforward to talk about. The first involves encryption/decryption that can be done in any order (for instance m -> E1 -> E2 -> D1 -> D2 = m). The first person encrypts the entire deck with the same key, and then shuffles it any way he pleases and sends it to the next person until everyone has encrypted it. Then the second phase is everyone removing their generic key, and applying a specific key for the nth card of the deck. This results in a deck that has been encrypted with unique keys for each slot in the deck. To reveal a card to a player, simply reveal the decryption key for that slot to the players that need to know what it is. This scheme is secure assuming there is a step that verifies that you are being honest when shuffling (it's not trivial to explain how to do this though). The other way is to generate an encrypted random number corresponding to one of the cards in the deck. To reveal which card it was, just send the decryption keys to the people that need to know it. The other concern is that the same card could be dealt twice, so the trick is to compare the number to all the other numbers to see if they are the same, without decrypting them.
- petrosagg 12y ago
  For the first method to work the encryption function must be commutative. Are there any commutative encryption functions?
  - fryguy 12y ago
    Single-prime RSA is commutative. Agree on prime p, and encrypt with random prime e. d = e^-1 (mod p-1) which is easy to calculate using Extended Euclidean Algorithm. With keys e and r, (m^e)^r === m^er === m^re === (m^r)^e (mod p).
    - stouset 12y ago
      Asymmetric cryptography isn't necessary here, and is typically much slower and much more complicated. Any stream cipher (e.g., AES-CTR) XORs a keystream against the plaintext. XOR is trivially commutative. Players would have to commit to their keys ahead of time, however (one approach is to publish a hash of the key). Otherwise, a player can cheat by enumerating keys at random until they find one that causes the deck to decrypt to a more favorable ordering.
      - fryguy 12y ago
        You don't really even need a stream cipher, just random data if you're using XOR. You're right that XOR is trivially commutative, but it is weak to known-plaintext attacks which makes it unsuitable for this algorithm. Suppose you have a deck { 1, 2, 3, 4 }, I'm alice(A) and you're bob(B) and I'll denote xor with dot. I shuffle it with the first round, revealing { A(3), A(1), A(2), A(4) } and then you shuffle revealing { B.A(2), B.A(4), B.A(3), B.A(1) } Then we re-encrypt with unique keys: { A_1.B(2), A_2.B(4), A_3.B(3), A_4.B(1) } { A_1.B_1(2), A_2.B_2(4), A_3.B_3(3), A_4.B_4(1) } Now you "deal" me the first card by revealing B_1. This means that I know that the first slot is card 2. But I also know `B xor A xor 2` from the end of the first phase, which means it's easy to calculate what `B xor A` is. From this, I can decrypt the entire deck.
        12y ago
web007 12y ago
They probably shouldn't be using MT for their random number generator - http://en.wikipedia.org/wiki/Mersenne_twister#Alternatives http://en.wikipedia.org/wiki/Mersenne_twister#Alternatives
- petrosagg 12y ago
  Given that it's a two year old post they may have changed their PRNG.
  - stouset 12y ago
    Honestly, the post reads as cryptographically incompetent to me. > Just in case the Mersenne Twister algorithm has any unknown vulnerabilities The Mersenne Twister has known vulnerabilities. Seeing 624 iterations of the output is enough to reconstruct all future outputs. Does this affect their algorithm in practice? I don't know — but just as it's better to lay a building on a strong foundation rather than sand, it's better to design secure protocols with strong cryptographic components with well-tested security features and proofs than to compose multiple weak components and hope for the best. This protocol also only demonstrates that the casino is "fair", in that it's shuffling decks in an ordering which is not known to the casino ahead of time. This is a far cry from "secure", which would (amongst other things) ensure the casino doesn't even know which card it's dealing until the card has been dealt (ensuring the casino can't collude with other players), and that other players can't predict the next cards with a better probability than random luck.
javajosh 12y ago
TL;DR: No - actually, there is no way to protect a player from a bad actor casino. The server always knows the state of the deck! Hashing, cutting, etc doesn't matter. In that game of high card, the computer can win in every case but one, when you pick the absolute highest card. Further, the "fairness" of the shuffle has more to do with the ability to identify (or define) "noise", which is an extremely hard problem mainly because noise is a definition of exclusion. E.g. if a sequence can't mean anything, then we define it to be noise. But how many possible meanings can a string have? I think the technical term is lots, although there are others that involve boldfaced greek letters. Players have to trust the casino. There is no test a player can do to "verify" a casino is being fair. (The real attack vector a casino has to worry about is if someone can predict or retrieve the PRNG seed that you used for a particular shuffle, which would be enough for the player to infer the content of the deck - which is what the casino already knows.)
- petrosagg 12y ago
  Actually, you don't have to trust the casino. As pointed out by fryguy there are ways to ensure no party knows the deck [1]. [1] http://en.wikipedia.org/wiki/Mental_poker#Shuffling_cards_using_commutative_encryption http://en.wikipedia.org/wiki/Mental_poker#Shuffling_cards_us...
  - javajosh 12y ago
    Wow, I've never heard of commutative encryption and this is a clever application! My claim was wrong - although the OP doesn't mention this in his article.
nrubin 12y ago
Quick question about one of the algorithms this article proposes: >Instead, we compute a seed by combining a server_seed (which is provided in hashed form to the client before the deal - in the same way as the initial_shuffle is) and a client_seed. What if the server picked a large value and this appending caused an overflow? Don't some languages/runtimes turn an overflow into 0? Then the server could always seed the RNG the same way. I'm probably very wrong, can someone tell me why?
Pyramids 12y ago
Although much simpler, this reminded me of a website from ~2008 which did the same thing with the now defunct Liberty Reserve combined with a basic coin flip game. The site is, surprisingly, still online[1] and now accepting Perfect Money in place of Liberty Reserve. Unfortunately, they seem to still be using MD5 hashes even years later, for example: TAIL/OaU1ERm1ZbUl5WWpGbE5UTm bf30359e539686fb3eaa9abf9701938e [1] http://win29.com/game.ht.php http://win29.com/game.ht.php

28 points by petrosagg 12y ago

Revealing the deck after the game is over works for Blackjack, but it would be a problem for Poker. There, players who fold do not want anyone to know what cards they held. Is there a way to make a protocol that can reveal cheating while not revealing the actual cards?

fryguy 12y ago

This only works for games where one party can know the contents of the deck, and can be trusted not to reveal them to others. For instance, if you're in the last spot in blackjack, the players ahead of you can know the cards in the deck and hit/stay in order to force bad cards onto you if they are colluding with the house. Also, I'm assuming that the hash is revealed before you accept the client_seed, otherwise the server can trivially make any arbitray shuffle based on the client seed. There are several algorithms involving multi-party encryption that actually solve this problem fully. Google for "mental poker" to find more details. There are two classes that are pretty straightforward to talk about. The first involves encryption/decryption that can be done in any order (for instance m -> E1 -> E2 -> D1 -> D2 = m). The first person encrypts the entire deck with the same key, and then shuffles it any way he pleases and sends it to the next person until everyone has encrypted it. Then the second phase is everyone removing their generic key, and applying a specific key for the nth card of the deck. This results in a deck that has been encrypted with unique keys for each slot in the deck. To reveal a card to a player, simply reveal the decryption key for that slot to the players that need to know what it is. This scheme is secure assuming there is a step that verifies that you are being honest when shuffling (it's not trivial to explain how to do this though). The other way is to generate an encrypted random number corresponding to one of the cards in the deck. To reveal which card it was, just send the decryption keys to the people that need to know it. The other concern is that the same card could be dealt twice, so the trick is to compare the number to all the other numbers to see if they are the same, without decrypting them.

petrosagg 12y ago
For the first method to work the encryption function must be commutative. Are there any commutative encryption functions?
- fryguy 12y ago
  Single-prime RSA is commutative. Agree on prime p, and encrypt with random prime e. d = e^-1 (mod p-1) which is easy to calculate using Extended Euclidean Algorithm. With keys e and r, (m^e)^r === m^er === m^re === (m^r)^e (mod p).
  - stouset 12y ago
    Asymmetric cryptography isn't necessary here, and is typically much slower and much more complicated. Any stream cipher (e.g., AES-CTR) XORs a keystream against the plaintext. XOR is trivially commutative. Players would have to commit to their keys ahead of time, however (one approach is to publish a hash of the key). Otherwise, a player can cheat by enumerating keys at random until they find one that causes the deck to decrypt to a more favorable ordering.
    - fryguy 12y ago
      You don't really even need a stream cipher, just random data if you're using XOR. You're right that XOR is trivially commutative, but it is weak to known-plaintext attacks which makes it unsuitable for this algorithm. Suppose you have a deck { 1, 2, 3, 4 }, I'm alice(A) and you're bob(B) and I'll denote xor with dot. I shuffle it with the first round, revealing { A(3), A(1), A(2), A(4) } and then you shuffle revealing { B.A(2), B.A(4), B.A(3), B.A(1) } Then we re-encrypt with unique keys: { A_1.B(2), A_2.B(4), A_3.B(3), A_4.B(1) } { A_1.B_1(2), A_2.B_2(4), A_3.B_3(3), A_4.B_4(1) } Now you "deal" me the first card by revealing B_1. This means that I know that the first slot is card 2. But I also know `B xor A xor 2` from the end of the first phase, which means it's easy to calculate what `B xor A` is. From this, I can decrypt the entire deck.
      - 12y ago

web007 12y ago

They probably shouldn't be using MT for their random number generator - http://en.wikipedia.org/wiki/Mersenne_twister#Alternatives http://en.wikipedia.org/wiki/Mersenne_twister#Alternatives

petrosagg 12y ago
Given that it's a two year old post they may have changed their PRNG.
- stouset 12y ago
  Honestly, the post reads as cryptographically incompetent to me. > Just in case the Mersenne Twister algorithm has any unknown vulnerabilities The Mersenne Twister has known vulnerabilities. Seeing 624 iterations of the output is enough to reconstruct all future outputs. Does this affect their algorithm in practice? I don't know — but just as it's better to lay a building on a strong foundation rather than sand, it's better to design secure protocols with strong cryptographic components with well-tested security features and proofs than to compose multiple weak components and hope for the best. This protocol also only demonstrates that the casino is "fair", in that it's shuffling decks in an ordering which is not known to the casino ahead of time. This is a far cry from "secure", which would (amongst other things) ensure the casino doesn't even know which card it's dealing until the card has been dealt (ensuring the casino can't collude with other players), and that other players can't predict the next cards with a better probability than random luck.

javajosh 12y ago

TL;DR: No - actually, there is no way to protect a player from a bad actor casino. The server always knows the state of the deck! Hashing, cutting, etc doesn't matter. In that game of high card, the computer can win in every case but one, when you pick the absolute highest card. Further, the "fairness" of the shuffle has more to do with the ability to identify (or define) "noise", which is an extremely hard problem mainly because noise is a definition of exclusion. E.g. if a sequence can't mean anything, then we define it to be noise. But how many possible meanings can a string have? I think the technical term is lots, although there are others that involve boldfaced greek letters. Players have to trust the casino. There is no test a player can do to "verify" a casino is being fair. (The real attack vector a casino has to worry about is if someone can predict or retrieve the PRNG seed that you used for a particular shuffle, which would be enough for the player to infer the content of the deck - which is what the casino already knows.)

petrosagg 12y ago
Actually, you don't have to trust the casino. As pointed out by fryguy there are ways to ensure no party knows the deck [1]. [1] http://en.wikipedia.org/wiki/Mental_poker#Shuffling_cards_using_commutative_encryption http://en.wikipedia.org/wiki/Mental_poker#Shuffling_cards_us...
- javajosh 12y ago
  Wow, I've never heard of commutative encryption and this is a clever application! My claim was wrong - although the OP doesn't mention this in his article.

nrubin 12y ago

Quick question about one of the algorithms this article proposes: >Instead, we compute a seed by combining a server_seed (which is provided in hashed form to the client before the deal - in the same way as the initial_shuffle is) and a client_seed. What if the server picked a large value and this appending caused an overflow? Don't some languages/runtimes turn an overflow into 0? Then the server could always seed the RNG the same way. I'm probably very wrong, can someone tell me why?

Pyramids 12y ago

Although much simpler, this reminded me of a website from ~2008 which did the same thing with the now defunct Liberty Reserve combined with a basic coin flip game. The site is, surprisingly, still online[1] and now accepting Perfect Money in place of Liberty Reserve. Unfortunately, they seem to still be using MD5 hashes even years later, for example: TAIL/OaU1ERm1ZbUl5WWpGbE5UTm bf30359e539686fb3eaa9abf9701938e [1] http://win29.com/game.ht.php http://win29.com/game.ht.php