←back to thread

97 points indigodaddy | 1 comments | | HN request time: 0.208s | source
Show context
pmarreck ◴[] No.45155251[source]
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)

replies(3): >>45155382 #>>45155506 #>>45156321 #
kerkeslager ◴[] No.45155382[source]
> 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

replies(1): >>45155421 #
pmarreck ◴[] No.45155421[source]
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.

replies(3): >>45155555 #>>45156002 #>>45207546 #
1. kerkeslager ◴[] No.45207546[source]
> 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.

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.