6 ms·
The math of shuffling cards almost brought down an online poker empire
- ajross 1y agoArticle 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.
- deleted 1y ago[deleted]
- sejje 1y agoIt 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 1y agoThe 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 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/ 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 1y ago52! < 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.
- danielheath 1y agoRight, but storing 52! distinct values isn’t something a computer is going to be able to do.
- adastra22 1y agoA quantum computer can.
- zmgsabst 1y agoSo? You’re only using one deck at a time; so you only need to generate 1 bit randomly 226 times — then use that deck.
- bobbylarrybobby 1y agoWithout a bunch of (unentangled) electrons you can observe, getting 226 truly random bits in quick succession doesn't seem all that easy.
- alexey-salmin 1y agoDepends on what you mean by "truly random" but if it's "cryptographically secure random" then it's not particularly hard. There are strong monetary incentives to break all kinds of private keys but most of the time they hold pretty well.
- Sanzig 1y agoRDRAND has a throughput of hundreds of megabytes per second on most processors. Getting 226 bits is pretty easy, even shuffling millions of decks per second you'd be bottlenecked elsewhere. (That does sound like a fun optimization challenge: "write a program to fairly shuffle the most decks of cards per second possible.")
- deleted 1y ago[deleted]
- sneak 1y 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 1y agoI 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_dude 1y agoGo (and probably other languages) has the Fisher-Yates algorithm for shuffling https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
- genghisjahn 1y agoIt’s comments like this that keep me coming back to HN. I’d never heard of this before.
- andrewflnr 1y agoReally? It repeats a point from the article, and in so doing utterly misses the point of the comment it's replying to. Fisher-Yates is at least not broken, but it can only be as good as the underlying RNG.
- awesome_dude 1y agoGo has a cryptographically secure RNG now, I wouldn't be surprised if it's being used for the shuffle. Also, I'm keen to see what shuffle algorithms you know of that aren't susceptible to RNG issues
- ziofill 1y 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 1y agoIf 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 https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle [2]: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Na%C3%AFve_method https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#N...
- alexey-salmin 1y 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.
- caminante 1y agoNot sure "overconfidence" applies as you might be stretching the author's unfounded narrative. This is more impressive than the alternatives: 1. Security through obscurity. 2. Increased financial liability due to #1.
- alexey-salmin 1y ago
- mmmpetrichor 1y agoThis 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 1y agoClosed 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 1y agoMTGA uses a method called ‘smoothing’ for initial hand selection: https://mtgazone.com/mtg-arenas-opening-hand-algorithm-and-smoothing/ 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 1y agoModo uses FY and fits not smooth draws. Arena only smooths in best of 1 matches.
- Sophira 1y agoOne 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?
- adastra22 1y agoNo cryptographically secure PRNG has a 64-bit state. If you are not using a CSRNG in an adversarial environment, you have bigger problems.
- kristianp 1y agoLink to the discoverers of the problem: https://web.archive.org/web/20140104095330/http:/www.cigital.com/papers/download/developer_gambling.php 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 1y agoNo paywall mirror: https://archive.ph/ONQgF https://archive.ph/ONQgF
- dragontamer 1y agoRDRAND 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.
- pmarreck 1y agoWhy 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)
- kerkeslager 1y 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 https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
- pmarreck 1y agoFrom 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-86693a0d8722 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.
- runeblaze 1y 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 1y agoSatsifactory 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_ 1y agoBut 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.
- VanTheBrand 1y agoRight and that’s what satisfactory means, the condition was satisfied.
- insaider 1y agoLame clickbait title. TLDR; shuffling algorithm's have improved since the 90s...
- defrost 1y agoReally? 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 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 1y agoWhen 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 1y agoOnline 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 1y agoNone 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)
- kittikitti 1y agoI'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 1y agoA lot of problems are pretty hard if you insist on doing zero research