The math of shuffling cards almost brought down an online poker empire

https://www.scientificamerican.com/article/how-the-math-of-shuffling-cards-almost-brought-down-an-online-poker-empire/

by indigodaddy • 11 months ago

98 111 11 months ago

ajross• 11 months ago

Article goes through a mostly irrelevant discussion about "52 factorial is a really really big number" before getting to the computer science meat of the headline:

RNG was seeded with a millisecond time of day, leading to 86.4M possible decks. Oooph.

sejje• 11 months ago

It didn't even go into the fact that it got exploited, which it did.

And I don't think it almost brought them down.

shagie• 11 months ago

The number 52! is absurdly large. While the article is behind a paywall and so I can't see its full discussion, I'm reminded of https://czep.net/weblog/52cards.html that has a bit on the "how large is the number"

Start by picking your favorite spot on the equator. You're going to walk around the world along the equator, but take a very leisurely pace of one step every billion years. The equatorial circumference of the Earth is 40,075,017 meters. Make sure to pack a deck of playing cards, so you can get in a few trillion hands of solitaire between steps. After you complete your round the world trip, remove one drop of water from the Pacific Ocean. Now do the same thing again: walk around the world at one billion years per step, removing one drop of water from the Pacific Ocean each time you circle the globe. The Pacific Ocean contains 707.6 million cubic kilometers of water. Continue until the ocean is empty.

And it goes on.

Numbers like Tree(3) or Loader's number or the various "these are really big mathematical functions" ( relevant xkcd https://xkcd.com/207/ )... we know we can't comprehend them. But 52! - that's something that we think we can get our head around... and it's mind boggling large once you start doing the math and trying to relate it to real things that we can relate to (which are mind bogglingly large).

gucci-on-fleek• 11 months ago

52! < 2^226, so it's not that big in computer terms. It's smaller than a single AVX2 register, a ChaCha20/AES-256/Curve25519 key, a pair of IPv6 addresses, etc. Still mindbogglingly huge, but not uncommonly large.

kerkeslager9• 11 months ago

Sure, it's a big number, but nobody was ever approaching the problem of generating a randomly shuffled deck by generating all 52! possibilities and choosing one of them.

sneak• 11 months ago

Card dealers create a unique deck with each shuffle, something computers cannot replicate

This is entirely, unequivocally false.

Shuffling as an algorithm to implement is easy to fuck up, but if you use a good one and a true RNG source, computers can shuffle better than humans - just as randomly, and many orders of magnitude faster.

smallerize• 11 months ago

I think the RNG source is the point here. It's not as impossible as stated, but you have to put some work in to get a good one.

awesome_dude5• 11 months ago

Go (and probably other languages) has the Fisher-Yates algorithm for shuffling

https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

Sanzig2• 11 months ago

Do you? Modern CPUs have had built-in TRNGs for years.

indigodaddy3• 11 months ago

Maybe they mean that computers can't replicate the imperfections/shortcomings that might define human/hand shuffling? That's kind of how I took it.

evrydayhustling• 11 months ago

Those human imperfections likely decrease randomness - for example leaving cards that started adjacent more likely to remain adjacent han by strict chance.

dwattttt• 11 months ago

Given

an algorithm would randomly select an arrangement from the 52! possible decks. But no computer has enough memory to evaluate all of these possibilities

It sounds more like they don't understand how a computer can shuffle something.

mistercow• 11 months ago

There’s an almost mystical belief among certain tech and science journalists that computers are bad at randomness, and it’s really bizarre, and in my opinion, pretty harmful.

ziofill• 11 months ago

“In an ideal world, an algorithm would randomly select an arrangement from the 52! possible decks. But no computer has enough memory to evaluate all of these possibilities, and a perfect random number generator doesn’t yet exist. Therefore, developers generally rely on algorithms that simulate card shuffling.”

You’ve got to be kidding me. What’s wrong with sampling each card independently and uniformly (without replacement)?

RainyDayTmrw• 11 months ago

If you do it correctly, you've reinvented Fisher-Yates[1]. If you do it wrong, you've reinvented this unnamed, broken algorithm[2], instead.

