Topic: Beware bitZino shuffling algorithm leaves much to be desired... (Read 8641 times)

Standard integer-to-permutation algorithm, applied to large integers.

uint256 Shuffle = rand256();
int deck[52];

for (count = 0; count < 52; count++) deck[count] = count;
for (count = 52; count > 0; count--){
  swap(deck[count-1], deck[Shuffle % count]);
  Shuffle /= count;
}

How do you shuffle a deck of cards (52 cards) with 256 bits? I'm thinking a card sort ... (I have a really long method in another thread, but that's not very efficient; it does have the property of being able to reveal only some cards and not the whole deck, which is useful in poker.)

*edit* I did look up the Fisher Yates shuffle, but I'd like to know what others suggest.

The issue is that his server seed plus your client seed are combined using XOR into a 32-bit shuffle seed.

It doesn't matter who picks what, or whether you know his server seed or whether he knows your client seed.  The issue is that there are only 4 billion possible shuffles.

If you can see five to seven cards, and you know the sequence in which those cards came off the deck, then you know which of those 4 billion shuffles it was.  And therefore what all the other cards (the ones you "can't see") are too. 

This is the fallout from 'Oh crap they can't do math.' 

That is, either they *Really* can't do math, and you can rob them blind because you know what all the face-down cards are - or they're *pretending* they can't do math while they rob all the players blind because they know what all the face-down cards are.

In this case, they came up with a protocol that allows people to 'verify' that the shuffle was "fair" in terms of having both sides pick a seed and having both seeds used in the shuffle.  But 'oh crap they can't do math' because the combined seed was only 32 bits long (4 billion possible shuffles) instead of ~250 bits (same number of possible shuffles as with a real card deck.  The result is that the protocol isn't badly incorrect but because of the implementation it doesn't matter because the game is still unfair.

I don't understand.

How many 4 billion entry lookup tables does he need? What's the key? What's the value? How does he use it?

You understand he picks the server seed *before* you pick the client seed, right? And once he has done it, that's all his choices used up. He doesn't get to change anything once you have picked your client seed.

The only scope for cheating I see is that he could pick a server seed which does badly on average against all 4 billion client seeds, but that's a different concern. You seem hung up on the "initial shuffle" part. Would you still think he was cheating if the client seed was 256 bits instead of 32 bits?

I'm really annoyed with all of you and everyone discussing this issue on other sites like reddit.

How can you all be so daft? He admits, and I quote: "The other difference is that rather than shuffling a fresh deck, we shuffle the deck once on the server first (the initial_shuffle)."

Are you guys seriously so computer science stupid as to not see how that is more or less proof that he is cheating people. If not, it's at the very least a 100% proof that the algorithm is not "provably fair"

He does an initial shuffle.

Think it over.

Never mind. If I'm the only one who figured this out then I probably need to explain it.

You have your client and server seeds that combine to do a shuffle. That's all perfectly above board. He sends you a hash of the server's seed from the start so you can verify it when he gives it to you later. And you can monitor your client side seed, set it manually, or just check that fair jvs is running for the generation.

But HE DOES AN INITIAL SHUFFLE. HE FREAKING ADMITTED IT RIGHT THERE MY GOD

I called him out on this and he INSTANTLY stopped defending his site on reddit. He was responding to all comments with such haughtiness and faux pride and as soon as someone was smart enough to see through his shit, he vanished like a snake oil salesman as soon as you go around the corner.

All he needs is a lookup table with 4 billion entries (2^32 since the effective combined server+client shuffle seed is only 32-bits (a well kown problem since there are far more than 2^32 shuffles. fuck him. fuck him to death))

But all he needs is a 4 billion entry lookup table for each possible server+client seed and a corresponding "initial shuffle" that will benefit the server.

How did none of you see this? I don't do this for a living. I had to look up what hashing and seeds were when I read his bullshit.

He IS cheating. I didn't lose much $. About .2 bitcoins. But I was still enraged by how ridiculous the statistics were panning out. I didn't play enough hands to make any statements on the issue.

