5 ms·

Provably Fair Shuffling Through Cryptography (2012)

19 points by tlrobinson 13y ago

tlrobinson 13y ago
I'm no crypto expert, but their use of Mersenne Twisters and 32 bit seeds seems suspect to me. In theory couldn't the casino compute all 2^32 possible seeds for a bunch of server seeds, and select the ones that are biased in their favor?
- kedean 13y ago
  They mention that they first do enough shuffling to cover all possibilities of the deck, then apply the seeded shuffling.
  - sirclueless 13y ago
    The "enough shuffling to cover all possibilities of the deck" is a server-side-only operation. It's not verified at all, they could replace a pre-shuffled deck with a carefully chosen one if they liked.
- advisedwang 13y ago
  Essentially yes. As with the shuffle-and-cut example the server can constrain the possible choices. However this seems to be an impractical as this requires an astronomical amount of effort - the server would need to run through all 2^32 shuffles from the deck they pick just to see if that deck was favourable. This would be exceedingly rare, so a vast number of shuffles must be tested in this manner.
  - sirclueless 13y ago
    You don't have to do it for every deck. You can work backwards from a desirable end result. For example, here's a really dumb formula to do a tiny bit better than random: The game is "Black or red," where the top card of the deck is revealed. If it is black (clubs or spades), you win. If it is red (hearts or diamonds), the casino wins. The casino can cheat as follows: It generates all 2^32 possible Mersenne "cuts" of the deck. Then it finds those card positions which, through random chance, are shuffled to the top slightly more often by the Mersenne cut process. Then it chooses a deck to reveal as the "shuffled" deck at the beginning with a disproportionately large number of red cards in those locations. Since they will get cut to the top more than 50% of the time, the casino can do more than break even. The law of large numbers and the fact that MT19937 is a decent PRNG that passes an awful lot of randomness tests says that the chance of each position being "cut" to the top is almost exactly 1/52. So the casino isn't going to do much better than 50% on this game. But the Mersenne twister isn't cryptographically secure at all, you can imagine a casino coming up with a better game that does better than this one at taking advantage of MT-generated permutations.
tptacek 13y ago
The Mersenne Twister is not a cryptographically secure random number generator.
- bigiain 13y ago
  Does it need to be for this use-case? As a way of "cutting the deck" that results in an unfeasably-computationally-large variation on the "ordinary" card deck cut (which has only 52 possible changes to the allegedly shuffled deck) - doesn't it satisfy that goal?
  - tptacek 13y ago
    I read the article closely enough to come to believe they could have used a CSPRNG but opted instead to use MT19937, considered that the title indicated that the approach was an application of cryptography, and decided to keep my response simple. MT is really, really bad. We don't see it too much in the real world, but it's so easy to attack that we have several attacks on it in our crypto challenges.
    - bigiain 13y ago
      Have you got any links or keywords I can search about MT's vulnerabilities? I wonder if those vulnerabilities are exploitable given the seeding construct they chose? seed = SHA256(client_seed + server_seed) % 2 ^ 32
      - tptacek 13y ago
        It takes a tiny amount of entropy as its input and its internal state is recoverable from its outputs.
        bigiain 13y ago
        Yeah, but it's "internal state" is already known to the attacker here. The whole point of using it is for it's deterministic output given a pre-disclosed seed. It's only using it as a way to enumerate with of 2^32 possible reshufflings we agree to do to the deck before playing - which either of us can check at the conclusion of the game since we both knew up front the initial shuffled deck hash, the two PRNG seeds, and the order the cards came out in the game.
ChuckMcM 13y ago
Fascinating, something I've played with in my spare time for a while. As others have pointed out the Mersenne twister isn't cryptographically secure so in this case you can attack the shuffle by attacking the PRNG. However it is an interesting cryptography problem to create an ordered sequence of tokens where nobody trusts anyone else to pick the order. To be really useful in cards you would want some other functions too of course.
- ryan-c 13y ago
  https://en.wikipedia.org/wiki/Mental_poker https://en.wikipedia.org/wiki/Mental_poker
  - ChuckMcM 13y ago
    Awesome it has a friggin' name even. Wow, tracking down some of those references.
andrewcooke 13y ago
hmmm. what this really does is allow "unsafe" validation to be postponed until after the deck is used, when it no longer matters that the validation is unsafe. which i guess is fair enough, but i was expecting some kind of homomorphic solution and/or a zero knowledge proof. anyone have a solution that meets my finicky expectations?
- lann 13y ago
  Even better: it is possible for N players to fairly (safe from N-1 collusion) shuffle a deck with no central authority. The magic Google words are "mental poker". As you guessed, it involves homomorphic (or at least commutative) crypto.
ryan-c 13y ago
I wrote this a a few months back: https://github.com/ryancdotorg/libtprpg https://github.com/ryancdotorg/libtprpg (do note the disclaimer in the README) It's particularly good for blackjack using multiple decks (that implementation should be able to generate all possible permutations of up to four decks, not that the universe will exist long enough to do it) because it requires no computation ahead of time, only when cards are dealt. I got the idea from this article: http://blog.notdot.net/2007/9/Damn-Cool-Algorithms-Part-2-Secure-permutations-with-block-ciphers http://blog.notdot.net/2007/9/Damn-Cool-Algorithms-Part-2-Se... see also http://www.cs.ucdavis.edu/~rogaway/papers/subset.pdf http://www.cs.ucdavis.edu/~rogaway/papers/subset.pdf
chowells 13y ago
They should just have the client send the server a full permutation. It's just an array of 52 numbers, quick to verify, quick to execute. It also has the full range of 52! permutations, meaning no matter what permutation the server generates, the client can change it to any other permutation. That's the property you really want, in order to trust this.

