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) 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.
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)$ ]:
- The output of the "golden standard" cryptographic random source
- 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. 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.
² 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.