Hacker News Reader

Comment by pclmulqdq | Hacker News Reader

A Mersenne twister or another PRNG with a long sequence length is fine for deck shuffling. A CSPRNG is more comfortable.

As to the idea that it's superstition not to trust CSPRNGs: sometimes, you want to eliminate the variable, and sometimes your CSPRNG is actually worth attacking. A lot of CSPRNGs also involve secret state, so if you are worried that this state might get exfiltrated, some paranoia is ok.

The post here recommends using Intel's RDSEED, which is ironically trusted far less than /dev/urandom by most people who have a secret to keep or a process to protect.

View on HN

> A Mersenne twister ... is fine for deck shuffling

It isn't. Please don't do that! Mersenne Twister is fully reversible given its 624 consecutive outputs (see, for instance, this pretty good write-up: https://blog.ollien.com/posts/reverse-mersenne-twister). In other words, someone who can observe 624 outputs can reconstruct its entire output sequence forward and backward.

You're right that you wouldn't want to use any non-cryptographic PRNG for gambling games of any significant stake. Many low-stakes games will use them, relying on having many different players connected to one result source to protect themselves.

However, "624 consecutive outputs" is not the way to think about it, because those outputs are truncated to narrow integers. A single shuffled deck leaks about 230 bits of information, and backing out the state of a Mersenne twister needs several thousand bits of information.

This is very interesting, thank you! When I was implementing random shuffling I used xoroshiro128+ instead of Mersenne twister and felt pretty good about it but only because it was used for randomness needed for Monte Carlo simulations, not for gambling games where there are potential adversaries looking to break it. Are you aware of how that one (xoroshiro128+) or other pseudo random generators fare against adversaries?

Don't use a non-CSPRNG if you worry about adversaries. CSPRNGs are only ca. 10 times larger and roughly as fast if you can use SIMD.

According to [1], you only need 4 outputs to predict xoshiro. Predicting PCG is a bit more difficult, but still on the level of "exercise for cryptography students" [2].

[1]: https://www.pcg-random.org/posts/a-quick-look-at-xoshiro256....

[2]: https://hal.science/hal-02700791/document

What secret state do you mean? All PRNGs have state right? Which you need to keep secret if you don't want the sequence to be predictable. Is there something more I'm missing?

CSPRNGs keep the state secret so an observer can't tell the next output from the previous ones. Most other PRNGs have a sequence that can be backed out from observing their outputs.

> The post here recommends using Intel's RDSEED, which is ironically trusted far less than /dev/urandom by most people who have a secret to keep or a process to protect.

What? If security is a special consideration for some form of data, why would someone choose a non-physical noise source over a hardware-based noise source?

Trust. It's suspected that RDSEED is essentially backdoored based on the published structure of the RNG. TRNGs are allowed to use a cryptographic conditioning component on top of a non-full-entropy physical stream, and that is what Intel does, using a long-lived secret key. The output you see is actually the result of cryptographic postprocessing, which may be partially transparent to the entity that has the secret key.

Intel has no published third-party audits of their silicon, and has a very close relationship with some three-letter agencies. Hence the concern.

By contrast, urandom is completely open, and is reseeded relatively frequently with entropy. If both are effectively acting as a CSPRNG, the one with public attention and no secret key that can be handed to a third party is better.

Reply on news.ycombinator.com