Perfect shuffle possible with limited raw entropy?

Question

I am trying to shuffle a standard 52-card deck in a perfect way (every outcome should be possible at an equal chance). I am not, at this point, concerned with cryptanalysis attacks against it.

I have run into some problems/questions that are probably answered in cryptographic theory:

1. Most PRNGs run off some sort of internal state. A deck of cards has 52! shuffles, which is a 220+ bit number. Is it possible to generate all shuffles with a PRNG that has 64, 128 or 160-bit internal state? My intuition says no. Even though to shuffle the deck I only need 52 small random integers, a PRNG with internal state size below 52! probably cannot generate all the different 52 number sequences needed. Is this true or am I completely wrong?

2. In case I am right above, does that mean I cannot generate a true shuffle in most modern programming languages? Java's SecureRandom only has 128bit internal state and even /dev/rand uses a SHA-1 based PRNG on MacOS (160bits), so even using the "golden standard" cryptographic random source it isn't going to be enough. What are my options? What about JavaScript.. what are my options in the browser?

3. The option I came up with is to use CPU's built-in RDSEED command to get 256 bits of a really random seed, then I would like to use a PRNG with 256 bit internal state to shuffle the cards. Is that a sensible choice? What's the simplest way? Some sort of SHA-256 hash-based PRNG?

Answer 1

Is it possible to generate all shuffles with a PRNG that has 64, 128 or 160 bit internal state?

No, for restriction of "possible .. with" to a deterministic procedure using the Pseudo RNG output as sole input, and:

• Bound to output a single shuffled sequence per run. To generate all shuffles, $\lceil\log_2(52!)\rceil=226$ bits of PRNG internal state are required.
• Or bound to use strictly less than $\lceil\log_2(52!)\rceil-160=66$ bits of memory between output of shuffles (for appropriate account of memory).

This is proven by counting the possible states of the deterministic system consisting of the PRNG plus device running the shuffling procedure.

Does that mean I cannot generate a true shuffle in most modern programming languages?

No. It means that a single instance of a built-in PRNG with that 160-bit limitation can't be used, should we require that the shuffle generated could be any of the $52!$ shuffles, say because such claim was made. If we used such PRNG, irrespective of how it was seeded and security, it could be rationally proven such claim is untrue. But, for a secure and properly seeded PRNG and shuffling procedure, such proof can't be by examination of the shuffles produced (even with a 128-bit internal PRNG state). The proof must rely on the design characteristics of the PRNG. That could be the case in a code audit.

The difficult problem is not making a PRNG with a large state (virtually all modern languages allow to build one). The problem is seeding it with enough entropy. This is not always possible, much less built "in" the programming language¹. However, many modern programming languages (most if you weight in how commonly used/taught they are) come with libraries or allow using external libraries/services which often conveniently provide entropy without a size limitation, and at a rate way more than sufficient for the application.

For example, on a Unix system, a language allowing file I/O often can read /dev/random, which promises to provide true randomness and pause towards that goal if necessary. Using that should be OK, but historically, it has not always. There are anecdotes of embedded devices which generate a key on first boot and end up with a guessable key.

Java's SecureRandom only has 128bit internal state

That's a dubious assertion. Things depend both on how SecureRandom is used², and on the environment.

even /dev/rand uses a SHA-1 based PRNG on MacOS (160bits)

As long as /dev/random appropriately re-seeds itself using true entropy, being based on a 160-bit hash or even having a 160-bit state does not imply the (theoretical anyway) limitation of being a PRNG with a 160-bit state. This generator promises to reseed with fresh entropy as needed, and wait when it lacks entropy. It is not (or not supposed to be) a PRNG, that is deterministic after seeding. From this standpoint, /dev/random gives a stronger insurance than /dev/urandom.

Even using the "golden standard" cryptographic random source it isn't going to be enough. What are my options?

When a paranoia damper is needed (e.g. to convince a gambler who does not trust that $2^{128}$ is large enough), or in order to formally fulfill a promise that all $52!$ possible shuffles can be generated with (nearly) equal probability, the recommendable way is to combine using XOR [or using modular addition modulo $n$ for a primitive that generates a random integer in $[0,n)$ ]:

1. The output of the "golden standard" cryptographic random source
2. The output of a custom RNG that is in no way influenced by 1.

With a flawless implementation of that, the resulting RNG is at least as good as the best of the two. This architecture minimizes the (still very practically real) probability that trying to improve on 1 leads to a disaster. Additionally, 1 should be carefully checked to be a Cryptographically Secure True RNG, or a Cryptographically Secure Pseudo RNG seeded from a TRNG with enough entropy.

Now comes the problem of making the custom RNG 2. One possibility if to make a CSPRNG with a 512-bit state initialized as the SHA-512 hash of multiple sources:

• The CPU's built in RDSEED, if there is such thing available in the programming environment, in which case that's a sensible choice as an extra entropy source. Same for RDRAND.
• Current time to the highest accuracy available, perhaps at different moments in the execution. Same for the job's CPU usage.
• The output(s) of some instance of the "golden standard" cryptographic random source with said instance discarded after use³.
• For code with a user interface, keypresses and mouse movements (value or position, and sampling of the above sources at each change).
• Whatever is easily available, tends to vary, and is even mildly hard for an attacker to guess: compilation date/time, address of static variable/local variable/code, process id, output of some system command (on Windows, wmic process).

For the PRNG 2 itself, one possibility is HMAC-SHA-512(seed, counter) truncated to 32 bytes, where the key seed is the above hash, and the message counter is incremented for each 32 bytes. Techniques to turn this into a uniform generator in $[0,n)$ are well-known.

Note: I'm not claiming that this will generate all shuffles with the exact same probability, or even that it it is possible to positively demonstrate that it is close to that.

---

¹ Many if not most modern programming languages have no RNG. For example, there's no RNG in the Java language specification. If we count the JCL APIs as part of Java, SecureRandom is there. It is explicitly specified to deffer to providers that often are part of the underlying OS.

² JCL's SecureRandom supports plenty of providers and RNGs, typically including a provider with NativePRNGBlocking which promises to output continuously reseeded entropy, straight from or equivalent to /dev/random.

³ There is nothing preventing repeatedly creating a SecureRandom object, using it to generate say 16 bytes, then disposing of this object. There is at least the potential that the multiple chunks obtained are independently seeded.

Answer 2

I will take a different take vs previous answers. Let's say we really have only 128 bits of entropy at our disposal does that prevent us from applying a determinstic algorithm on shuffling a deck of cards?

From a pure counting perspective surely, a determinstic function on 128 bits of input can not have 52! different possible outputs.

But If we use cryptographicly secure PRNG seeded on 128 bit entropy source we can easily shuffle a deck of cards so that it is indistinguishable from a truely random shuffle. Even if I shuffle this way a billion decks and you crunch the data on your computer for many years you still won't be able to tell the difference between this limited seed shuffle and a truely random shuffle.

So I ask what is the virtue of a truely uniformly random shuffle?

Answer 3

A PRNG with insufficient states can also achieve complete shuffling.

The way to do this is to do multiple rounds of shuffling. Reseeding seeds in each round. The most important thing is that entropy must be sufficient.

A Python library that implements complete shuffling https://github.com/fsssosei/complete_shuffle