5 ms·

> 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.

> 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 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-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.
- kerkeslager 1y 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. 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 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.
  - indigodaddy 1y ago
    Lol, I laughed at his confident usage of "turns out" and "apparently" after his conclusive conversation with his chatgpt expert..
    - pmarreck 1y ago
      I never claimed conclusivity; words like "apparently" were supposed to suggest that, which is why I didn't use "obviously," "definitely" or "conclusively". 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
      - indigodaddy 1y ago
        I don't think you're either wrong or right (in fact my intuition sides with yours I think) because I definitely know way less than you about the subject in general, or probably also less than almost anyone here on HN-- just the trust of swaths of people in the authoritativeness of LLM outputs does generally amuse me. I'm sure we'll get there one day, but we're not there yet. I clearly offended you, and I apologize.
      - kerkeslager 1y ago
        Sure, it's okay to be wrong, but it gets significantly less okay when you just keep doubling down on being wrong and refuse to admit you are wrong. 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.
- oneshtein 1y ago
  > Turns out that an even easier way is just to assign 128 bits of randomness 52! is roughly 2^226. You cannot address all 2^226 positions with a 2^128 address generated from 2^64 seed.
  - rcxdude 1y ago
    it's 128 bits per card. That's vastly more than 226 bits.
    - amluto 1y ago
      You could use something like 12 bits of randomness per card (a very rough approximation of the log_2(n^2)) to get the probability that you reuse a number down to a manageable level, check if you’ve reused a number (which is basically free once you’ve sorted), and then repeat the whole process if you reused a number. 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.
  - pmarreck 1y ago
    With all due respect, I don't think you understand. The 128 bits are just to sort the 52 cards into a random-enough order, and they have sufficient entropy and space for that. 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.
    - oneshtein 1y ago
      2^128*52 is 6656 bits, or 30x more than 2^226, so it will work IF those bits are independent. If CSPRNG is used, such as AES128, it will use 2^128 seed, which is not enough to cover all 2^226 permutations. If PRNG sequence is reused to generate more shuffles, then the next shuffle can be predicted from the previous one. CSPRNG AES256 with 2^256 random seed is safe. CSPRNG AES128 with 2^128 (or less) random seed is not safe.
- kerkeslager 1y ago
  > 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 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.

pmarreck 1y 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-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.

kerkeslager 1y 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. 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 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.
- indigodaddy 1y ago
  Lol, I laughed at his confident usage of "turns out" and "apparently" after his conclusive conversation with his chatgpt expert..
  - pmarreck 1y ago
    I never claimed conclusivity; words like "apparently" were supposed to suggest that, which is why I didn't use "obviously," "definitely" or "conclusively". 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
    - indigodaddy 1y ago
      I don't think you're either wrong or right (in fact my intuition sides with yours I think) because I definitely know way less than you about the subject in general, or probably also less than almost anyone here on HN-- just the trust of swaths of people in the authoritativeness of LLM outputs does generally amuse me. I'm sure we'll get there one day, but we're not there yet. I clearly offended you, and I apologize.
    - kerkeslager 1y ago
      Sure, it's okay to be wrong, but it gets significantly less okay when you just keep doubling down on being wrong and refuse to admit you are wrong. 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.
oneshtein 1y ago
> Turns out that an even easier way is just to assign 128 bits of randomness 52! is roughly 2^226. You cannot address all 2^226 positions with a 2^128 address generated from 2^64 seed.
- rcxdude 1y ago
  it's 128 bits per card. That's vastly more than 226 bits.
  - amluto 1y ago
    You could use something like 12 bits of randomness per card (a very rough approximation of the log_2(n^2)) to get the probability that you reuse a number down to a manageable level, check if you’ve reused a number (which is basically free once you’ve sorted), and then repeat the whole process if you reused a number. 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.
- pmarreck 1y ago
  With all due respect, I don't think you understand. The 128 bits are just to sort the 52 cards into a random-enough order, and they have sufficient entropy and space for that. 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.
  - oneshtein 1y ago
    2^128*52 is 6656 bits, or 30x more than 2^226, so it will work IF those bits are independent. If CSPRNG is used, such as AES128, it will use 2^128 seed, which is not enough to cover all 2^226 permutations. If PRNG sequence is reused to generate more shuffles, then the next shuffle can be predicted from the previous one. CSPRNG AES256 with 2^256 random seed is safe. CSPRNG AES128 with 2^128 (or less) random seed is not safe.
kerkeslager 1y ago
> 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 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.