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

(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 
#include 
#include 

typedef std::vector 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://bitcointalksearch.org/topic/m.15071925)

Topic: Breaking: Shuffle-based Provably Fair Implementations Can Cheat Players (proof) - page 6. (Read 4659 times)