19 points by tlrobinson 13y ago

I'm no crypto expert, but their use of Mersenne Twisters and 32 bit seeds seems suspect to me. In theory couldn't the casino compute all 2^32 possible seeds for a bunch of server seeds, and select the ones that are biased in their favor?

kedean 13y ago
They mention that they first do enough shuffling to cover all possibilities of the deck, then apply the seeded shuffling.
- sirclueless 13y ago
  The "enough shuffling to cover all possibilities of the deck" is a server-side-only operation. It's not verified at all, they could replace a pre-shuffled deck with a carefully chosen one if they liked.
advisedwang 13y ago
Essentially yes. As with the shuffle-and-cut example the server can constrain the possible choices. However this seems to be an impractical as this requires an astronomical amount of effort - the server would need to run through all 2^32 shuffles from the deck they pick just to see if that deck was favourable. This would be exceedingly rare, so a vast number of shuffles must be tested in this manner.
- sirclueless 13y ago
  You don't have to do it for every deck. You can work backwards from a desirable end result. For example, here's a really dumb formula to do a tiny bit better than random: The game is "Black or red," where the top card of the deck is revealed. If it is black (clubs or spades), you win. If it is red (hearts or diamonds), the casino wins. The casino can cheat as follows: It generates all 2^32 possible Mersenne "cuts" of the deck. Then it finds those card positions which, through random chance, are shuffled to the top slightly more often by the Mersenne cut process. Then it chooses a deck to reveal as the "shuffled" deck at the beginning with a disproportionately large number of red cards in those locations. Since they will get cut to the top more than 50% of the time, the casino can do more than break even. The law of large numbers and the fact that MT19937 is a decent PRNG that passes an awful lot of randomness tests says that the chance of each position being "cut" to the top is almost exactly 1/52. So the casino isn't going to do much better than 50% on this game. But the Mersenne twister isn't cryptographically secure at all, you can imagine a casino coming up with a better game that does better than this one at taking advantage of MT-generated permutations.

tptacek 13y ago

The Mersenne Twister is not a cryptographically secure random number generator.

bigiain 13y ago
Does it need to be for this use-case? As a way of "cutting the deck" that results in an unfeasably-computationally-large variation on the "ordinary" card deck cut (which has only 52 possible changes to the allegedly shuffled deck) - doesn't it satisfy that goal?
- tptacek 13y ago
  I read the article closely enough to come to believe they could have used a CSPRNG but opted instead to use MT19937, considered that the title indicated that the approach was an application of cryptography, and decided to keep my response simple. MT is really, really bad. We don't see it too much in the real world, but it's so easy to attack that we have several attacks on it in our crypto challenges.
  - bigiain 13y ago
    Have you got any links or keywords I can search about MT's vulnerabilities? I wonder if those vulnerabilities are exploitable given the seeding construct they chose? seed = SHA256(client_seed + server_seed) % 2 ^ 32
    - tptacek 13y ago
      It takes a tiny amount of entropy as its input and its internal state is recoverable from its outputs.
      - bigiain 13y ago
        Yeah, but it's "internal state" is already known to the attacker here. The whole point of using it is for it's deterministic output given a pre-disclosed seed. It's only using it as a way to enumerate with of 2^32 possible reshufflings we agree to do to the deck before playing - which either of us can check at the conclusion of the game since we both knew up front the initial shuffled deck hash, the two PRNG seeds, and the order the cards came out in the game.

ChuckMcM 13y ago

Fascinating, something I've played with in my spare time for a while. As others have pointed out the Mersenne twister isn't cryptographically secure so in this case you can attack the shuffle by attacking the PRNG. However it is an interesting cryptography problem to create an ordered sequence of tokens where nobody trusts anyone else to pick the order. To be really useful in cards you would want some other functions too of course.

ryan-c 13y ago
https://en.wikipedia.org/wiki/Mental_poker https://en.wikipedia.org/wiki/Mental_poker
- ChuckMcM 13y ago
  Awesome it has a friggin' name even. Wow, tracking down some of those references.

andrewcooke 13y ago

hmmm. what this really does is allow "unsafe" validation to be postponed until after the deck is used, when it no longer matters that the validation is unsafe. which i guess is fair enough, but i was expecting some kind of homomorphic solution and/or a zero knowledge proof. anyone have a solution that meets my finicky expectations?

lann 13y ago
Even better: it is possible for N players to fairly (safe from N-1 collusion) shuffle a deck with no central authority. The magic Google words are "mental poker". As you guessed, it involves homomorphic (or at least commutative) crypto.

ryan-c 13y ago

I wrote this a a few months back: https://github.com/ryancdotorg/libtprpg https://github.com/ryancdotorg/libtprpg (do note the disclaimer in the README) It's particularly good for blackjack using multiple decks (that implementation should be able to generate all possible permutations of up to four decks, not that the universe will exist long enough to do it) because it requires no computation ahead of time, only when cards are dealt. I got the idea from this article: http://blog.notdot.net/2007/9/Damn-Cool-Algorithms-Part-2-Secure-permutations-with-block-ciphers http://blog.notdot.net/2007/9/Damn-Cool-Algorithms-Part-2-Se... see also http://www.cs.ucdavis.edu/~rogaway/papers/subset.pdf http://www.cs.ucdavis.edu/~rogaway/papers/subset.pdf

chowells 13y ago

They should just have the client send the server a full permutation. It's just an array of 52 numbers, quick to verify, quick to execute. It also has the full range of 52! permutations, meaning no matter what permutation the server generates, the client can change it to any other permutation. That's the property you really want, in order to trust this.