Provably Fair Shuffling Through Cryptography (2012) | Hacker News Reader

Provably Fair Shuffling Through Cryptography (2012)

techblog.bitzino.com

19 pointstlrobinson26 comments

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

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?

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.

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

It takes a tiny amount of entropy as its input and its internal state is recoverable from its outputs.

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.

Agreed. The only way I can see for either party to cheat would be for the casino precompute a large number of shuffled decks along with the output after all 2^32 possible MT seeds and use shuffles that give the house an additional statistical edge, but I can't see this getting a large enough edge to be worth the trouble.

So I went looking myself - it seems a big problem with MT is that it's "easy" to determone the seed from a sample of generated "random" numbers. I don't think that's a problem here, since the "casino" end knows the seed anyway.

I _think_ to attack this you would need to do two seemingly difficult things. 1) come up with a seed which generates a sequence from the prng which allows a shuffle to create a favourable-to-you deck - this might be doable given my very quick reading of MT's weaknesses. But then you need to do 2) create a server_seed such that PRNGseed = SHA256(client_seed + server_seed) % 2 ^ 32. I suspect that's "hard". (I don't know if SHA256 is vulnerable to extension attacks the way MD5 is - I don't _thin_ so, but even if it were, some simple "plausibility checks" on the alleged server_seed would protect against that.)

I guess there's a problem if the client_seed ad server_seed ever get re-used - but that's a common crypto in-use issure, right? Just don't do that...

Why do you care about attacks on SHA? It's a 32 bit seed.

Yeah - in retrospect I was confusing myself there.

I still think this works though. Unless there is a way for them to chose a server_seed such that:

SHA256(server_seed + client_seed) % 2 ^ 32 = PRNG_seed(favourable to them)

without my choice of client_seed messing up their desired PRNG_seed.

Two generation of Pokemon games were plagued by people who figured out how to reverse the random number generator, and could make the game do exactly what they want. I think it was a MT generator, but it's been a while since I played with it -- the search space was small enough that a decent desktop could search the space in less than a minute.

I'm also unsure whether their usage of MT is actually a problem. The small seed size is what seems like a problem to me.

They note they're actually reshuffling, not just cutting the deck, but even then there are only 2^32 possible seeds and thus 2^32 possible reshuffles. What's stopping them from pregenerating server seeds that are biased in their favor? Maybe using MT makes that even easier.

I don't think that works - they have to tell me their server_seed before I tell them my client_seed. That makes the PRNG seed dependent on the SHA256 hash of something out of their control.

I think tlrobinson means seed decks, not server_seeds as used in the generation of the MT seed.

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.

https://en.wikipedia.org/wiki/Mental_poker

Awesome it has a friggin' name even. Wow, tracking down some of those references.

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.

I wrote this a a few months back:

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-Se...

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?

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.

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?

They mention that they first do enough shuffling to cover all possibilities of the deck, then apply the seeded shuffling.

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.

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.

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.

Reply on news.ycombinator.com