Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

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 (219937 − 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?

share|improve this question
    
By the way, this seemed the most appropriate website to ask this question but if it doesn’t fit, I’d ask for it to please be moved to a more appropriate site. –  Konrad Rudolph Feb 11 at 9:10
1  
I don't understand why anybody would risk a weaker PRNG. CSPRNGs are fast and just as easy to use as MT. Certainly easier to use than throwing away part of MT's output in the hope of making it secure that way. –  CodesInChaos Feb 11 at 9:57
    
I don't have access to Reddit right now, so I can't see the original context for the numbers, but can you double-check your number formatting in the third quote? It's a minor nitpick, but something like (219937 ** 4) - 1 would make more sense given the context. (Of course, if he actually did mean 879,744, that right there tells you all you need to know about whether someone is lying on the Internet. . .) –  Jonathan Garber Feb 11 at 14:44
    
@JonathanGarber Right, of course. I lost the exponent when copying the unformatted text. –  Konrad Rudolph Feb 11 at 16:12
1  
This week I read this VERY relevant article: lauradhamilton.com/random-lessons-online-poker-exploit –  kiBytes Feb 11 at 17:54

3 Answers 3

up vote 20 down vote accepted

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 "(219337-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 2135 (bits), a figure much lower than 219337-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 2123.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).

share|improve this answer
3  
mumbo-jumbo - lol +1 –  fr00tyl00p Feb 11 at 20:33

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.

share|improve this answer
    
When I say "required" , I mean in order to be unhackable (for commercial use). rand clearly isn't that, it's trivial to predict and thus to exploit the game. –  Konrad Rudolph Feb 11 at 11:05
1  
The poker company has a strong incentive to avoid predictable numbers regardless of regulations and audits because the cheats will drive the other players away. How cheating affects other players will depend very much on which game is being played. In poker, money is mostly won from other players rather than the house. –  Ladadadada Feb 11 at 11:30
1  
@KonradRudolph Since your goal is high randomness, unpredictability, and non-bias, then it's only natural to go with a CSPRNG. I'll state that in the answer. –  Adnan Feb 11 at 11:32

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.

share|improve this answer
    
I think what he meant by throwing away a large amount was just that he’d re-seed the MT13997 after a certain time – this may be deterministic, it needn’t be unpredictable! – before producing 624 consecutive values, at which point the generator becomes predictable. –  Konrad Rudolph Feb 11 at 20:21
    
The thing is that you do NOT need an unpredictable scheme. It only has to look like it :-) Think of the function being the first round of MT again and again with different seeds. You would not be able to distinguish between that and complete randomness. –  fr00tyl00p Feb 11 at 20:29
    
That’s my point: the claim isn’t (or doesn’t seem) that it needs to be (or look) unpredictable. The claim is that it can be completely predictable and publicly known. The only reason for throwing away random data, as far as the claim goes, is to avoid MT’s predictability after 624 consecutively generated values, at which point the generator is known to be predictable. –  Konrad Rudolph Feb 11 at 20:31
    
Allright. Seems like the part "throw away a large and unpredictable amount" is misleading. –  fr00tyl00p Feb 11 at 20:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.