Use your heads people. He fully admitted he's cheating and he deserves to be in prison.

OK, I missed the 32-bit client seed part. That's no good.

Maybe, but I'm not even going to have read far enough to evaluate that part of their protocol. 

I'm going to get as far as "32-bit seed" and "shuffle" and go, "oh crap they can't do  math!"  and go on to someplace else.

If I were habitually looking for opportunities to cheat, I'd see "Oh crap they can't do math!" as possibly good news - and read on to figure out which of us it's empowering to cheat. 

But I'm pathologically honest, and "Oh crap they can't do math" means cheating is possible. Therefore I'm out of there, and usually assume that if somebody is putting up a site where cheating is possible that it's going to be them cheating rather than them allowing the customers to cheat.

The way that Bitzino works is that they shuffle the deck using their random seed, then the user shuffles it using theirs.

If Bitzino isn't using enough randomness to do their initial shuffle that helps the user cheat, not the site.

Suppose they only used 2 bits to do their shuffle. That means they'd only have 4 possible shuffles they could do. It would be easy for the player to find a client seed that took all 4 initial shuffles and turned it into a winning shuffle for them. The most more bits the house uses for their initial shuffle, the harder it is for the user to cheat in that way, and so it's in the user's favour if the house shuffle is insecure not the other way around.

Don't defend it silly.  Just fix it. 

Everybody knows shuffling a pack of cards takes 240 bits.  If you do it with less than 240 bits everybody knows you're cheating.  So they don't play with you, and therefore, even if you're NOT really cheating you lose money.

Everybody knows the randomness used by a game has to be the result of a bit commitment from both sides.  Therefore if your game isn't providing a bit commitment and taking one, and allowing the results to be checked to make sure that the randomness is really the result of combining the numbers committed to, everybody knows you're cheating.  So they won't play with you, and therefore even if you're NOT really cheating you lose money.

Again, it's not worth arguing about.  The only way to "win" the argument is by fixing it so that the site has the desired properties.  It isn't a matter of opinion, it's a matter of math.  Changing anyone's opinion about it won't matter because you can't change the laws of math.  It's either right or it's wrong, and if it's wrong, you can't PROVE that you aren't cheating.  So even if you aren't, everybody will assume you're cheating.  The only way to convince anyone you're not cheating is to use the math to PROVE that you aren't cheating.

I dunno how much Sergio's cards protocol has in common with my dice protocol, but what I use is that each side provides a sequence of inputs where each input is the hash of the subsequent one.  It's a cute trick where each number is also the "bit commitment" for the number that follows.  It requires that each side generate its sequence from the end to the beginning, but if you run out, you can just generate a new sequence and exchange bit commitment numbers again to continue.

- https://news.ycombinator.com/item?id=9058074

Is this a problem for bitZino users?

this was an extremely interesting read. thank you

Thanks for the feedback, Sergio. I really do appreciate it!

I believe you're right that a greasemonkey client-side script which used a CSPRNG to generate the client_seed would drastically improve the quality of the overall system, especially for users with insecure browsers. There are some talks in other threads about members of the community building this on their own, which I've offered to support. I think would be the absolute best: having a 3rd party script which verifies all hands, and stores a history of every hand played would be ideal. Before that script is built, I still hold that this system is vastly superior to most other online casinos.

libertaad: I know you´re doing your best effort to prove the game is fair, but using math.Random() you are proving nothing. I would be the same as skipping the client_seed stuff and telling the users to trust you because you´re good person or had no complains in the past. Either you provide a secure system or your efforts are worthless. If you want to convince your users there are plenty of companies that audit the PRNGs like iTech Labs. , eCOGRA, etc.

It seems that with little additional effort (providing client-side user programmed scripts to choose the client_seed) you could still take advantage of current developed system and secure it.

best regards, Sergio

                                                                                                                                                                                                                                                                                                                                                                                                                                                               

