5
$\begingroup$

Suppose, as an example, we want to use the Fisher-Yates algorithm along with a pseudorandom number generator to shuffle a deck of cards. We know that there are limitations with respect to the internal state of the PRNG and its ability to reach the distinct permutations of the deck. If, for example, the PRNG can only be seeded with $2^{32}$ bits, then it cannot possibly produce all the $52!$ distinct permutations. In addition, even if we could meet the 226 bits needed for a 52-card deck, the distribution may not be uniform.

Now, suppose we switch and swap the PRNG with a CSPRNG. How do these limitations apply? In practice, they're seeded and reseeded frequently, depending on implementation, but this is generally done behind the scenes. Since CSPRNGs are PRNGs, my initial thoughts would lead me to believe that they will suffer the same limitations. Yet, if we used a PRNG with the same seed, but continuously draw numbers from it, we could reach additional permutations.

Over yonder in response to this question, one answer suggests that a cryptographically strong source of unbiased numbers will reach the desired permutations. Would you agree?

Finally, I used a deck of cards as an example. I'm curious about list sizes with respect to this question. I know that with PRNGs, the seed bits must increase to accommodate larger lists.

$\endgroup$
  • $\begingroup$ The important difference between CSPRNGs and regular PRNGs is that the former are designed not to leak a single bit of their internal state when attackers are given arbitrary amounts of their output, whereas this is not a consideration regular PRNGs have to deal with. In terms of the total entropy of pseudorandom output, a CSPRNG cannot be any better than a regular one: this entropy can never be greater than the entropy it is (re)seeded with. That's a hard upper bound, but whether it is achieved by any real (CS)PRNG is a good question. $\endgroup$ – DiscobarMolokai Jun 6 '16 at 5:51
  • $\begingroup$ What I actually mean to express: in theory at least, the distributions of CSPRNGs are not necessarily more uniform than the ones of good PRNGs. It's just that CSPRNGs have to prevent their state from becoming known, as that could cause cryptosystems keyed off them to fail horribly. $\endgroup$ – DiscobarMolokai Jun 6 '16 at 6:01
3
$\begingroup$

If, for example, the PRNG can only be seeded with $2^{32}$ bits, then it cannot possibly produce all the $52!$ distinct permutations. In addition, even if we could meet the 226 bits needed for a 52-card deck, the distribution may not be uniform.

This is true, but a good PRNG (even non-cryptographic) will give you a random sample from a uniform distribution. That means that until you get close to the square root of the seed size, your sampling will still look random. With a 32-bit seed you can easily go over that limit, but with larger seeds you will not.

Yet, if we used a PRNG with the same seed, but continuously draw numbers from it, we could reach additional permutations.

Yes, but even then the state size will limit which outputs are possible.

Now, suppose we switch and swap the PRNG with a CSPRNG. How do these limitations apply? In practice, they're seeded and reseeded frequently, depending on implementation, but this is generally done behind the scenes.

If you take a sequence from a CSPRNG that is longer than the state size, without reseeding in between, it cannot produce every possible output value. However, it is guaranteed to be indistinguishable from random.

For example, suppose you have a CSPRNG based on AES CTR. A single AES key will produce $2^{128}$ different 128-bit outputs, but as long as you see (significantly) fewer than $2^{64}$ you do not notice this. As long as the RNG is reseeded often enough and you do not use it enough that both keys and inputs would repeat (impossible in practice), you are fine.

So yes, there are $52!$ different ways to shuffle cards, but since there is no chance that you will look at them all, it is sufficient to generate deck orders from a set of e.g. $2^{128}$ that are themselves a random selection of all possible ones.

$\endgroup$
  • $\begingroup$ It is a compliance requirement in many regulated gambling jurisdictions that every game state be reachable with probability equivalent to any physical game being simulated (even by implication). So if your casino game simulates 8-deck blackjack, you must have a random number generator which can has $(8*52)!$ in possible states. So a "so many states you'll never notice" solution often doesn't meet the application requirement for shuffling. $\endgroup$ – rmalayter Jul 5 '16 at 22:03
  • $\begingroup$ @rmalayter, no CSPRNG will do in that case, since any finite state CSPRNG will have outputs with (very slightly) different probabilities. E.g. a CSPRNG with a 256-bit state would very likely give you every possible one-deck order, but their probabilities would necessarily differ. $\endgroup$ – otus Jul 6 '16 at 4:34
  • $\begingroup$ Laws are often written by those with a terrible understanding of math. But hashing a 4-kbit seed and 128-bit counter using SHA-256 would seem to meet this requirement if you unbiased the output as required by Fisher-Yates. Physical blackjack shuffling machines used at tables get certified somehow. $\endgroup$ – rmalayter Jul 6 '16 at 8:21
  • $\begingroup$ @rmalayter, that would not have equal probabilities of outputs (and is wasteful) - the 4k seed effectively just gets reduced to a 256-bit IV. But yeah, I don't know anything about such certifications. $\endgroup$ – otus Jul 6 '16 at 8:24
  • $\begingroup$ I agree SHA-256 would effectively nullify the large state space; perhaps a Keccak variant with even larger capacity.... But I too know of these requirements only anecdotally from a friend who actually worked for a gaming machine manufacturer. The RNG mechanisms were obviously highly scrutinized by regulators. $\endgroup$ – rmalayter Jul 6 '16 at 8:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.