Does (online) poker require cryptographically secure randomness?

Question

Here’s a quote from a reddit discussion:

… for poker [a cryptographically secure RNG] is completely unnecessary. If you have an appropriate unpredictable seed, and you are throwing away a lot of the randomness, MT is perfectly safe.

I’d normally write this off as ignorance, but this goes on:

I've actually implemented a real-money poker backend, and the company even had it certified

And since nobody lies on the internet, this makes me wonder. Said person expands on this in another part of the discussion:

[To prevent predictability] you would not use 624 consecutive values produced from [the MT generator]. If you want a real-money app. certified, one of the criteria is to throw away a large and unpredictable amount of the output of the PRNG.

You also don't know the specifics of how the PRNG was used to produce a shuffle. So, you have no way to map the cards you see on the table to a sequence from the PRNG.

You also don't know when the PRNG is reseeded.

One last thing. You need to store (2¹⁹⁹³⁷ − 1) * 4 bytes of data for lookup, in order to find the pattern you need to predict.

Except for the last paragraph, these arguments sounds suspiciously like security by obscurity. The last paragraph sounds less so, but somebody else in the discussion has claimed that the statement is untrue, and you don’t need such a big lookup table.

Just to clarify, I’m aware that MT19937 isn’t cryptographically secure (and so is the person I’m quoting). However, my assumption so far was that gambling (and poker) would require a cryptographically secure random source – and not just a secure seed – (a) to be tamper proof, and (b) for certification. Is this wrong?

Answer 1

Here is the cryptographer's point of view. The person you quote says: "you don't need a cryptographically secure PRNG", but what he actually claims is "when I use MT 19937 and do some mumbo-jumbo such as throwing away a large part of the output, it somehow becomes a cryptographically secure PRNG".

His comment about storing "(2¹⁹³³⁷-1)*4 bytes for lookup" is enough to demonstrate that he is not very clear in his head about what security, cryptography, randomness and unpredictability actually are. This figure is the "period"; the period was used in (very) older times as a measure of security, because known PRNG from that time had very small periods, to the point that repetition did occur in practice. This engendered a whole family of non-crypto PRNG where designers where trying to overawe their competitors by flourishing the longest possible period. This makes no real sense from a cryptographic point of view. Security of a PRNG is about unpredictability, and a very short period is an issue only because it allows future output to be predictable. AES used in CTR mode is a PRNG with a period of 2¹³⁵ (bits), a figure much lower than 2¹⁹³³⁷-1, and yet not a problem at all.

The "throwing away of large and unpredictable amount of output" also illustrates the confusion. Removing bits from the output may hide some state leakage from a weak PRNG; this can even turn a weak PRNG into a strong one, as studied with the shrinking generator. However, it does nothing about seed predictability; indeed, if some of the output is "thrown away", then there is a mechanism which decides what to keep and what to throw away, and that mechanism is also part of the PRNG. If all of this is seed with the current time, then exhaustive search on the possible "current time" values will be efficient (current time is not a secret) and will unravel the whole thing.

---

However we may argue that though MT is not cryptographically secure, this does not mean that making an effective attack is easy. There are three types of PRNG:

• The awfully weak algorithms, either through very poor processing (leaking the internal state), or predictable seed, or both. These are broken in practice.
• The "cryptographically strong" PRNG, which resist attacks even in the ludicrous conditions that academics assume (an academic will consider an algorithm as "broken" if it claims 128-bit security but offers only 2^123.4 resistance).
• The grey zone in between: broken as per academics, but a practical attack is not immediate.

With his Mersenne Twister, he is in the grey zone, and he believes that his voodoo manipulations will keep it that way. It is entirely plausible that he could also convince an auditor that voodoo works. This in no way implies that the algorithm is secure; only that an auditor was ready to sign a paper claiming that the algorithm fulfils some legal requirements. At that point, it is a good thing to remember that some other auditors found it fit to sign papers claiming that Enron was a financially sound and clean venture: this helps to put things into the right perspective.

From what he describes, chances are that the initial seed is time-based, and the actual security relies entirely on the non-publication of the algorithm details. That's security through obscurity at its best (or worst, depending from the point of view).

Answer 2

First of all, there's a very important thing: What do you mean when we say "required"? The game itself (online poker) doesn't really require that level of randomness. You can probably get away with plain old rand().

However, legal and regulated online poker games need to follow certain rules, one of which is that the RNG should be audited by an independent audit firm. That's the case in the United Kingdom. Auditing firms (PwC,EY, Cigital, Gaming Laboratories International) and regulatory bodies (Kahnawake Gaming Commission) in many places in the world have had and usually do handle cases like that.

Such auditing firms and regulatory bodies require the RNG to be of very high randomness, unbiased, and unpredictable. Now, what RNGs do we know that are easy to implement and use, and are suitable for such regulations? Well, you guess right; your good ol' trusted CSPRNG.

As @Ladadadada mentions, besides regulation and laws, it's in the game's operator’s best interest to make the game as fair as possible because unfairness and "crackability" will drive users away. Therefore, in order to achieve that level of fairness, you need high quality randomness and unpredictability provided by a CSPRNG.

With a quick Google session you'd find several highly-tested, scrutinized, and well-vetted CSPRNGs that can be taken as is, and used into your online poker project.

Answer 3

The guy is wrong when he states that a CSRNG was "completely unnecessary". He even confirms that when he says that you need an "unpredictable seed".

What means an unpredictable seed?

When I give you a reasonable amount of pseudo-random numbers derived from that seed, you shall not be able to compute the next number. Simple. From a mathematical point of view the security of such generators can be proven by a simple game.

I send you a sequence of numbers and you have to decide if they are completely random or derived by a function (F). If your average success rate is better than a half (+/- a neligible amount) you win.

You will find that your chances to win depend (at least) on the amount of input the function gets. If I used only a few bits of input than you can surely distinguish between complete rendomness and function output much better than a half.

Up to this point there is no way around a good seed. What about the magic throw-away?

Does throwing away some output make it more secure?

I find the statement to "throw away a large and unpredictable amount" somehow funny. What they do here is to skip portions of the function's output. But how many Bytes exactly? He states "a large and unpredictable amount". This basically means that you modify the function from above.

However, you are still at the point where you started. You play the game and try to distinguish between complete randomness and output of a new function (F'). After all there is an algorithm running and it has to decide exactly how many Bytes to skip. So this value is somehow computed an can be seen as an additional part of the original function.

What you can do?

As you can see throwing away an unpredictable amount of output does not make the function more secure. In contrast if you chose to throw away a completely random amount of bytes this colud lead to a more secure algorithm.

If an algorithm outputs the bits 0101010101... and so forth your chances to win the game are quite good. If I skip a random amount of output and send you one bit, then skip again another amount and send you one bit, and so on, what would it be? Your chances to win were your chances to predict the amount of skipped bits. In the end you would have to predict the randomness, and you chances to win would no longer be that good.

However, the secureness of my number generator benefits from skipping only under certain conditions, whose evaluation would go beyond this thread. Just to get the right impression: what would the skipping bring if my function outputs the bit "1" in 99% of the time and "0" only in 1%? You would find that even if I skip a random amount of bits, the statistical distribution is still constant.

Conclusion

You definitely would want real randomness in a poker game, for the seed or the skipping of output or both. But it is sufficient to use this expensive randomness as input for well defined functions that work as a CSPRNG.

Just for the record: You could create such a function that withstands all of the mentioned tests using cryptographic primitives in a way that the sequence is predictable if you know a secret key. Without knowledge of the secret key it looks so random, that your chances to win the game are roughly a half.