15
$\begingroup$

Say a server plays a game of blackjack with a client, and the cards are shuffled and dealt by the server. The shuffle itself may or may not be fair, but what needs to be shown is that the cards dealt weren't altered during the course of gameplay, ie: after the start of the hand, the cards in the deck do not secretly have their ordering changed by the server.

I was thinking of the following solution using cryptography and wanted to gain some feedback if it would be acceptable for a production system, and if not, why not:

Step 1) The server would secretly shuffle a deck of cards in some order, say the following (we omit the suit for simplicity): [3, 9, 2, ..., A]

It would then create the following message M:
M = "Card shuffle: [3, 9, 2, ..., A]. Random number: A96A...QT3"

Random number is a random number the server internally generates and keeps secret until the game concludes. Its length would be long enough to prevent the hash being cracked by the client via brute force (let's say it's 512 characters in length).

The server would now hash M using sha-256 or some other trusted hashing algorithm, eg: hash(M)

Step 2) Before the game begins, the server sends this hash(M) to the client, which the client stores. The client has no way of knowing M from what I can gather.

Step 3) The game begins, the cards are dealt in the shuffled order, the player makes decisions, and the game finally concludes.

Step 4) The client now wants to know that the game was fair, ie: the server didn't cheat by altering the cards during the hand. The server now sends the message "M" to the client in plaintext to show this.

Step 5) The client runs hash(M) and see's that it matches its hash(M) received in step 1.

Is this a fair way to prove the game was fair, without the client or server being able to cheat, excluding the possibility that the shuffle itself wasn't random? If the server were to alter the cards from the original shuffle during the course of the hand, then the client would see this in Step 5 (either the ordering would be transparently different to the client, or the hash of the message sent in Step 4 would be different to the one sent in step 2). Also, only a single hash is sent per hand, so the server can't generate a large number of hashes and send them separately then pick the best one during the course of the hand.

$\endgroup$
8
  • $\begingroup$ What do you do if the client finds out that the initial hash and the Client-Computer Hash are not equal? $\endgroup$
    – marstato
    May 3, 2022 at 17:38
  • 1
    $\begingroup$ @marstato: Then you know the server defrauded you and (hopefully) you can file a chargeback or something. But if you used Bitcoin to pay, you might be out of luck. $\endgroup$
    – Kevin
    May 3, 2022 at 21:57
  • $\begingroup$ @Kevin you mean file a charge back with the guys that run the fraudster server? $\endgroup$
    – marstato
    May 4, 2022 at 19:00
  • 2
    $\begingroup$ @marstato I'd simply stop playing the game. The server gets a bad reputation and finds it hard to attract new clients. $\endgroup$
    – user4779
    May 5, 2022 at 1:05
  • 2
    $\begingroup$ @marstato: No, with your credit card company, just like you would with any other fraudulent transaction. I have never heard of filing a chargeback with the vendor. As far as I'm aware, that's simply not a thing. $\endgroup$
    – Kevin
    May 5, 2022 at 2:24

2 Answers 2

22
$\begingroup$

You've created a hash commitment with a random blinding factor. This will work, and the blinding factor is necessary so that as cards are progressively revealed to the player, it is not possible for the player to learn useful information about the hash message in order to be able to brute force the remainder of the shuffled deck. A uniformly random 128-bit blinding factor is sufficient.

You can compact this further by declaring a 128-bit 'seed' instead of listing all of the individual card positions, and then using a deterministic shuffle based on this seed to shuffle the cards.

If you do this using the shuffle method linked above, you will not need to use a blinding factor. This is because, by definition, a CSPRNG can withstand the "next-bit test". Knowledge of some of the output of a CSPRNG will not make it easier to brute force the seed or provide any advantage in guessing the next cards in the deck.

Therefore, $commitment = hash(\texttt{128-bit seed})$.

Note that a truly random shuffle will have $log_2(52!)\approxeq225$ bits of entropy, which is greater than the entropy of the seed. However, it would be infeasible to even determine a single shuffle outcome that would not be obtainable (out of the approx. $2^{225}$ possible shuffles), and so it would not be an improvement to have a seed larger than 128 bits.