Fortunately, due to the nature if bitZino being a webapp, this already is possible! Any user is free to create a greasemonkey script which modifies the client_seed using their own randomness source. Additionally, users are free to manually enter a client_seed before every hand.

Also, as an additional measure, because the initial_shuffle is provided directly to the user after every hand, any suspicious user could easily to entropy analysis on all the hands they've played and prove whether or not the server is serving up truly random initial_shuffles.

I've not researched the subject myself, but reading other peoples research it's clearly stated that Math.Random can be predicted with high accuracy: it is seeded with the system time each time a new page or new tab is open.

From http://ifsec.blogspot.com.ar/2012/05/cross-domain-mathrandom-prediction.html:

"In Firefox, each page will have its own PRNG while in IE 8 and below each tab will have its own PRNG and the PRNG will *not* be reseeded if the page in the tab changes, even though the new page might be in another domain."

In Windows, Firefox javaScript engine calls QueryPerformanceCounter(), which provides some a few more bits of entropy (see http://mxr.mozilla.org/seamonkey/source/js/src/jsmath.c#366)

So in IE8 a single javaScript method that is executed before the user starts playing can detect the current seed before the page https://bitzino.com/blackjack loads and afterwards, the client_seed is completely useless as an entropy source. The user will never notice the fact the seed is known by the sever.

But the simplest attack in IE8 is to take some Random() values and solve the modular equations to obtain the seed. Since the PRNG (in Firefox and IE8) is a simple linear Congruential Generator (LCG) [ (state*a+b)%(2^48) ] the seed can be recovered by only knowing only two outputs !! No hidden code has to be sent to the user. Only the first two games would be "fair".
The client script itself is providing enough information for the server to cheat the user in the following games!


So, either you allow the user to supply the random via a greasemonkey script or fairness will never be guaranteed.

On the contrary, claiming fairness by using Math.Random() can be taken by the user as a a sign of hidden malicious intentions.

Best regards,
 Sergio.

Nice to meet you too!


A key reason that we went with Mersenne Twister for the reshuffle phase was because we place a lot of value on the reference implementation. We wanted an accessible reference implementation, that any of our end users could run. This meant it had to be in javascript. We didn't want to just have this awesome provably fair shuffling algorithm, but make it basically impossible for any of our end-users to truly verify anything.

We also didn't want to re-implement any PRNG's in javascript, because this would defeat the goal of having a simple reference implementation. Our reference implementation is less than 100 lines of code, but it does rely on an existing Mersenne Twister implementation.


I believe that a great way for a savvy user to do this on their own would be through a greasemonkey script. This is possible since bitZino is an HTML5 app. Since greasemonkey scripts are in javascript, the user could even use our reference implementation if they desired


bitZino actually does allow you to edit the client_seed if you so desire (you can see the interface for yourself if you'd like with a play money table at https://bitzino.com/blackjack). While it would be possible for us to send down fake javascript on occasion to generate client_seeds that favored us, we would be guaranteed to eventually be caught if we did this.

This avenue of attack could also be stopped in its tracks by the user running a greasemonkey script which always submitted their own client_seed. In this way, the user would never be depending on the javascript on the page to generate the seed for them.


We are indeed using Math.random() to generate the seed.

The source code, if you're curious (it creates a 24 character base-62 string):


Once again though, the user could utilize a greasemonkey script to create their own seed, and therefore not rely on the page javascript for security at all.

We did think about making this whole algorithm greasemonkey script from the beginning - which would have satisfied all of your issues regarding the server sending down tainted JS. The reason we chose not to do this primarily as a greasemonkey script was once again about accessibility. We wanted 100% of our users to be able to verify their hands if they chose to. I still may make a greasemonkey verifier, but I think it would actually be better if the greasemonkey verifier came from the community, rather than from us.

There are (possibly) two other problems with your protocol:

1) The origin of the code that choses the client_seed:

I haven´t seen the page, but I doubt the user can provide the random seed manually in an edit box.
If not, then the server-sended client-side javaScript code could choose the number in a predictable way, and the user has no way to find it.

A "fake" webpage could be sent with a probability of 1/10, so the user chances of finding it while reviewing the source code is low.

2) The way the client_seed random is chosen:

