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

[JackpotRacer]

I guess that could work.

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.

please let me state that I have no clue about the provably fair option and I see more and more that it is anyway not an easy task.

my point of view is that we as  casino owners don't want to cheat the players and don't want to be cheated by players. therefore I asked for the perfect way or best solution to offer a provably fair card game like BJ, Baccarat, Poker etc?

NLNico mentioned now that it could be like unique dice results and I am not sure if I understand this because BJ or Baccarat is played with 6 or 8 decks (reshuffled after each game) and up to 10 + cards could be dealt in a game. real BJ and Baccarat players are interested in the cards they get dealt and not in dice decisions. my question is if it would be like provably fair shuffled 6 or 8 decks?

sorry for my english and I hope you could understand my question

thx

[1714605796]

1714605796

[RHavar]

Nice work! But I think you're missing out the most interesting part, in a game of X how much can this exploit raise the house?


Also regarding the exploit, this type of attack was first noticed a while ago (although in the context of bustabit):
https://bitcointalk.org/index.php?topic=709185.msg8535291#msg8535291 who was able to raise the house edge by 0.2%.

Anyway, I ended up solving by mixing in the hash of a yet-unmined bitcoin
block (see: https://www.bustabit.com/faq#fair).

[RHavar]

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.

I don't think that's a great idea. You're better off by creating a random number stream like this:

Code:

function* randomNumberGeneration(seedShit) {
    for (var nonce = 0; true ; ++nonce) {
         yield sha256(seedShit + '|' + nonce) % amountOfCardsInADeck; // using bigint maths..
    }
}

(i.e. something along the lines of how dice sites currently generate outcomes.) The modulo-bias is so insigificant, that you could run it for a billion years and not hit a case of it. Anyway, instead of assigning a random number to each card and sorting you're better off sticking with a Fisher–Yates shuffle, which is proven to be perfect with no bias. (Which is a fancy way of saying, you loop through the deck of cards and for each card you generate a random index. Then you SWAP the current card, with the one at that index. And continue on your loop. Once you get to the end of the loop, you're guaranteed to have perfectly shuffled it.

The psuedo code from wikipedia:

Code:

-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

[TrevorXavier]

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

Thank you!

It's more than that. I'm claiming that the shuffle-based games are actually not provably fair. This is a direct attack against the algorithm.

Here's why:

• On a mid-range CPU (like a Core i5), a casino can calculate a single arrangement in about 17 hours.
• Since it is not looking for the "ultimate" arrangement (just a better one), it can continuously search one arrangement at a time and update its "master list" of cold decks that result in a higher house edge.
• These deck arrangements, over time, will always perform better.

I have written a new implementation that I will share here soon. I won't go so far as to say that it is "perfect" (since there is no perfect crypto), but maybe "next generation"?

[TrevorXavier]

Nice work! But I think you're missing out the most interesting part, in a game of X how much can this exploit raise the house?

Thanks! More results to follow. The code is in the wild, I suspect someone will rewrite it to conform to the reference implementation. I'll reveal the arrangements I found and the raised house edge here soon. Since they're "drop in" exploits, a casino can deploy them immediately, and I don't want to be the direct cause of players getting cheated.

I actually did hit the modulo bias quite often, since I'm searching the entire space. I think it's silly that bitZino even had a modulo bias. It's a casino. Quick and easy fix:

Adapted from (https://stackoverflow.com/questions/10984974/why-do-people-say-there-is-modulo-bias-when-using-a-random-number-generator)

Code:

const RAND_MAX = 0xFFFFFFFF

function random() {
  let x
  do {
    x = rand_int32() // use crypto.randomValues or something tied to a csprng
  } while (x >= (RAND_MAX - RAND_MAX % n))

  return x % n
}

A player may actually hit the modulo bias quite often for some games, such as blackjack, since it requires 314 random numbers per round of 8-deck. The Fisher-Yates shuffle actually requires a uniform random distribution to result in non-biased shuffles. An extreme example: shuffle a deck but always use the number 5 as the random number.

[serje]

Can you give us a list of casinos that use bitzeno?
I think it would be helpful

Thankd

[casinobitco]

Agreed Stunna... All players should change the client-seed when offered, and not trust the casino's version of it; regardless if they've been around forever (like Bitzino or PrimeDice), or been around since 2013 (Us).

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

[JackpotRacer]

Agreed Stunna... All players should change the client-seed when offered, and not trust the casino's version of it; regardless if they've been around forever (like Bitzino or PrimeDice), or been around since 2013 (Us).

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

did I miss the point the OP did or you? I understood that OP said that even you change the client seed the casino has an advantage (if they want) in card games like BJ or Baccarat

[Lutpin]

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?

Kinda like Crypto-Games.net does?

[TrevorXavier]

Agreed Stunna... All players should change the client-seed when offered, and not trust the casino's version of it; regardless if they've been around forever (like Bitzino or PrimeDice), or been around since 2013 (Us).

did I miss the point the OP did or you? I understood that OP said that even you change the client seed the casino has an advantage (if they want) in card games like BJ or Baccarat

You're right, JackpotRacer, the exploit works regardless of client seed. You could change the client seed every time with random data; the house will still win more often than expected if it uses an optimized deck.

[JackpotRacer]

Agreed Stunna... All players should change the client-seed when offered, and not trust the casino's version of it; regardless if they've been around forever (like Bitzino or PrimeDice), or been around since 2013 (Us).

did I miss the point the OP did or you? I understood that OP said that even you change the client seed the casino has an advantage (if they want) in card games like BJ or Baccarat

You're right, JackpotRacer, the exploit works regardless of client seed. You could change the client seed every time with random data; the house will still win more often than expected if it uses an optimized deck.

thx for confirming it but to be frank I am not happy about your findings because players could stay away from those popular card games

[TrevorXavier]

thx for confirming it but to be frank I am not happy about your findings because players could stay away from those popular card games

You're welcome! It's natural for any cryptographic mechanism to show weaknesses over time. They (almost never) get stronger. Eventually, they are replaced with modern versions, which I think will happen here as well.

If I were a card player, I would rather know that an exploit exists than not know and be silently cheated out of my coins.

[casinobitco]

Agreed Stunna... All players should change the client-seed when offered, and not trust the casino's version of it; regardless if they've been around forever (like Bitzino or PrimeDice), or been around since 2013 (Us).

did I miss the point the OP did or you? I understood that OP said that even you change the client seed the casino has an advantage (if they want) in card games like BJ or Baccarat

You're right, JackpotRacer, the exploit works regardless of client seed. You could change the client seed every time with random data; the house will still win more often than expected if it uses an optimized deck.

I'd love to see some working examples of a 'rigged deck' in blackjack, baccarat, roulette, whatever - where the client seed has no effect on the end shuffle using Provably Fair Shuffle.

[JackpotRacer]

thx for confirming it but to be frank I am not happy about your findings because players could stay away from those popular card games

You're welcome! It's natural for any cryptographic mechanism to show weaknesses over time. They (almost never) get stronger. Eventually, they are replaced with modern versions, which I think will happen here as well.

If I were a card player, I would rather know that an exploit exists than not know and be silently cheated out of my coins.

I fully agree with you that a player needs to know if any exploit exists and decide himself to play at those casinos or not

thx again for your very interesting findings

[TrevorXavier]

I'd love to see some examples of a 'rigged deck' in blackjack, baccarat, roulette, whatever - where the client seed has no effect on the end shuffle using Provably Fair Shuffle.

I'm intentionally waiting on this for a bit until players become aware of the exploit. If I were to drop the optimized decks right now, they could immediately be used to cheat players.

You can generate your own non-reference decks using the code I provided. Simply let it run. On a single-core machine, it takes less than a day to scroll through an arrangement. A few tweaks and you can go multithreaded and cut the time down significantly. For reference decks, you'll have to rewrite parts of it to conform to the target casino.

In roulette, for example, you will receive a deck arrangement and a number. The number corresponds to how many seeds were beaten. If the number exceeds the expected probability of the draw, then it is a partially-optimized deck.

[dothebeats]

thx for confirming it but to be frank I am not happy about your findings because players could stay away from those popular card games

You're welcome! It's natural for any cryptographic mechanism to show weaknesses over time. They (almost never) get stronger. Eventually, they are replaced with modern versions, which I think will happen here as well.

If I were a card player, I would rather know that an exploit exists than not know and be silently cheated out of my coins.

The last line of your (trevor) post hit me big. From the start, I don't really like playing shuffle-based games (like baccarat, card games or the likes), as I thought that they can be somewhat rigged. Well, turns out that I'm right on my thoughts after all, but with that I'd like to see a video demo of the exploit as "provably fair" casinos seemed to not be fair at all.

[TrevorXavier]

The last line of your (trevor) post hit me big. From the start, I don't really like playing shuffle-based games (like baccarat, card games or the likes), as I thought that they can be somewhat rigged. Well, turns out that I'm right on my thoughts after all, but with that I'd like to see a video demo of the exploit as "provably fair" casinos seemed to not be fair at all.

Thanks for the feedback!

I thought about doing a video, but didn't really know if it would cultivate interest. I'll rethink the idea. Might be nice seeing the exploit visually.

[casinobitco]

The last line of your (trevor) post hit me big. From the start, I don't really like playing shuffle-based games (like baccarat, card games or the likes), as I thought that they can be somewhat rigged. Well, turns out that I'm right on my thoughts after all, but with that I'd like to see a video demo of the exploit as "provably fair" casinos seemed to not be fair at all.

Thanks for the feedback!

I thought about doing a video, but didn't really know if it would cultivate interest. I'll rethink the idea. Might be nice seeing the exploit visually.

I think that would be extremely valuable... also, how would a 'rigged casino' account for games that have unexpected customer behaviors? Like hitting or staying in Blackjack, or going randomly red / black in roulette?

Not discounting what you're saying technically, but I just don't see how a rigged casino could account for these variables.

[TrevorXavier]

I think that would be extremely valuable... also, how would a 'rigged casino' account for games that have unexpected customer behaviors? Like hitting or staying in Blackjack, or going randomly red / black in roulette?

Not discounting what you're saying technically, but I just don't see how a rigged casino could account for these variables.

Yes, so that's part of the heuristic I mentioned earlier. There are games, such as roulette, which require play history. However, there are others, such as blackjack, that are exclusive. The exploit works regardless. In addition, you don't really need to account for 'strange' plays, as the goal is to reduce favorable cards for the player, or encourage favorable cards for the dealer. Since the dealer doesn't play strangely, the exploit works. Here's a brief overview:

Roulette

• Optimizations: favor one color over another; favor thirds; favor number; reduce instance of number, color, or third.
• Heuristic: Brute-force. The arrangement space is computationally feasible.
• Deployment: Requires at least one game played to stack decks.

Blackjack

• Optimizations: player receives bust hand (13-16); deny player ace; house starts with 10, Ace, or non-bust card; reduce splitting; reduce doubling; reduce dealer busts, and more
• Heuristic: Create translation decks using the seed space. Since most blackjack games average 6-7 cards total dealt, attempt to optimize by best-fit.
• Deployment: Mutually-exclusive. Exploit works regardless of prior play.

For blackjack, you're not necessarily attempting to combat random play (random hits, random doubles), but rather, encourage favorable cards to the dealer and encourage bad cards for the player. So, you're looking for arrangements that give the dealer an Ace more often than not, give the player a 6, reduce the likelihood of splitting, doubling, and so on. Beyond that, you'd want to allow for the house to make their hand (try to keep a slug of low cards beyond the 7th position of the final deck, etc.). You can also optimize to combat basic strategy and 'upgrade' the cold decks when prior play history suggests the player is playing this way.

Blackjack works due to the extremely large arrangement space. You're talking 416! / 128! / (32!)⁹ possible arrangements in an 8-deck game. Since your target is only 2³², that means you need to find an arrangement that works well against the 2³² / (416! / 128! / (32!)⁹) shuffles in the final space. The number is so small that most calculators can't even represent it. It's possible there exists an arrangement that beats all possible seeds.


Video Poker

• Optimizations: encourage dead hands for the first 10 cards; reduce royal flush, straight flush, and so on; allow for good primary hands (like four to a straight flush), but deny matching card, and more
• Heuristic: Create translation decks using the seed space. Reduce translations to first 10 cards and attempt a best-fit optimization.
• Deployment: Mutually-exclusive. Exploit works regardless of prior play.

This is just a partial list. I'll elaborate more when I publish the optimized decks. This is pretty much where I started when I attacked the problem.

Addendum: Also, remember, the goal of shufflepuff is to not discover the uber-optimized deck, just ones that perform better than others. So, a casino operator performing a random search would probably do well in the short term with shufflepuff vs. hiring a mathematician to construct a heuristic.

[casinobitco]

Yea, makes total sense...

And sorry I'm skeptical, I guess I'm just being dense here, but would love to see a video show that you can produce such kind of rigged decks with a truly random client seed with 100% success.

Example - Blackjack
You want to show the dealer always gets a "20" with first 2 cards. Using provably fair shuffle, and ANY client seed you can achieve that repeatedly?

I think that would be extremely valuable... also, how would a 'rigged casino' account for games that have unexpected customer behaviors? Like hitting or staying in Blackjack, or going randomly red / black in roulette?

Not discounting what you're saying technically, but I just don't see how a rigged casino could account for these variables.

Yes, so that's part of the heuristic I mentioned earlier. There are games, such as roulette, which require play history. However, there are others, such as blackjack, that are exclusive. The exploit works regardless. In addition, you don't really need to account for 'strange' plays, as the goal is to reduce favorable cards for the player, or encourage favorable cards for the dealer. Since the dealer doesn't play strangely, the exploit works. Here's a brief overview:

Roulette

• Optimizations: favor one color over another; favor thirds; favor number; reduce instance of number, color, or third.
• Heuristic: Brute-force. The arrangement space is computationally feasible.
• Deployment: Requires at least one game played to stack decks.

Blackjack

• Optimizations: player receives bust hand (13-16); deny player ace; house starts with 10, Ace, or non-bust card; reduce splitting; reduce doubling; reduce dealer busts, and more
• Heuristic: Create translation decks using the seed space. Since most blackjack games average 6-7 cards total dealt, attempt to optimize by best-fit.
• Deployment: Mutually-exclusive. Exploit works regardless of prior play.

For blackjack, you're not necessarily attempting to combat random play (random hits, random doubles), but rather, encourage favorable cards to the dealer and encourage bad cards for the player. So, you're looking for arrangements that give the dealer an Ace more often than not, give the player a 6, reduce the likelihood of splitting, doubling, and so on. Beyond that, you'd want to allow for the house to make their hand (try to keep a slug of low cards beyond the 7th position of the final deck, etc.). You can also optimize to combat basic strategy and 'upgrade' the cold decks when prior play history suggests the player is playing this way.

Blackjack works due to the extremely large arrangement space. You're talking 416! / 128! / (32!)⁹ possible arrangements in an 8-deck game. Since your target is only 2³², that means you need to find an arrangement that works well against the 2³² / (416! / 128! / (32!)⁹) shuffles in the final space. The number is so small that most calculators can't even represent it. It's possible there exists an arrangement that beats all possible seeds.


Video Poker

• Optimizations: encourage dead hands for the first 10 cards; reduce royal flush, straight flush, and so on; allow for good primary hands (like four to a straight flush), but deny matching card, and more
• Heuristic: Create translation decks using the seed space. Reduce translations to first 10 cards and attempt a best-fit optimization.
• Deployment: Mutually-exclusive. Exploit works regardless of prior play.

This is just a partial list. I'll elaborate more when I publish the optimized decks. This is pretty much where I started when I attacked the problem.

Addendum: Also, remember, the goal of shufflepuff is to not discover the uber-optimized deck, just ones that perform better than others. So, a casino operator performing a random search would probably do well in the short term with shufflepuff vs. hiring a mathematician to construct a heuristic.