4 ms·

Interesting, but there's one part I'm not sure I agree with. > Pseudo-random number generators are useful for many purposes, but unbiased shuffling isn't one o

Interesting, but there's one part I'm not sure I agree with. > Pseudo-random number generators are useful for many purposes, but unbiased shuffling isn't one of them. A properly seeded CSPRNG is perfectly fine at this. And if it's not, then all of our cryptography is pretty much screwed. This is why in modern kernels, /dev/random and /dev/urandom are the same (minus differences in behavior when the initialization isn't complete). As D.J. Bernstein put it, it's superstition to not trust CSPRNGs. https://www.mail-archive.com/cryptography@randombit.net/msg04763.html https://www.mail-archive.com/cryptography@randombit.net/msg0... And if it's good enough for crypto, it's good enough for card shuffling. FYI I am not a cryptographer

mlyle 2y ago
There are 52! possible decks of cards— if you don’t have more than 230 bits of entropy in your prng per deck shuffled things go badly pretty quick. You also tend to share deck state so far with the adversary. Shuffling cards is a surprisingly demanding prng application.
- magicalhippo 2y ago
  How many shuffled decks do you need to with 99% confidence determine if I used say Mersenne Twister or a hardware-based RNG? edit: I know MT has a rather large state, but it has some issues. Alternatively what about say one of the 128bit state PCG generators?
- adgjlsfhk1 2y ago
  Counterpoint, even if you only have 256 bits of entropy (which is common for many widely used PRNGs), you can prove that there's bias due to the pigeon hole principal, but finding a shuffle that is under-represented is computationally impossible.
  - pvillano 2y ago
    I can say, infalsifiably, it will be computationally possible eventually
    - SAI_Peregrinus 2y ago
      Eventually, but long after the Sun has expanded into a red giant and burned the surface of the Earth off.
  - deleted 2y ago
    [deleted]
- slaymaker1907 2y ago
  It’s almost certainly still good enough since it’s unlikely to be biased in ways that matter. Most hand shuffling methods have nasty biases as well. For standard riffle shuffling, there is often a bias in pulling from the pile opposite from the last pulled card (so alternating pairs of left and right). The model saying “7 shuffles is sufficient” as people like to quote presumes you pull from a pile only proportional to the size of the pile (so you get many fewer alternating runs).
  - Harmohit 2y ago
    That is such an interesting idea! I wonder if someone has systematically studied hand shuffling biases and what consequences it has (or should have) for brick and mortar casinos
    - Zanni 2y ago
      Yes. Card counters (advantage players at blackjack) studied shuffle tracking. I haven't seen much good material published on it, but I played on a team with a math whiz (physicist) who ran the numbers. For the casino we were playing at the time, the last 20 or so cards would be distributed over the bottom half of a six-deck shoe. A strategic cut would bring those three decks to the front, and you could play with a slight advantage. Suppose you're at a full table and 12 of the last 20 cards are aces or tens (rare but possible). These get shuffled and cut into the first three decks, giving you a true count of four (12/3) for the first half of the shoe, which is significant. We never really put it into practice, though, since: 1) you have to track the count for the last 20 cards in addition to the regular count, 2) shuffles change, 3) dealers are inconsistent, 3) casinos use different shuffles, 4) the typical advantage is likely to be much smaller. My knowledge on this is at least 20 years out of date, though, so who knows?
      - slaymaker1907 2y ago
        The bias I saw would likely be difficult to exploit without studying the mathematics a lot more. It seems to pass several statistical tests, but the problem I found was more about independence. Let's call the two splits L for left and R for right and consider the resulting deck to be defined as a sequence of these letters indicating whether that card was taken from the left or right pile so in theory you can specify a shuffle uniquely like "LRRLLLLLLRRR...". This method of labeling shuffles has the advantage of being extremely easy to record and also makes the bias I found apparent where there are way too many pairs of "LR" and "RL" compared to "LL" and "RR" like the "7 shuffles is enough" model suggests there should be. For some reason, when I did all this analysis last year, I was mostly thinking about how to ensure my MTG decks are sufficiently shuffled. I didn't really think about the implications for card counting. However, normal riffle shuffling seems to have less bias (but still present) than the mash shuffling I looked at and I think most casinos use machines for shuffling these days.