Again, I haven´t seen the source code of the webpage where the client_seed is chosen. (I haven´t played in your site) but I guess it has some javaScript code that calls Math.random(), which is not cryptographically secure and so it´s predictable.

How do you compute the client_seed ? You should use a CSPRNG, such as the one provided by SJCL namespace sjcl.random (I haven´t tested it myself)

Could you post the source code of the webpage where the client_seed is chosen ?

Best regards,
 Sergio.

Hi Libertaad, nice to meet you!


What you say is only partially true: since Mersenne Twister is not a Cryptographically-Strong Pseudorandom number generator (CSPRNG) there is the possibility that the possible pre-images could be computed to maximize some statistical properties of the Mersenne Twister output. The advantage might be subtle, but it could be done, in theory.
My suggestion is to use a client_seed much longer (say 80 bits) and a CSPRNG.


You are right. But you should tell the user not to accept reloads with changing hashes.


Great! But the problem is that the user has to manually check the shuffles every time. There should be a way to automate the checks, but in a way the the checking code is not sent by the server, but given by the user. An interfase between the web page and a local application.

It was my pleasure.

The protocol was improved since the thesis.. performance is 10x faster now. These improvements are described in a US patent ...

My implementation is not ready to go open source, and must be cleaned up. Also there is the patent issue, so I must find a license compatible with the patent. I will publish the code soon.

Hi Sergio! I'm the owner and primary developer of bitZino. Thanks for the feedback! I relish the opportunity to defend our approach to shuffling as truly Provably Fair. I firmly believe that the best cryptography is that which is practiced in the open, with honest and open discussion about any possible weaknesses or avenues of attack.

I believe that the blog post you linked to has a pretty good discussion about most of your points, but I'll take the time to individually address all of your critiques:


The client_seed is only used to reshuffle the deck, so it's not necessary to use it to be able to represent the full set of possible decks. In effect, the reshuffling is like cutting the deck, but significantly more robust. Even if the server could analyze all possible deck combinations before each shuffle, it wouldn't help. This is because the Mersenne Twister has the property of having a Uniform Distribution, which means the avenue of attack of "creating a pre-shuffled deck such that all possible re-shuffled decks still favor the house" is impossible.


Even if there is a server error prior to the deal, the user can still confirm that the server didn't change the pre-shuffled deck - as long as the `Hash(secret)` which is presented to the user doesn't change when the user reloads the page, they will know the server is being honest. I do agree though, that if the `Hash(secret)` changes,  this would be a clear indication that the house is cheating.


The code for the Javascript Hand Verifier is indeed open source! If you view the source for that page, you will see the algorithm implemented in 100 lined of clean, well-commented javascript. If you don't trust the javascript though, you are free to re-implement your own verifier - that's why I created the detailed blog post as well as the reference javascript implementation - I want to be as open about this whole process as possible.


Ok, I admit there is no rigorous mathematical proof to accompany the algorithm - but that's why it's not "Proven" - it's just "Provable".  I do believe a rigorous mathematical proof could accompany this, and prove that it would be NP hard to cheat a user at dealing if this algorithm is followed. You could say it's just in the theory stage right now



A link to the wikipedia Mental Poker page, for the lazy I'm a big fan of these types of approaches, and the general guiding principal is what drove me to make bitZino provably fair. But, I disagree on your assessment that MP is the only way to have a secure game. MP is great for situations when neither player can know the shuffle of the deck. But in a casino game's use case, it is not a problem for the house to know the shuffle - as long as it doesn't know the shuffle until the moment the game is dealt (again, assuming that `Hash(secret)` doesn't change in the event of an error - which would be a clear indication that the house is cheating).

Thanks again for the critique! I truly do love how the bitcoin community embraces cryptographic approaches to solve real-world problems, and I also love how it's rigorous in its critique of systems that aren't truly secure. Please, bring on any more critiques you have, I'd love to continue the discussion!