Return to Answer

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) allow calling libraries or external services which, depending on runtime environment, often conveniently provide entropy without a size limitation, and at a rate way more than sufficient for the application.

¹ Many if not most modern programming languages have no RNG. For example, there's no RNG in the Java language specification. While most Java environments have a RNG, that's in some Java library, these differ with environments, and not all provide SecureRandom (much less a proper one). Even if we count the JCL APIs as part of Java, SecureRandom is explicitly specified to deffer to providers that often are part of the underlying OS.

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.

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

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 modular addition modulo $n$ for a primitive that generates a random integer in $[0,n)$ ).

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.

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)$ ]:

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.

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

• Bound to output of 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 system consisting of the PRNG plus device running the deterministic procedure.

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 (first, or $k^\text{th}$ for fixed $k$) shuffle generated could be any of the $52!$ shuffles, say because such claim was made. If we go the simplest route, 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 use the size of the PRNG. That could be the case in a code audit.

The actual problem is not making a PRNG with a large state (virtually all modern languages allow to build one). The problem is seeding the RNG 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 teached or used they are) allow calling external services or libraries which, depending on runtime environment, often conveniently provide entropy without a size limitation, and at a rate way more than sufficient for the application.

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 wait when it lacks entropy. From this standpoint, /dev/random gives a stronger insurance than /dev/urandom.

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.

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) allow calling libraries or external services which, depending on runtime environment, often conveniently provide entropy without a size limitation, and at a rate way more than sufficient for the application.

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.