- Dylan16807 2y ago
  How fast things go badly is proportional to how well you can measure the bias, isn't it? If you need 2^200 hands to do so, good luck getting there. And a CSPRNG has to be robust to sharing every single bit so far with your adversary.
  - ilya_m 2y ago
    Exactly. > things go badly pretty quick. Dealing 2^200 hands, assuming that one hand takes 1ns, is more than ... pretty much any conceivable physical quantity one can think of. (Technically, the heat death of the universe takes longer than that but all card decks will be long gone, having been consumed by black holes.) This is a long-winded way of saying that cryptography with 2^256 security margin ought to be sufficient for all human-scale applications.
- omoikane 2y ago
  > if you don’t have more than 230 bits of entropy Should this be 226 instead of 230, since 2**225 < 52! < 2**226 ?
  - mlyle 2y ago
    I did round, but you probably need more than 226. Because 52! does not divide into any power of 2. Imagine if you had 5 possible hands, and 3 bits of entropy. Some hands are going to be twice as likely than others (pigeon hole principle). So if you have 4 bits more, the least common hands will be 31/32 as common as the most common hands.
pclmulqdq 2y ago
A Mersenne twister or another PRNG with a long sequence length is fine for deck shuffling. A CSPRNG is more comfortable. As to the idea that it's superstition not to trust CSPRNGs: sometimes, you want to eliminate the variable, and sometimes your CSPRNG is actually worth attacking. A lot of CSPRNGs also involve secret state, so if you are worried that this state might get exfiltrated, some paranoia is ok. The post here recommends using Intel's RDSEED, which is ironically trusted far less than /dev/urandom by most people who have a secret to keep or a process to protect.
- kurikuri 2y ago
  > The post here recommends using Intel's RDSEED, which is ironically trusted far less than /dev/urandom by most people who have a secret to keep or a process to protect. What? If security is a special consideration for some form of data, why would someone choose a non-physical noise source over a hardware-based noise source?
  - pclmulqdq 2y ago
    Trust. It's suspected that RDSEED is essentially backdoored based on the published structure of the RNG. TRNGs are allowed to use a cryptographic conditioning component on top of a non-full-entropy physical stream, and that is what Intel does, using a long-lived secret key. The output you see is actually the result of cryptographic postprocessing, which may be partially transparent to the entity that has the secret key. Intel has no published third-party audits of their silicon, and has a very close relationship with some three-letter agencies. Hence the concern. By contrast, urandom is completely open, and is reseeded relatively frequently with entropy. If both are effectively acting as a CSPRNG, the one with public attention and no secret key that can be handed to a third party is better.
- IAmLiterallyAB 2y ago
  What secret state do you mean? All PRNGs have state right? Which you need to keep secret if you don't want the sequence to be predictable. Is there something more I'm missing?

mlyle 2y ago

There are 52! possible decks of cards— if you don’t have more than 230 bits of entropy in your prng per deck shuffled things go badly pretty quick. You also tend to share deck state so far with the adversary. Shuffling cards is a surprisingly demanding prng application.

magicalhippo 2y ago
How many shuffled decks do you need to with 99% confidence determine if I used say Mersenne Twister or a hardware-based RNG? edit: I know MT has a rather large state, but it has some issues. Alternatively what about say one of the 128bit state PCG generators?
adgjlsfhk1 2y ago
Counterpoint, even if you only have 256 bits of entropy (which is common for many widely used PRNGs), you can prove that there's bias due to the pigeon hole principal, but finding a shuffle that is under-represented is computationally impossible.
- pvillano 2y ago
  I can say, infalsifiably, it will be computationally possible eventually
  - SAI_Peregrinus 2y ago
    Eventually, but long after the Sun has expanded into a red giant and burned the surface of the Earth off.
- deleted 2y ago
  [deleted]
