RNG was seeded with a millisecond time of day, leading to 86.4M possible decks. Oooph.
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.
> 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).
You’ve got to be kidding me. What’s wrong with sampling each card independently and uniformly (without replacement)?
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...
> 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.
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?
It actually has some depth into the multiple problems of the algorithm published by the gaming company.
Also, I'm keen to see what shuffle algorithms you know of that aren't susceptible to RNG issues
The whole premise of computers being unable to do shuffling as good as humans is ridiculous. 52! is huge but log(52!) is not.
If anything it's humans (unless specifically trained) who produce horribly biased shuffles. Whole chunks of sequences from the previous deal can show up, either directly or spaced 2x or 4x. Try ordering a deck first, then shuffle it, then open each card and see if you notice any patterns.
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.
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)
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.
There are strong monetary incentives to break all kinds of private keys but most of the time they hold pretty well.
"... 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,"
Assuming CSPRNG and fisher yates, why is it only "satisfactory"...? What's better...?
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
(That does sound like a fun optimization challenge: "write a program to fairly shuffle the most decks of cards per second possible.")
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.
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.
2. Nobody in this thread is criticizing Fisher-Yates, because in all likelihood all of us are using Fisher-Yates. We're discussing the failure of the algorithm used in the article.
3. Please take the time to read and understand the posts you respond to before you respond to them.
(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.
Yes.
Pretty much every modern language ships with a secure PRNG (which probably just calls /dev/urandom). A poker site probably has enough throughput to want to not block while waiting for /dev/urandom to build up entropy, so they might do something faster, but /dev/urandom is probably secure, it just might be a slower than a big poker site needs.
The non-evenly-diving divisor thing is a bit trickier, which is why standard libraries implement Fisher-Yates for you. But the solution is basically:
Using your PRNG, generate the number of bits you need. So if you need a number 0-51, generate 6 bits. 6 bits can hold 0-63. If you get a number in the range 52-63, discard that and generate a new 6-bit number with the PRNG.
If you need a number in an awkward range like 0-35, you'll need to discard a lot of numbers, but keep in mind this may still be faster than modular division which is pretty dang slow.
> 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.
That's very much not what I said.
"Testing it thoroughly" is not adequate. Start by proving the algorithm is correct. If you don't have a proof the algorithm works there's no reason to even start implementing it so there's nothing to test.
> 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...
Jesus Christ, no. If you still believe anything ChatGPT says then security is not the field for you.
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.
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)
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.
The following algorithm is not susceptible to RNG issues (in Rust, since I've been playing around with it):
fn shuffle(vec: &Vec) -> () {
}
Poker must be played in person, otherwise it’s a dead game
So the fourier-transform of white noise is still.... white noise. Random is random as you say. But this has implications. That means the "wattage" of noise (ie: Voltage * Current == Watts aka its power) is a somewhat predictable value. If you have 0.5 Watts of noise, it will be 0.5 Watts of noise in the frequency-domain (after a fourier transform, across all frequencies).
The hard part of amplification is keeping it consistent across all specifications. I assume the previous post was talking about keeping white noise (which is "flat" across all frequency domains), truly flat. IE: It means your OpAmps (or whatever other amplifer you use) CANNOT distort the value.
Which is still student level (you cannot be a good EE / Analog engineer if you're carelessly introducing distortions). Any distortion of white-noise is easily seen because your noise profile weakens over frequency (or strengthens over frequency), rather than being consistent.
[1] https://bughunters.google.com/blog/5424842357473280/zen-and-...
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...
If that's not overconfidence then it's hard to find what is.
That would certainly be a good thing to check before using Go's shuffle for real-money poker games. I wouldn't take it for granted.
> Also, I'm keen to see what shuffle algorithms you know of that aren't susceptible to RNG issues
There are not and cannot be any such algorithms. That's the entire point of this thread. Fisher-Yates is necessary but not sufficient. You either have sufficient random bits for your shuffle or not.
If ChatGPT says things that are empirically provable, then it's not wrong, is it?
Also, maybe be less of an asshole next time. People are allowed to be wrong, that is the whole point of a discussion, and ridicule is not a counterargument.
/eyeroll
We're not interested in sorting all possible decks, just all possible cards (52) into 1 unique randomized deck. The more bits we assign to these, the more any error or bias in the source goes to nil. (In contrast, consider the use of only 4 bits.)
Since everyone's bashing my use of ChatGPT, I don't think ChatGPT5 would have made that categorical error.
For Fisher-Yates, if the RNG is good then the output permutation is independent of the input permutation. That's not true for your proposed algorithm, and neither you nor the the LLM has analyzed to determine how quickly the sensitivity to the input permutation decays. That sensitivity will have complicated structure, so it's a nontrivial problem in cryptanalysis.
The problem where the low bits of old, not cryptographically secure PRNGs were particularly non-random is real. That would be a problem for any algorithm using it though--imagine if your riffle took rand() % 2. The resolution (use the high bits, not the low bits) is the same for any algorithm. It's possible that your proposed algorithm is less sensitive because the much greater number of RNG calls makes it somehow average out, but neither you nor the LLM has analyzed that, because the residual structure is again a cryptanalysis problem.
Any potentially adversarial application should use a CSPRNG, moving the cryptographic security into that existing, well-studied block. So the problem you're trying to solve doesn't exist in practice. The LLM can probably be prompted to tell you that; but since you stated that the new shuffling algorithm was your idea, it worked to find reasons it was a good one. I don't think this is a good use of LLMs, but if you're going to then you have to avoid any suggestion that the new idea is yours, to avoid triggering the sycophancy.
Or you could have a lazily calculated infinite precision random number per card and use more like 6 bits per card on expectation. Other than using more (and annoyingly variable) memory, this may well be faster than a properly unbiased Fisher-Yates.
Or you could assign a few bits per card, sort, and then recurse on each group of cards that sorted into the same bucket.
In summary, there are lots of genuinely unbiased solutions (assuming a perfect binary RNG), and they all boil down to something roughly equivalent to rejection sampling.
Why is it beside the point?
You haven't established their intent for gross negligence and give no charity to the fact this was 30 years ago (pre-Wikipedia and the search breadth we have today). Since then, people have continued to expose severe RNG design flaws in other systems designed by very smart people. It happens...
RDRAND is allowed to stretch the true random seed a little bit inside of hardware, which is sufficient for most purposes.
CSPRNG AES256 with 2^256 random seed is safe.
CSPRNG AES128 with 2^128 (or less) random seed is not safe.
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.
That's theoretically true by a counting argument, but for a CSPRNG the only way to compute that next shuffle costs about as much computationally as brute force. 128 bits is enough to make that infeasible, though 256 may be preferable for the usual abundance of caution.
The number of permutations doesn't matter here, since an attack becomes computationally infeasible before it becomes counting infeasible. It's also possible for a practical attack to exist even when the output can't be predicted exactly, since statistical information is still valuable.
Imagine paying to a professional plumber, he installs the toilet upside down and then posts the photos online for the community to check his work.
When you do a shuffling algorithm in a sensitive context (money or security), you have prove that it returns all the possible permutations with equal probability plus put lower bounds on the amount of entropy you need from the underlying RNG. If you're unable to prove it, you shouldn't move forward with the algorithm. Any irregularities in the output distribution can be exploited. This is textbook knowledge pioneered in early encryption works and perfected by the time WWII ended. Evidently the effort to prove correctness was never made.
Now the original article can indeed misrepresent or omit important facts. I'm definitely open to reconsider my conclusion if more facts become available. However "there was no Wikipedia" isn't one of them, it doesn't count as an excuse not to do your job properly.
If it turned out, for example, that "ASF Software" wasn't even aware that their shuffling algorithm was used to shuffle cards and just shipped it along with 200 other basic algorithms as a some sort of "better standard library", this would change the situation. However from the quick googling it seems that their product wasn't a standard library, it was specifically software for Texas Hold'em. This is a "you had one job" kind of situation.
> Since then, people have continued to expose severe RNG design flaws in other systems designed by very smart people. It happens...
Absolutely, but we're not talking frontiers of Computer Science here.
* If you seed your RNG with at most 86 million unique values, you get at most 86 million unique random sequences out of it.
* If your code should have M possible equiprobable outcomes, it has N equiprobable outcomes, and N doesn't divide M, you're in trouble.
Such as the reverse-bias shot and/or avalanche noise at the pn junction of a reverse bias'ed Zener Diode. Which is white-noise into the hundreds-of-MHz. Maybe not good enough for RDSEED, but certainly good enough and fast-enough for most hobbyist projects who are experimenting with this for the first time.
I didn't say or imply books didn't exist. You can't credibly say it was as readily available, and I promise you that people are still making these mistakes, today.
> When you do a shuffling algorithm in a sensitive context (money or security), you have prove that it returns all the possible...If you're unable to prove it, you shouldn't move forward with the algorithm.
Ideally, of course! This is a really high standard that I'm afraid isn't enforced in a lot of commercial or even sensitive applications. 86 million permutations is probably good enough and even if someone was clever enough to synch clocks and narrow to 200k permutations, then I'm not convinced there was actually any harm.
Do you have any proof of harm?
And there are plenty of smart people in the 90s and beyond not realizing that relying a system clock to seed values is attackable. These guys, to their credit, patched their system by openly providing their algorithms.
Even if their clients had been harmed, they'd published the algorithm so that their "sophisticated" clients could audit the algorithm.
> I'm definitely open to reconsider my conclusion if more facts become available.
This is circular as you're taking the article's narrative at face value without getting any primary sources confirming gross negligence or "arrogance" as you imply.
Of course not, this is ridiculous. If your job is to shuffle the deck, shuffle it well. It's like doing a 80/20 coinflip and arguing that 50/50 is a "really high standard". And that for a company that sells bet-money-on-coinflips software.
If you don't know how to do it well -- read a book or use std::random_shuffle. Somehow Stepanov was able to do it right (assuming a good RandomNumberGenerator input) from the first try in 1993, without Wikipedia poor guy. And this wasn't even his main job, random_shuffle was one of a dozens of algorithms he envisioned and implemented for the STL.
> This is circular as you're taking the article's narrative at face value without getting any primary sources confirming gross negligence or "arrogance" as you imply.
I did some quick research and it seems that ASF Software had indeed developed the Planet Poker online platform. Which comes down to failing at your main job, I don't really see what other evidence you expect here?
I strongly believe that people in general and software engineers in particular should be held up to high standards. Finding excuses for how school-level math is too hard for them is condescending. It is disrespectful to the very people you're talking about.
If you say they couldn't even understand that N^N is not divisible by N! you basically say that they're mentally challenged. I on the contrary say that they most certainly would've been able to understand it if they made an effort -- which they didn't. So negligence.
> if someone was clever enough to synch clocks and narrow to 200k permutations, then I'm not convinced there was actually any harm.
I don't think you understand the situation at all. In Hold'em in the end you see 7 cards: 2 in your hand and 5 on the table. That's 52x51x...x46 = 674B different sequences of open cards.
This means that by the time you see these cards you can know exactly which of the 200k permutations the engine had chosen for this hand. There's only one that precisely matches one of the 674 billions possible open cards combination that you observe.
In fact, by the time you see the flop (2+3 open cards, 311M variants), you know everyone else's cards.
No, you're making a logical error. It's not that I believe the opposite of what ChatGPT says, it's that I don't believe what ChatGPT says based on ChatGPT saying it alone. If ChatGPT says your algorithm is right, it's not that I automatically believe your algorithm is wrong, it's that I believe I still don't know it's right because ChatGPT is shit at being right.
> The dilemma is that it is mostly right, most of the time, isn't it? Almost like... people?
I mean, yeah. Which is why I don't believe things just because some random person says them, either.
I tend to assign confidence intervals to beliefs in my head, and even and expert saying something doesn't make me super confident in it. I tend to believe things strongly if I can understand the hard evidence for them, not because any person, even an expert, says it.
With security, we have tens of thousands of examples of unproven security assertions being proven wrong later with disastrous effect, so the standard of proof is very high, and ChatGPT saying it is absolutely nowhere near close enough to proof. The only acceptable proof with a security algorithm is mathematical proof.
> If ChatGPT says things that are empirically provable, then it's not wrong, is it?
ChatGPT also says things that are empirically disprovable, so basically you always have to go to empirical proof to tell whether what ChatGPT has said is true, making ChatGPT next-to-useless if accuracy is at all a concern. Just go to empirical proof and skip the pointless ChatGPT step.
And accuracy really, really is a very big concern in secure random shuffling algorithms, so you really really need to empirically prove that they work which you really really have not done because you stopped thinking when you trusted ChatGPT. Your shuffling algorithm is not proven, and very likely is not secure.
Unless I've missed something, you still seem to be under the very wrong impression that you've come up with a secure shuffling algorithm. You simply have not come up with a secure shuffling algorithm. The minimum viable evidence of security for an algorithm is mathematical proof and you don't have that, and you don't get to sit a the security table until you do. Put bluntly: mathematical proof or GTFO.
Yes, I'm gatekeeping, and there's a very good reason for that: we know from tens of thousands of bad attempts at secure algorithms that if there isn't a proof of security it very likely is not secure, with disastrous effects. It is not a kindness to let this sort of wrong information spread, and it's not assholish to be clear that it is wrong.
EDIT: Even if you want to add "probably" or some other qualifying word to your claims, "This shuffling algorithm is probably secure" is still wrong. No, that shuffling algorithm is probably not secure. I am sorry to be a hardass here, but the idea that this is an effective approach to security needs to be deleted from your mind.
This was edited in after my original response, so I didn't respond to it previously.
I won't generally do the work to find the attacks your bad security claims are susceptible to, but this one is trivial.
This does not degrade gracefully in any way. If your biased source of randomness generates the same numbers more than once, the items in the list are assigned the same number, so that sorting creates a bias toward the pre-shuffle ordering. This sort of collision is more common than one would intuit due to the birthday paradox[1] which is why this class of attacks is known as birthday attacks. In short, the birthday paradox amplifies problems of biased randomness sources rather than degrading gracefully.
In fact, this bias toward the pre-shuffle ordering still exists even with a perfect RNG, it's just going to be extremely unusual for a collision to occur in the space of 128 bits. But Fisher-Yates doesn't have this problem; why use an algorithm that we can easily prove is biased, even if the bias is negligible with proper PRNG?
Also, I really have to question your claim that this is even easier than Fisher-Yates. Fisher-Yates is not particularly complicated. Did you even bother to learn how Fisher-Yates works before assuming you could come up with a simpler solution than the industry standard?
[1] https://en.wikipedia.org/wiki/Birthday_problem
EDIT: Another problem with all the algorithms you've proposed is that they can't be partially applied. A hand of 6max Texas Hold'em, the most common online poker variant, requires only 2x6 + 5 = 17 cards, and by partially applying Fisher-Yates you can select just the first 17 cards in the shuffled deck without having to know or generate the other 35. This will be faster and deplete your RNG slower, further decreasing the chance of bias.