Serious Security: How randomly (or not) can you shuffle cards?

Cryptoguru Bruce Schneier (where crypto means cryptography, not the other thing!) just published an intriguing note on his blog entitled On the Randomness of Automatic Card Shufflers.

If you’ve ever been to a casino, at least one in Nevada, you’ll know that the blackjack tables don’t take chances with customers known in the trade as card counters.

That term is used to refer to players who have trained their memories to the point that they can keep close track of the cards played so far in a hand, which gives them a theoretical advantage over the house when predicting whether to stand or hit as play progresses.

Card counters can acquire an advantage even if all they do is keep track of the ratio of 10-cards (Ten, Jack, Queen and King) to non-10s left in the dealer’s shoe.

For example, if the dealer is sitting with an Ace, but an above-average number of 10-value cards have already been used up, then the dealer has a below-average chance of making a blackjack (21 points with two cards, i.e. Ace and one of 10-J-Q-K) and winning at once, and an above-average chance of going bust before reaching the stopping point of 17 and above.

If you can balance the probabilities in your head in real time, then you may be able modify your bets accordingly and come out ahead in the long run.

Don’t actually try this, at least in Nevada: the casino is likely to catch you out pretty quickly, because your pattern of play will diverge notably from the most informed winning choices available if you aren’t counting cards. You might not end up in court, but you will almost certainly get escorted off the premises, and never let back in again.

Levelling the odds

To reduce the counterbalance of probabilities that card counters enjoy (those who haven’t been caught yet, at least), the casinos typically:

• Deal hands from a shoe loaded with six packs (decks) of 52 cards. This means that each hand dealt out skews the remaining distribution of cards less than if a single pack were used.
• Shuffle the entire shoe of 312 cards (six packs) before every hand. To save time and to remove suspicion from the dealer, a pseudorandom electromechanical machine shuffles the cards right on the table, in front of all the players.

That immediately raises the question posed by Schneier: just how well-shuffled are the cards when they emerge from the machine?

Notably, with six new packs of cards, which arrive in a predictable order (e.g. Ace to King of Hearts, Ace to King of Clubs, King to Ace of Diamonds, King to Ace of Spades), how much partial ordering is left after the machine has done its work?

Could you “guess” the next card out of the shoe better than chance suggests?

A fully electronic randomiser is limited in its complexity mainly by the speed of the CPU that it uses, which is typically measured in hundreds of millions or billions of arithmetical operations a second.

But an electromechanical card shuffler literally has to move the cards around in real life.

There’s obviously a limit to how quickly it can perform pack splits, card swaps and interleaving operations before the speed of the mechanism starts to damage the cards, which means that there’s a limit to how much randomness (or, more precisely, pseudorandomness) the machine can introduce before it’s time to play the next hand.

Shuffle for too short a time, and the casino might actually make things easier for card counters, if there’s a known bias in the distribution of the cards right from the start.

Shuffle for too long, and play will be too slow, so that players will get bored and wander off, something that casinos desperately try to avoid.

Schneier’s blog posts links to a fascinating piece by the BBC that describes how a mathematician/magician called Persi Diaconis of Stanford University, together with Jason Fulman and Susan Holmes, conducted a formal investigation into this very issue earlier this century, in a paper entitled simply: ANALYSIS OF CASINO SHELF SHUFFLING MACHINES.

Levels of complexity

Clearly, there are some shuffling techniques that don’t mix the cards up much at all, such as simply cutting the pack into two parts and moving the bottom part to the top.

Other techniques result in (or feel as though they should result in) to better mixing, for example the riffle shuffle, where you split the pack roughly in half, hold one half in each hand, and “flip” the two halves together, interleaving them in a pseudorandom way that alternates between taking a few cards from one side, then a few cards from the other.

The idea is that if you riffle-shuffle the pack several times, you perform a pseudorandom sequence of cuts each time you divide the pack before each riffle, mixed together with a pseudorandomly variable sequence of pseudorandom interleaving operations involving an N-from-the-left-then-M-from-the-right process.

Intriguingly, however, when skilled human shufflers are involved, none of those assumptions of unpredictability are safe.

Dextrous magicians and crooked dealers (Diaconis himself is the former, but not the latter) can perform what are known as faro shuffles, or perfect shuffles, where they do both of the following things every time they riffle the pack:

• Split the cards precisely in two, thus getting exactly 26 cards in each hand.
• Interleave them perfectly, flipping down exactly one card at a time alternately from each hand, every single time.

Diaconis himself can do perfect shuffles (including the rare skill of doing so with just one hand to hold both halves of the pack!), and according to the BBC:

[He] likes to demonstrate the perfect shuffle by taking a new deck of cards and writing the word RANDOM in thick black marker on one side. As he performs his sleight of hand with the cards, the letters get mixed up, appearing now and then in ghostly form, like an imperfectly tuned image on an old TV set. Then, after he does the eighth and final shuffle, the word rematerialises on the side of the deck. The cards are in their exact original sequence, from the Ace of Spades to the Ace of Hearts.