But the issue in the article isn't application of pseudorandom numbers. It's seeding the generator.

[1] https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle [2]: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#N...

alexey-salmin15• 11 months ago

In the late 1990s the development platform ASF Software supplied several online poker providers, such as Planet Poker, with card-shuffling algorithms. The platform even posted the algorithm on its website as proof that the game was reliably programmed.

What amazes me is the level of overconfidence the developers of the broken algorithm had to post it online. I mean it's not that the probability theory was a novel and unexplored field at the time.

woopsn• 11 months ago

I guess this PRNG has recurrence period much less than 52! (or wasn't seeded appropriately), so that only sampled a fraction of the distribution

"... the system ties its number generation to the number of seconds that have passed since midnight, resetting once each day, which further limits the possible random values. Only about 86 million arrangements could be generated this way,"

mmmpetrichor• 11 months ago

This became a hot discussion issue in magic the gathering online (MTGO). I always felt my shuffles in MTGO felt different somehow than my offline paper shuffles. It's hard to know for sure when its all closed source. I know a lot of people were suspicious though.

IncreasePosts• 11 months ago

Closed source doesn't need to stop you - even if a server was dealing out the cards you can still do a randomness test on them once you gather enough deals, but you would probably need millions of hands of data to do the analysis (see: dieharder tests)

Fezzik• 11 months ago

MTGA uses a method called ‘smoothing’ for initial hand selection: https://mtgazone.com/mtg-arenas-opening-hand-algorithm-and-s...

I assume MTGO uses something similar and I swear I had a great analytical article bookmarked regarding MTGO shuffles but I can’t find it.

malnourish• 11 months ago

Modo uses FY and fits not smooth draws. Arena only smooths in best of 1 matches.

Sophira• 11 months ago

One thing that I wonder about is that even with Fisher-Yates, a PRNG relies on a seed value. Assuming that this seed is going to be a 64-bit value, that seed value can only go up to a maximum of 2^64-1 = 18,446,744,073,709,551,615.000, which is still less than 52!.

I know that modern operating systems use an entropy pool. Does this mean that the PRNG is re-seeded for every random number generated, thus making this a non-issue? Or does it just take from this entropy pool once?

adastra222• 11 months ago

No cryptographically secure PRNG has a 64-bit state. If you are not using a CSRNG in an adversarial environment, you have bigger problems.

kristianp• 11 months ago

Link to the discoverers of the problem: https://web.archive.org/web/20140104095330/http:/www.cigital...

It actually has some depth into the multiple problems of the algorithm published by the gaming company.

thedigitalone• 11 months ago

No paywall mirror: https://archive.ph/ONQgF

dragontamer5• 11 months ago

RDRAND and RDSEED are both using quantum principles (aka: heat and temperature / truly quantumly random noise at the microscopic level in the CPU's transistors) to generate random numbers.

Well... a seed at least. And then they are expanded using AES encryption IIRC (which "shouldn't" be breakable, and even if it were breakable it'd probably be very difficult to follow). I think RDSEED takes hundreds (or nearly a thousand) cycles to complete, but we're still talking millions-of-bits of entropy per second. More than enough to shuffle a deck even if you're taking a fresh RDSEED every single card.

Every few months, it feels like "someone effed up RNG" becomes an article. But in practice, RDRAND / RDSEED are the primitives you need. And you should be getting that for free with Linux's /dev/urandom on modern platforms.

----------

I think RDSEED / RDRAND cannot be "proven secure" because of all the VMs we are running in practice though. So its something you need to be running on physical hardware to be 100% sure of security. So its still harder than it looks.

But its not "impossible" or anything. Just work to cover all the little issues that could go wrong. After all, these RDRAND/RDSEED instructions were created so that we can send our credit card numbers securely across the internet. They're solid because they _HAVE_ to be solid. And if anyone figures out a problem with these instructions, virtually everyone in the cryptographic community will be notified of it immediately.

---------

EDIT: I should probably add that using the shot-noise found in a pn-junction (be it a diode or npn transistor) is a fun student-level EE project if anyone wants to actually play with the principles here.

You are basically applying an amplifier of some kind (be it 3x inverters, or an OpAmp, or another NPN transistor) to a known quantum-source of noise. Reverse-avalanche noise from a Zener Diode is often chosen but there's many, many sources of true white-noise that you could amplify.

klodolph• 11 months ago

What I’m impressed by is getting noise of a consistent level out of a circuit. That’s a nice second layer of difficulty to the “make some noise” EE project.

blobbers• 11 months ago

I think the noise has to be random... so its inherently inconsistent ;) .. maybe?

kittikitti2• 11 months ago

These are methods to generate cryptographically secure pseudo random numbers using a truly random seed.

dragontamer5• 11 months ago

RDSEED returns a truly random seed (as long as you aren't getting hacked while running in a VM or something)

RDRAND is allowed to stretch the true random seed a little bit inside of hardware, which is sufficient for most purposes.

thijsr• 11 months ago

When you can modify the microcode of a CPU, you can modify the behaviour of the RDRAND/RDSEED instructions. For example, using EntrySign [1] on AMD, you can make RDRAND to always return 4 (chosen by a fair dice roll, guaranteed to be random)

[1] https://bughunters.google.com/blog/5424842357473280/zen-and-...

dragontamer5• 11 months ago

I don't mean to say that RDSEED is sufficient for security. But a "correctly implemented and properly secured" RDSEED is indeed, quantum random.

IE: While not "all" RDSEED implementations (ie: microcode vulnerabilities, virtual machine emulation, etc. etc.) are correct... it is possible to build a true RNG for cryptographic-level security with "correct" RDSEED implementations.

------

This is an important factoid because a lot of people still think you need geiger counters and/or crazy radio antenna to find sufficient sources of true entropy. Nope!! The easiest source of true quantum entropy is heat, and that's inside of every chip. A good implementation can tap into that heat and provide perfect randomness.

Just yeah: microcode vulnerabilities, VM vulnerabilities, etc. etc. There's a whole line of other stuff you also need to keep secure. But those are "Tractable" problems and within the skills of a typical IT Team / Programming team. The overall correct strategy is that... I guess "pn-junction shot noise" is a sufficient source of randomness. And that exists in every single transistor of your ~billion transistor chips/CPUs. You do need to build out the correct amplifiers to see this noise but that's called RDSEED in practice.

pmarreck5• 11 months ago

Why not just simulate a real shuffle?

Just "cut" in a random location (rotate the deck a random amount), then split the deck roughly in half (add a bit of random variation), then "flip them together" back to front by alternately taking 1 or 2 (randomly, add a small chance of 3, so maybe 50% 1, 40% 2 and 10% 3) from each side till there are no cards left to shuffle. Then repeat 8 times or so (there's a certain minimum number of times that ensures good randomness)

kerkeslager9• 11 months ago

Why not just simulate a real shuffle?

If you are asking why your proposed shuffling method is insecure: I don't know, and that's why I would never use that.

Asking "why not do X?" is entirely not paranoid enough for security. If you want to propose an algorithm, start with trying to prove the security claims of the algorithm. In this case, you'd need to prove that your algorithm creates a permutation that is indistinguishable from random. If you can't prove it, it's highly probable that your algorithm doesn't create a random permutation and someone will figure out how to break it.

I'll point out that we already have proven shuffling algorithms[1] and they're obviously faster than what you've proposed. So the simple answer to your question is "Because it's unproven and slower than proven algorithms."

[1] https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

pmarreck5• 11 months ago

From what I understand, the quality of the randomness of Fisher-Yates depends entirely on the quality of the random source AND that you didn't bias it by using modulo with a non-evenly-dividing divisor. It actually says that right in the article.

My method may not suffer as much from those drawbacks, but you're right, without testing it thoroughly, there's no way to know and it should not be relied upon instead of F-Y.

EDIT: My intuition was correct more or less. Doing it the way I described serves to "smear" any bias across the deck. Fascinating chatgpt convo on it: https://chatgpt.com/share/68bd103f-9188-8004-8cbc-86693a0d87...

Turns out that an even easier way is just to assign 128 bits of randomness to each card and sort them by that. Degrades gracefully from biased sources, apparently.

amluto2• 11 months ago

You can:

(a) Use Fischer-Yates, which is fast and, if correctly implemented, unbiased, or

(b) Come up with an ad-hoc scheme like this, do some fancy math to bound its total variation distance (or, worse, some weaker concept of distance), convince yourself that the distance to the uniform distribution is acceptable, and end up with a slower algorithm when you’re done.

wzdd• 11 months ago

The artice links to the paper which discusses the issue. The paper identifies two problems: a biased swapping algorithm, and a PRNG with easy-to-guess state.

For the first problem, a very simple "for each card, pick a number between 1 and 52 and swap the card with that number (or do nothing if it's the same card)" is proposed to eliminate bias. This seems pretty simple to verify.

For the second problem, there is no workaround except to use a better RNG.

So in the context of the paper, the reason your algorithm wouldn't have worked is because the programmers seeded their PRNG with the time of day. In the context of shuffling more generally, I don't know but it seems that there are even simpler algorithms.

That paper: https://web.archive.org/web/20140104095330/http:/www.cigital...

runeblaze• 11 months ago

Today many online poker sites use the Fisher–Yates algorithm, also called the Knuth shuffle (which sounds delightfully like a dance). It’s easy to implement and delivers satisfactory results.

Assuming CSPRNG and fisher yates, why is it only "satisfactory"...? What's better...?

eterm• 11 months ago

Satsifactory in this context is good, not bad.

We live in a euphemistic world where "satisfactory" is presented to failures to not hurt their feelings, but the word also and originally means it's good enough, i.e. delivers an unbiased shuffle.

pfg_• 11 months ago

But it's not just good enough, it's optimal. It is equivalent to picking a random deck from the set of all possible decks assuming your random source is good. More random than a real shuffle.

insaider• 11 months ago

Lame clickbait title. TLDR; shuffling algorithm's have improved since the 90s...

defrost• 11 months ago

Really?

  The original Fisher–Yates shuffle was published in 1938 by Ronald Fisher and Frank Yates in their book Statistical tables for biological, agricultural and medical research.

   The modern version of the Fisher–Yates shuffle, designed for computer use, was introduced by Richard Durstenfeld in 1964. It is also known as the Knuth shuffle after Donald Knuth who popularized it in Volume Two of The Art of Computer Programming (1969)

~ https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

Picking a bad algorithm, as they did here in this example from the 1990's is timeless.

Good shuffle algorithms existed then, and had existed since the 1930s.

rekttrader• 11 months ago

When I did it back in the day for a poker site we also had the constraint of never storing the positions of shuffled cards for security reasons. We always sorted the deck and when it came to dealing I developed a shuffle server that got noise from a taped up webcams cmos sensor, when a player needed a card it polled the server which was just outputting random positions from 0 to 51 continuously, if the card position was already dealt, it re requested a new one, entropy was gotten from player decision time and network speed. It was a fun thing to build.

monero-xmr• 11 months ago

Online poker died because having 1 other person at the table sharing cards surreptitiously drastically increases the odds in your favor, which ruins cash games. Let alone AI which has mostly solved the game if you have a bot making your decisions.

Poker must be played in person, otherwise it’s a dead game

bzhang255• 11 months ago

None of this is wrong, but anecdotally, I will say that there are still human beings playing poker online, and a better human being can still win in the long run. (Though, live poker is much more fun)

kittikitti2• 11 months ago

I've run TRNG's to create truly random numbers that can be audited and certified by the NSF. Hardware like HSM's and TPM's were convenient sources. I just have to wait until a Big Tech gatekeeper propagates this method. Who knows? Maybe even the temperature parameter in language models could find some value in it.

procaryote• 11 months ago

A lot of problems are pretty hard if you insist on doing zero research

The math of shuffling cards almost brought down an online poker empire

Related Stories