$\endgroup$
8
  • $\begingroup$ Wouldn't a deterministic shuffle based on a 128-bit seed make it impossible to reach the vast majority of possible (~225 bit) shuffles? Most possible shuffles won't be hit anyways given how many there are, but that seems like the kind of thing that would bug someone who's worried about the fairness of the shuffle. $\endgroup$ May 3, 2022 at 15:26
  • 3
    $\begingroup$ I think the blinding factor is a good idea. If the raw deck was hash-committed, then if at some point most of the cards are revealed to the player, he can brute-force the remaining cards. $\endgroup$
    – Nayuki
    May 3, 2022 at 17:27
  • 3
    $\begingroup$ @JackAidley you're using the same logic that causes people to worry that their randomly chosen bitcoin wallet key could be brute forced. There is no small signal to pick up on, for the same mathematical reason that knowledge of the hash commitment does not constitute a small signal about the seed. It's technically true that you could succeed at brute force, but you have to trust how astronomically unlikely that is. $\endgroup$
    – knaccc
    May 4, 2022 at 17:16
  • 2
    $\begingroup$ @knacc You don't need to bruce force anything, you just need the probability of card X following card Y to be not precisely 1/52. While 128-bit will make things much harder to detect, with money on the line any defect will be exploited. This has actually happened with online casinos that failed to use proper shuffling algorithms in the past, although admittedly not at the 128 bit level. $\endgroup$ May 4, 2022 at 17:30
  • 1
    $\begingroup$ @JackAidley with knowledge of the hash commitment, it's also technically true that after a few cards have been dealt (to account for hash collision issues), you can tell with 100% certainty what all of the remaining cards in the shuffle will be. However, once you start to actually quantify the astronomic nature of the brute forcing involved, the picture looks entirely different. $\endgroup$
    – knaccc
    May 4, 2022 at 17:44
21
$\begingroup$

To extend knaccc's answer, it's even possible to use commitment schemes to prove (up to a point) that the server didn't cheat during the shuffle, e.g. like this:

  1. The server chooses a random 128-bit number $x$ and a 128-bit blinding factor $r_x$, and sends the commitment $c_x = H(x \,||\, r_x)$ to the client.
  2. The client chooses a random 128-bit number $y$ and sends it to the server. (No commitment is needed here.)
  3. The server hashes $x$ and $y$ together to obtain a 128-bit seed $s = H(x \,||\, y)$.
  4. The server uses $s$ as a seed to a deterministic PRNG, and uses the PRNG output to deterministically shuffle the deck.
  5. The game is played with the shuffled deck.
  6. At the end of the game, the server reveals $x$ and $r_x$, allowing the client to verify that the deck was shuffled correctly (and not modified after being shuffled).

Note that the server can still cheat, after a fashion, by inspecting the shuffled deck after step 4 and aborting the game (e.g. pretending that the connection was dropped) if it doesn't like the deck. A client should thus be suspicious of servers that frequently drop connections between steps 2 and 5, or even during the game in step 5. Ideally, there should be a way for a client to ask a server to resume an interrupted game at any point, and a client should be very suspicious of servers that refuse to do so.

(Securely implementing such a resume mechanism in a way that works even if the server crashes and forgets the game state seems doable, but probably outside the scope of this answer. Ask a new question if you're interested.)

Also note that the blinding value $r_x$ isn't actually needed here, since $x$ itself already has enough entropy to make brute-forcing the commitment infeasible. In fact it would arguably be slightly safer to omit $r_x$ and just make $x$ itself 256 instead of 128 bits long.

The bit lengths of $y$ and $s$ can also be increased if desired; 128 bits is just a safe and practical minimum. There's no point in making $s$ longer than the combined length of $x$ and $y$ together, though.

$\endgroup$
1
  • $\begingroup$ This is good - it helps deal with the problem in the question (neatly buried by assuming a trusted hashing algorithm) of the possibility that the server could generate hash collisions if it gets to choose its own seed completely freely. $\endgroup$ May 16, 2022 at 15:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.