Two types of perfection

In fact, there are two sorts of perfect shuffle, depending on which hand you start riffling from after cutting the cards into two 26-card piles.

You can interleave the cards so they end up in the sequence 1-27-2-28-3-29-…-25-51-26-52, if the first card you flip downwards comes from the hand in which you are holding he bottom half of the pack.

But if the first card you flip down is the bottom card of what was previously top half of the pack, you end up with 27-1-28-2-29-3-…-51-25-52-26, so the card just past halfway ends up on top afterwards.

The former type is called an out-shuffle, and reorders the pack every eight times you repeat it, as you can see here (the image has 52 lines of pixels, each line corresponding to the edge of one card with the word RANDOM written on it with a marker pen):

The latter type is an in-shuffle, and this, amazingly, takes 52 re-shuffles before it repeats, though you can see clearly here that the pack never really shows any true randomness, and even passes through a perfect reversal half way through:

What did the mathematicians say?

So, back in 2013, when Diaconis el al. studied the shelf shuffler machine at the manufacturer's invitation, what did they find?

As the paper explains it, a shelf shuffler is an electromechanical attempt to devise an automated, randomised "multi-cut multi-riffle shuffle", ideally so that the cards only needs to be worked through once, to keep shuffling time short.

The cards in a shelf shuffler are rapidly "dealt out" pseudorandomly, one at a time, onto one of N metal shelves inside the device (whence the name), and each time a card is added to a shelf it's either slid in at the bottom, or dropped on the top of previous cards. (We assume that trying to poke the card in between two random cards already in the stack would be both slower and prone to damage the cards.)

After all cards have been assigned to a shelf, so that each shelf has about 1/Nth of the cards on it, the cards are reassembled into a single pile in a pseudorandom order.

Intuitively, given the pseudorandomness involved, you'd expect that additional re-shuffles would improve the overall randomness, up to a point…

…but in this case, where the machine had 10 shelves, the researchers were specifically asked, “Will one pass of the machine be sufficient to produce adequate randomness?”

Presumably, the company wanted to avoid running the machine through multiple cycles in order to keep the players happy and the game flowing well, and the engineers who had designed the device had not detected any obviously expoitable statistical anomalies during their own tests.

But the company wanted to make sure that it hadn’t passed its own tests simply because the tests suited the machine, which would give them a false sense of security.

Ultimately, the researchers found not only that the randomness was rather poor, but also that they were able to quantify exactly how poor it was, and thus to devise alternative tests that convincingly revealed the lack of randomness.

In particular, they showed that just one pass of the device left sufficiently many short sequences of cards in the shuffled output that they could reliably predict between 9 and 10 cards on average when a pack of 52 shuffled cards was dealt out afterwards.

As the researchers wrote:

[U]sing our theory, we were able to show that a knowledgeable player could guess about 9-and-a-half cards correctly in a single run through a 52-card deck. For a well-shuffled deck, the optimal strategy gets about 4-and-a-half cards correct. This data did convince the company. The theory also suggested a useful remedy.

[…]

The president of the company responded, “We are not pleased with your conclusions, but we believe them and that’s what we hired you for.” We suggested a simple alternative: use the machine twice. This results in a shuffle equivalent to a 200-shelf machine. Our mathematical analysis and further tests, not reported here, show that this is adequately random.

What to do?

This tale contains several “teachable moments”, and you’d be wise to learn from them, whether you’re programmer or product manager wrestling specifically with randomess yourself, or a SecOps/DevOps/IT/cybersecurity professional who’s involved in cybersecurity assurance in general:

• Passing your own tests isn’t enough. Failing your own tests is definitely bad, but it’s easy to end up with tests that you expect your algorithm, product or service to pass, especially if your corrections or “bug fixes” are measured by whether they get you through the tests. Sometimes, you need a second opinion then comes from an objective, independent source. That independent overview could come from a crack team of mathematical statisticians from California, as here; from a external “red team” of penetration testers; or from an MDR (managed detection and reponse) crew who bring their own eyes and ears to your cybersecurity situation.
• Listening to bad news is important. The president of the shuffling machine company in this case answered perfectly when he admitted that he was displeased at the result, but that he had paid to uncover the truth, not simply to hear what he hoped.
• Cryptography in particular, and cybersecurity in general, is hard. Asking for help is not an admission of failure but a recognition of what it takes to succeed.
• Randomness is too important to be left to chance. Measuring disorder isn’t easy (read the paper to understand why), but it can and should be done.

Short of time or expertise to take care of cybersecurity threat response? Worried that cybersecurity will end up distracting you from all the other things you need to do?

Learn more about Sophos Managed Detection and Response:
24/7 threat hunting, detection, and response  ▶