slaymaker1907 2y ago
It’s almost certainly still good enough since it’s unlikely to be biased in ways that matter. Most hand shuffling methods have nasty biases as well. For standard riffle shuffling, there is often a bias in pulling from the pile opposite from the last pulled card (so alternating pairs of left and right). The model saying “7 shuffles is sufficient” as people like to quote presumes you pull from a pile only proportional to the size of the pile (so you get many fewer alternating runs).
- Harmohit 2y ago
  That is such an interesting idea! I wonder if someone has systematically studied hand shuffling biases and what consequences it has (or should have) for brick and mortar casinos
  - Zanni 2y ago
    Yes. Card counters (advantage players at blackjack) studied shuffle tracking. I haven't seen much good material published on it, but I played on a team with a math whiz (physicist) who ran the numbers. For the casino we were playing at the time, the last 20 or so cards would be distributed over the bottom half of a six-deck shoe. A strategic cut would bring those three decks to the front, and you could play with a slight advantage. Suppose you're at a full table and 12 of the last 20 cards are aces or tens (rare but possible). These get shuffled and cut into the first three decks, giving you a true count of four (12/3) for the first half of the shoe, which is significant. We never really put it into practice, though, since: 1) you have to track the count for the last 20 cards in addition to the regular count, 2) shuffles change, 3) dealers are inconsistent, 3) casinos use different shuffles, 4) the typical advantage is likely to be much smaller. My knowledge on this is at least 20 years out of date, though, so who knows?
    - slaymaker1907 2y ago
      The bias I saw would likely be difficult to exploit without studying the mathematics a lot more. It seems to pass several statistical tests, but the problem I found was more about independence. Let's call the two splits L for left and R for right and consider the resulting deck to be defined as a sequence of these letters indicating whether that card was taken from the left or right pile so in theory you can specify a shuffle uniquely like "LRRLLLLLLRRR...". This method of labeling shuffles has the advantage of being extremely easy to record and also makes the bias I found apparent where there are way too many pairs of "LR" and "RL" compared to "LL" and "RR" like the "7 shuffles is enough" model suggests there should be. For some reason, when I did all this analysis last year, I was mostly thinking about how to ensure my MTG decks are sufficiently shuffled. I didn't really think about the implications for card counting. However, normal riffle shuffling seems to have less bias (but still present) than the mash shuffling I looked at and I think most casinos use machines for shuffling these days.
Dylan16807 2y ago
How fast things go badly is proportional to how well you can measure the bias, isn't it? If you need 2^200 hands to do so, good luck getting there. And a CSPRNG has to be robust to sharing every single bit so far with your adversary.
- ilya_m 2y ago
  Exactly. > things go badly pretty quick. Dealing 2^200 hands, assuming that one hand takes 1ns, is more than ... pretty much any conceivable physical quantity one can think of. (Technically, the heat death of the universe takes longer than that but all card decks will be long gone, having been consumed by black holes.) This is a long-winded way of saying that cryptography with 2^256 security margin ought to be sufficient for all human-scale applications.
omoikane 2y ago
> if you don’t have more than 230 bits of entropy Should this be 226 instead of 230, since 2**225 < 52! < 2**226 ?
- mlyle 2y ago
  I did round, but you probably need more than 226. Because 52! does not divide into any power of 2. Imagine if you had 5 possible hands, and 3 bits of entropy. Some hands are going to be twice as likely than others (pigeon hole principle). So if you have 4 bits more, the least common hands will be 31/32 as common as the most common hands.

pclmulqdq 2y ago

A Mersenne twister or another PRNG with a long sequence length is fine for deck shuffling. A CSPRNG is more comfortable. As to the idea that it's superstition not to trust CSPRNGs: sometimes, you want to eliminate the variable, and sometimes your CSPRNG is actually worth attacking. A lot of CSPRNGs also involve secret state, so if you are worried that this state might get exfiltrated, some paranoia is ok. The post here recommends using Intel's RDSEED, which is ironically trusted far less than /dev/urandom by most people who have a secret to keep or a process to protect.

kurikuri 2y ago
> The post here recommends using Intel's RDSEED, which is ironically trusted far less than /dev/urandom by most people who have a secret to keep or a process to protect. What? If security is a special consideration for some form of data, why would someone choose a non-physical noise source over a hardware-based noise source?
- pclmulqdq 2y ago
  Trust. It's suspected that RDSEED is essentially backdoored based on the published structure of the RNG. TRNGs are allowed to use a cryptographic conditioning component on top of a non-full-entropy physical stream, and that is what Intel does, using a long-lived secret key. The output you see is actually the result of cryptographic postprocessing, which may be partially transparent to the entity that has the secret key. Intel has no published third-party audits of their silicon, and has a very close relationship with some three-letter agencies. Hence the concern. By contrast, urandom is completely open, and is reseeded relatively frequently with entropy. If both are effectively acting as a CSPRNG, the one with public attention and no secret key that can be handed to a third party is better.
IAmLiterallyAB 2y ago
What secret state do you mean? All PRNGs have state right? Which you need to keep secret if you don't want the sequence to be predictable. Is there something more I'm missing?