Breaking: Shuffle-based Provably Fair Implementations Can Cheat Players (proof)

[TrevorXavier]

(Due to space constraints, this is highly abridged. I'll post a more detailed analysis on GitHub with the sample and optimized code shortly.)

Any shuffle-based provably fair casino that used bitZino as a reference implementation can exploit players.

A few years ago, I published an analysis of side-channel attacks on bitZino's provably fair method. It received a warm response. Today, I present a direct attack against the method. I call it "shufflepuff" — a tool a casino can use to optimize decks against players, effectively creating cold decks.

There are many recent, modern casinos that can deploy this exploit.

Here are the claims:

• Casinos can choose initial decks that perform strictly better against other initial decks, regardless of any Mersenne Twister seed.
• The result of the game is verifiably "provably fair" without compromising any code.
• The exploit can permanently alter the house edge of the game beyond expected outcomes.
• Due to the large arrangement space, the exploit is effectively undetectable. At the very least, refutable.

Woah. Pretty strong claims, eh? I'll explain it in a little more detail. But I'll assume you're familiar with how this provably fair method works. Please see bitZino's if you need a refresher (https://bitzino.com/about/fair). This attack applies to any casino that derives its method in a similar fashion.

You, as a player, have no ability to determine the actual Mersenne Twister seed. You can influence it, but the final seed is indirectly attributed to your client seed. However, the casino is free to determine the initial shuffle. It can be whatever they want. There is no guarantee that this shuffle (we'll call it initial deck from now on) is in any way random, and this is where the exploit begins.

In a nutshell, the house knows that the final shuffle will be one of 2³² possible shuffles. Since the initial deck space can be astronomically larger than the final shuffle space, the house simply needs to find an initial deck that performs well against as many final shuffles as possible.

How do we determine the optimized, stacked decks?

Let's try roulette, since it has the smallest search space. In the real world, it's a wheel game, but casinos like bitZino treat it like a card game nonetheless.

• First, we degenerate the deck into point-values based on the outcome we want. For example, if we want to optimize the deck for red, we convert all the red cards to +1 and the rest (including green) to 0.
• We arrange the point deck in lexicographic (sorted) order: { 0000000000000000000111111111111111111 }.
• For all permutations (without repetition), perform a Fisher-Yates or Durstenfeld shuffle with all possible Mersenne Twister seeds (which range from 0 to 2³² – 1). Add the first value of the shuffle to the rolling count.
• Compare two permutations. If one has a higher count than the other, it is strictly better than the other. Meaning, a casino can use it to permanently alter the house edge.

Shufflepuff Code (C++)

Code:

#include <iostream>
#include <algorithm>
#include <random>

typedef std::vector<int> deck_t;

int evaluator(deck_t deck, const unsigned int& seed) {
  std::mt19937 engine(seed);
  std::shuffle(deck.begin(), deck.end(), engine);
  return deck[0];
}

int main() {
  deck_t deck { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 };
  std::sort(deck.begin(), deck.end());

  // Decrease this number to see the tool in action. Results are not evidentiary unless space is 2^32 -1.
  const unsigned int SEED_SPACE = 4294967295;

  unsigned int i = 0;
  unsigned int count = 0;
  unsigned int highest = 0;
  do {
    count = 0;


    for (i = 0; i <= SEED_SPACE; ++i) {
      count += evaluator(deck, i);
    }

    if (count > highest) {
      highest = count;
      for (auto const& c : deck) std::cout << c;
      std::cout << ": " << highest << std::endl;
    }
  } while(std::next_permutation(deck.begin(), deck.end()));
  return 0;
}

// Run: clang++ -std=c++11 main.cpp
// Then: ./a.out

Things to Note

• This is a proof-of concept and intentionally different than bitZino. It is not a direct one-to-one implementation, so you will need to modify it to discover actual optimized shuffles. After some time has passed (to spread the word), I'll post the optimized arrangements I found that will work as a "drop-in" exploit for bitZino and others.
• The program will output the permutation and the number of seeds that it beat. Divide the number of seeds beaten by the seed space (plus 1) to get the probability of a win. If this exceeds the theoretical expectation, then it is a partial optimized arrangement.
• This code is not optimized for speed. It will take a long time (17+ hours) to calculate a single 2³² seed space. If you want to see it in action, you can lower the SEED_SPACE (to 5000, for example) to get the idea, although the results are not valid. The code can be adapted for distributed or parallel computing.
• BitZino also suffers from a modulo bias in the way it calculates random numbers. See source (https://bitzino.com/about/fair), line 801, so the shuffle algorithm in the C++ code also needs to be hand-written to mimic this.

Implications

• Once an arrangement has been found, it can be easily masked to prevent detection. In the example, the arrangement only represents the position of red and blacks, but a casino can fill it with any red or black card, effectively producing shuffles that appear different.
• The casino presents the shuffle first, but it can learn from subsequent play. A player who consistently plays red or black (or green) can be exploited in the next round.
• A casino doesn't need to find the most optimized shuffle, just one that beats the theoretical expectation. So, a nefarious casino would collect many optimized shuffles on a rolling basis, making it effectively undetectable.
• The shuffles can be used to help you win as well. For example, the house could produce good shuffles to help dust bettors win, in the hopes they bet more (where they could then be cheated with bad shuffles for more bitcoin).

I know this is a lot to digest in the limited space I have. I tried to distill a proof and large distributed computing code into something simple, so more to come. I'll be around for a few hours to answer some questions. Thanks for reading!

Update
Added "A Provably Unfair Blueprint" in this thread. (https://bitcointalk.org/index.php?topic=1494470.msg15071925#msg15071925)

[1713434723]

1713434723

[1713434723]

1713434723

[1713434723]

1713434723

[1713434723]

1713434723

[Stunna]

Provably fair is usually only as strong as the reputation and trustworthiness of the casino. Dice isn't as vulnerable to the attack you mentioned as users can roll over/under and use unpredictable multipliers but you still raise a valid concern, any website can recognize a pattern and plant a seed that makes the player more likely to lose. That's why it's important to set your own custom seed and when re-randomizing you should write in your own seed rather than let the website hand one to you.

I call it "shufflepuff"

Witty

[TrevorXavier]

Hi Stunna! Thanks for the reply.

You're right, the post excludes dice sites.

For other casinos, however, there is no amount of randomization that the player can do to prevent the attack. Even entering their own seed won't help. The optimized shuffle will win more often than expected.

A quick example of roulette using a pretend seed space of 5000 (0 - 4999) and running the code:

0000000000000000001111111111111111111: 2561
0000000000000000011111111111101111111: 2562
0000000000000000100111111111111111111: 2590
0000000000000000101111110111111111111: 2599
0000000000000000101111111101111111111: 2605
0000000000000000101111111111101111111: 2611
0000000000000001101111110111101111111: 2613
0000000000000001101111111101101111111: 2619
0000000000000001101111111111100111111: 2623
0000000000000010101111110111101111111: 2624
0000000000000010101111111101101111111: 2630
0000000000000010101111111111100111111: 2634
0000000000000011101111110111100111111: 2636
0000000000000011101111111101100111111: 2642
...
0000010111000110111110101111000011100: 2743

I stopped after a few moments. According to this setup, the probability of a win (for the house) is (19/37) = .5135. However, the last permutation wins 2743/5000, or .5486. We now have an arrangement that will always result in an average higher win rate. There is nothing the player can do (with this implementation) to overcome the optimized shuffle.

[Stunna]

Hi Stunna! Thanks for the reply.

You're right, the post excludes dice sites.

For other casinos, however, there is no amount of randomization that the player can do to prevent the attack. Even entering their own seed won't help. The optimized shuffle will win more often than expected.

Very true, with normal online casinos I think this usually isn't as much of a threat as a 5-15% edge will simply rake in tons of profit for the owners. But with many bitcoin casinos the operator can claim an ultra low edge to drag in volume but the actual edge would be multiple times that if they aren't playing fair.

Another important threat in the bitcoin space is investment based sites, there's absolutely no way to know if the owners will play against the house and steal from investors in an undetectable manner. It's this type of theft along with what you outlined in your post that are major threats to this community because the sites that do this will never get caught. I'm sure many of us have known people in real life who we could trust in a room with a million dollars and a video camera and they wouldn't touch a single bill, but when you remove the camera from the equation you'd often get a different result.

[NLNico]

Pretty interesting

I always dislike those complicated shuffle-based provably fair methods anyway. For roulette/slots/whatever it should be easy to just use the "normal dice nonce method" and generate numbers/results based on that, right?


Ps, there is actually one dice site "pocketdice" that uses "initial random numbers" which was proven to have a bad provably fair implementation (for more simple reasons than OP ) Unfortunately they still didn't improve this.

[TrevorXavier]

But with many bitcoin casinos the operator can claim an ultra low edge to drag in volume but the actual edge would be multiple times that if they aren't playing fair.

Totally right. You bring up another really good point. Using shufflepuff, we can feed it a truly fair roulette wheel (36 cards) playing red or black and still optimize the initial deck in a way that favors the house.

After a few minutes:

000000000000000000111111111111111111: 2496
000000000000000001111111111110111111: 2500
000000000000000010011111111111111111: 2526
000000000000000010111111011111111111: 2533
000000000000000010111111110111111111: 2538
000000000000000010111111111110111111: 2545
000000000000000011111111111110011111: 2546
000000000000000110111111110110111111: 2549
000000000000000110111111111110011111: 2553
000000000000001010111111011110111111: 2560
000000000000001010111111110110111111: 2565
000000000000001010111111111110011111: 2569
000000000000001110111111110110011111: 2573
000000000000010110111111110110011111: 2577
000000000000011010011111111110011111: 2581
000000000000011010111111010110111111: 2584
000000000000011010111111011110011111: 2588
000000000000011010111111110110011111: 2593

Anything above 2500 actually favors the house, despite the cards being in a "fair" distribution (18 red, 18 black).

Granted, advertising a 0% game would be silly and raise red flags, but an ultra-low edge would work well.

[TrevorXavier]

For roulette/slots/whatever it should be easy to just use the "normal dice nonce method" and generate numbers/results based on that, right?

Thanks!

Edit: Thought about it some more... The answer is 'not exactly' (see new reply).

[LiQuidx]

Quite interesting read. Hopefully this will spark a change in the way sites implement their provably fair schemes regarding decks shuffling but I doubt it.
Thanks for sharing your findings. 

[ndnh]

Glad I am not a fan of table games

Another important threat in the bitcoin space is investment based sites, there's absolutely no way to know if the owners will play against the house and steal from investors in an undetectable manner.

Can't agree more. I am not sure if many investors are aware of this possibility especially the ones with relatively high Profit/EV.

Ps, there is actually one dice site "pocketdice" that uses "initial random numbers" which was proven to have a bad provably fair implementation (for more simple reasons than OP ) Unfortunately they still didn't improve this.

How the system works exactly is still beyond me but I can't see the logic on the relatively complex way it is implemented or the mystery behind the 30.
But how is this?

The client's seed is not really used to generate the random result.

[Nobitcoin]

No wonder I always lost on online casinos 

[JackpotRacer]

For roulette/slots/whatever it should be easy to just use the "normal dice nonce method" and generate numbers/results based on that, right?

Thanks!

Yeah, that could work. Choosing multiple cards (i.e. blackjack) may have a couple of quirks. Roulette and slots should work fine.

this means that Black Jack, Baccarat, Poker etc are in danger to not be provably fair?

what would be the perfect provably fair implementation for those popular card games?

thx for the work you did

[RocketSingh]

I always dislike those complicated shuffle-based provably fair methods anyway. For roulette/slots/whatever it should be easy to just use the "normal dice nonce method" and generate numbers/results based on that, right?

True. Straight forward provably fairness is always better than complicated provably fairness.

[NLNico]

Ps, there is actually one dice site "pocketdice" that uses "initial random numbers" which was proven to have a bad provably fair implementation (for more simple reasons than OP ) Unfortunately they still didn't improve this.

How the system works exactly is still beyond me but I can't see the logic on the relatively complex way it is implemented or the mystery behind the 30.
But how is this?

The client's seed is not really used to generate the random result.

Pocketdice's problem is more simple. They could simply generate all 1's as "initial deck", and obviously it would be impossible for you to win if you don't bet on number 1 - no matter how random you shuffle all those 1's with your client seed


OP says that even when the distribution of numbers in the "initial deck" is fair, the outcome can still be influenced to have a slightly bigger chance to have an outcome the house prefers. This could be done by calculating what the different client seeds do with a specific initial deck.

all possible Mersenne Twister seeds (which range from 0 to 2^32 – 1)

^ I am more curious about above. BitZino allows 32 "aZ09" characters (62^32?) as clientseed and the MT seed is a SHA256 based on that. Isn't that a lot more than 2^32? Maybe I misunderstand that part though.

[BetKing.io]

Another important threat in the bitcoin space is investment based sites, there's absolutely no way to know if the owners will play against the house and steal from investors in an undetectable manner.

Can't agree more. I am not sure if many investors are aware of this possibility especially the ones with relatively high Profit/EV.

Stunna always bashes crowdfunded bitcoin casinos.

I can see why but people are smarter now and no one is investing large amounts in new sites with questionable owners who are likely to scam (Dicebitco.in and dice.ninja).
I wonder what his honest opinion is on BetKing.io/me when it comes to trust and investing.

But your argument doesn't make much.
If the Profit/EV is high then it is far less likely that the owner has been cheating the investors. If the owner was cheating then the Profit/EV would be lower.

Of the 5 Bitcoin investment sites on dicesites.com only 2 are under EV and people could accuse them of playing against investors.

People think SafeDice is legit though and is just below EV because of their risky invest model and were unlucky.

I've never trusted Bitdice so I won't go into that.

BetKing.io has a profit/ev of 140% so it strongly suggests that there is no cheating going on of investors.
Good job it's also provably fair so you can prove the house hasn't cheated players too

I've proved over and over that your funds are safer in BetKing than any other crowdfunded casino and it is a fact that it is the most trusted.
Primedice is certainly more popular but Stunna doesn't secure as many Bitcoin of other users as BetKing does at one time.
Though he may very hold more than the whole of BetKing in his own personal wallet

Moneypot looks like it might be safe to invest in as a couple of their owners (not all) are respectable members of the community, though the owners have only had it for 5 months so who knows.

SatoshiDice you would think would be safe since they have been around a long time but it seems common knowledge that they have changed owners more than a few times.

In response to OP. That is an interesting claim and I will look in to it a bit more. It would be good to see some ideas of solutions to the problem.

[TrevorXavier]

^ I am more curious about above. BitZino allows 32 "aZ09" characters (62^32?) as clientseed and the MT seed is a SHA256 based on that. Isn't that a lot more than 2^32? Maybe I misunderstand that part though.

Good catch, but sadly, the seed maxes out at 2³² – 1.

bitZino combines the server seed and client seed, hashes it with SHA256, but then only uses the first 8 bytes of it. So, the range is 0x0 to 0xFFFFFFFF. (FFFFFFFF)₁₆ = (4294967295)₁₀. They write about this in their techblog: https://techblog.bitzino.com/2012-06-30-provably-fair-shuffling-through-cryptography.html

[ajaxmoor]

BetKing.io has a profit/ev of 140% so it strongly suggests that there is no cheating going on of investors.
Good job it's also provably fair so you can prove the house hasn't cheated players too

These kinds of statements just show the immaturity of some of the casino owners. It doesn't stongly suggest anything. Any of those casinos you mentioned before could have been losing legitly. Any of those casinos could have gotten lucky and could have a positive return on ev, and could still be taking a 10% cut by playing against the investors money. Beking being 140% on profit does not suggest the fact that you could not be cheating the investors and neither would losing suggest that you are.

[NLNico]

^ I am more curious about above. BitZino allows 32 "aZ09" characters (62^32?) as clientseed and the MT seed is a SHA256 based on that. Isn't that a lot more than 2^32? Maybe I misunderstand that part though.

Good catch, but sadly, the seed maxes out at 2³² – 1.

bitZino combines the server seed and client seed, hashes it with SHA256, but then only uses the first 8 bytes of it. So, the range is 0x0 to 0xFFFFFFFF. (FFFFFFFF)₁₆ = (4294967295)₁₀. They write about this in their techblog: https://techblog.bitzino.com/2012-06-30-provably-fair-shuffling-through-cryptography.html

Ah, right. So this seems like a limitation of MT19937. So if they would use MT19937-64, would this be a sufficient solution? This is still less than 52! but at least less feasible to calculate? (I guess there is no JS code for MT19937-64 though.)

Like JackpotRacer I am wondering what "the best solution" would be to get a provably fair random card deck.

I can imagine something like the "dice nonce method" but adding an extra nonce so it could calculate more numbers (since a "duplicate card" cannot happen, so might need to loop a bit more.) But this might get a bit heavy in performance the more unique cards you need

[seuntjie]

^ I am more curious about above. BitZino allows 32 "aZ09" characters (62^32?) as clientseed and the MT seed is a SHA256 based on that. Isn't that a lot more than 2^32? Maybe I misunderstand that part though.

Good catch, but sadly, the seed maxes out at 2³² – 1.

bitZino combines the server seed and client seed, hashes it with SHA256, but then only uses the first 8 bytes of it. So, the range is 0x0 to 0xFFFFFFFF. (FFFFFFFF)₁₆ = (4294967295)₁₀. They write about this in their techblog: https://techblog.bitzino.com/2012-06-30-provably-fair-shuffling-through-cryptography.html

Ah, right. So this seems like a limitation of MT19937. So if they would use MT19937-64, would this be a sufficient solution? This is still less than 52! but at least less feasible to calculate?

Like JackpotRacer I am wondering what "the best solution" would be to get a provably fair random card deck.

I can imagine something like the "dice nonce method" but adding an extra nonce so it could calculate more numbers (since a "duplicate card" cannot happen, so might need to loop a bit more.) But this might get a bit heavy in performance the more unique cards you need

How about something like this:

PseudoCode:

Code:

list<int> UnshuffledDeck = new list<int>();
//Populate UnshuffledDeck from 1-52, where 1= ace of spades, 2=2 of spades etc etc.
list<int> shuffleddeck = new list<int>(); //empty list

string clientseed = "something"
string serverseed = "randomly generated server seed"
int nonce = 1 //or whatever your nonce should be

while (UnshuffledDeck.count>1)
{
  int tmp = UnshuffledDeck [rng(clientseed,serverseed,nonce,unsuffledeck.count)]
shuffleddeck.add(unshuffledeck[tmp])
shuffleddeck.removeat(tmp);
}
shuffleddeck.add(unshuffleddeck[0])
unshuffleddeck.removeat(0)

function int RNG(string client, string server, int nonce, int max)
{
int randomnumber =  Using a nonce based RNG system similar to Justdice or betking, generate a random number between 0 and 1 000 000.
return randomnumber%max
}

So take a "brand new" deck. Pick 1 card at random from the deck and put it at the top (or bottom) of a new deck. Continue doing this until there are no more cards left n the unruffled deck. The random card picked from the deck depends on the client seed and the nonce of the bet.
If you feel this isn't random enough, repeat the shuffle using the shuffled deck as the new unshuffled deck

[NLNico]

I guess that could work. (Potentially modulo bias though?)

You could probably also loop all 52 cards and assign random numbers to them and sort it from high to low. The random number for each card would be calculated in same like seed/nonce way (with 1 more nonce), so a bit like 52 (unique) dice results.

[rambeazle]

Wow, I have never considered this, but it makes sense.

So basically all the major casinos that offer card games are not PROVABLY fair...

I think betking is an exception, but I would love to hear from some of the other providers about how the intend to fix this situation...