6 ms·

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 rand

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)

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 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
amluto 1y 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 1y 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.com/papers/download/developer_gambling.php https://web.archive.org/web/20140104095330/http:/www.cigital...

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

amluto 1y 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 1y 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.com/papers/download/developer_gambling.php https://web.archive.org/web/20140104095330/http:/www.cigital...