> 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 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.
> 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 (first, or $n^\text{th}$ for fixed $n$) shuffle generated could be any of the $52!$ shuffles. That could be because such claim was made. If we go the simplest route, it could be rationally proven such claim is untrue. 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.
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 wait when it lacks entropy. 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
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.
___
¹ Many if not most modern _programming languages_ have no RNG. For example, there's no RNG in the [Java _language_ specification][1]. 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][2] as part of Java, `SecureRandom` is explicitly [specified][3] 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][4] 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.
[1]: https://docs.oracle.com/javase/specs/jls/se8/html/index.html
[2]: https://docs.oracle.com/javase/8/docs/api/allclasses-frame.html
[3]: https://docs.oracle.com/javase/8/docs/api/java/security/SecureRandom.html#SecureRandom--
[4]: https://docs.oracle.com/javase/8/docs/technotes/guides/security/StandardNames.html#SecureRandom