3
$\begingroup$

I want to create an online roulette game. Is it OK if the PRNG is seeded only once, when the user starts the game, or is it recommended to re-seed sometimes during game? Maybe just seeded once a day on the server and every players would get a next random number without re-seeding? How would you do? How do they do it at online casinos?

Please note that the following edit does not contain any relevant information regarding the original question. It is maintained because the given answers have been updated to reflect the additional information contained herein. Most - if not all - of the answers do not agree on the security of using the Mersenne Twister for generating secure random numbers.

EDIT (in response to comments & answers)

Everybody says I should use a CSRNG.I understand why MT is not cryptographically secure.
But guys, maybe you forget that we reduce the range, you forget that for a roulette I need numbers from 0 to 36 only.

MT can generate $2^{32}$ different numbers. Sharing these possible numbers between the roulette numbers uniformly, we can have $(2^{32})/37$ different numbers for each roulette number. To each number belongs one state number. MT for generating the next number, uses the numbers with these indexes: $i$, $i+1$ and $i+397$. That means we have $(2^{32})/37 * (2^{32})/37 * (2^{32})/37$ possibilities to generate the next state. If you want to crack my RNG knowing that it's not C-secure, you have a super-fast computer, and it takes only 1 second to calculate $(2^{32})/37$ possibilities, then the whole thing will still take for a very very long period of time, and you will get a huge amount of possible values for the next state.

Given a small amount of output, it is relatively straightforward to compute all future outputs.

It's simply not true, because you have to calculate all 624 states if you want to be able to predict all future states, and you can see only the results from 0 to 36. (I don't want to explain it now, but actually we need even more (much more) then 624 states to get only one number for one state, if we have a reduced range.) But let's say you want to crack the RNG and you ask your friends to calculate different parts of the states , and you together can finish it quite quickly, then I have a trick: when you spin the wheel of the roulette, I generate two numbers, I use one for the roulette, and I discard the other one. The RNG is still uniformly distributed, and you can never have the state with the index i+1 (because I discarded it), and it becomes impossible for you to find out the state of the MT. (Generating the second random number can happen while the wheel is spinning, so we don't lose much time.) If I am right and it works, it can solve the seeding problem too. Does this argument hold?

EDIT 2 (after getting new comments)

Reason of editing: The comments and the highest rated answer on this site make the visitor think that Mersenne twister can't be modified to get secure output.

Cryptographically secure modification of Mersenne twister from Mr. Matsumoto's website – he is one of the two creaters of Mersenne twister. Check the C codes on this site, the modification is that you can seed the algorithm with an array of seeds.

An other solution to make Mersenne twister cryptographically secure (written by Mr. Matsumoto):

To make it secure, you need to use some Secure Hashing Algorithm with MT. For example, you may gather every eight words of outputs, and compress them into one word (thus the length of the output sequence is 1/8 of the original one).

On this forum we have a long argument about my statement: if we hide many results of Mersenne twister randomly and the range of outcoming integers is limited, then these modifications make MT cryptographically secure. If my statement is correct, you don't need an array of seeds and this method can be more efficient then using hashing algorithms.

Warning: I didn't do cryptoanalysis, I just tried to prove that it's secure by arguing about it as you can learn from comments below. Do not use this method if you are not sure it will work. Nonetheless, the following statement is correct from my point of view: “Mersenne-twister can be used for a roulette game if you modified it properly. (Although we recommend to use a CSPRNG.) Can be seeded daily by a good quality seed.”

Improve this question
$\endgroup$
29
  • 5
    $\begingroup$ Wow. There's a pretty impressive amount of misconception shown here. All I can say is: You are not qualified to write a casino game. Don't do it. There is specific technical knowledge required to do this right, and you do not have it. Try to find someone more qualified to do this aspect of design, because your instincts are leading you astray, your reasoning is wrong, your conclusion is wrong (and worse, you seem convinced that you are right). $\endgroup$
    – D.W.
    Commented Dec 19, 2013 at 0:47
  • 8
    $\begingroup$ Why do you want to use a MT when there are plenty of strong and fast standard CSPRNGs? AES-CTR can output gigabytes of data per second on a modern CPU. What can be simpler than calling a function "Give me n cryptographically secure bytes*? $\endgroup$
    – CodesInChaos
    Commented Dec 19, 2013 at 15:00
  • 9
    $\begingroup$ You're a beginner who has no experience in cipher design and cryptoanalysis. You're inventing your own stream cipher which has seen no cryptoanalysis and hope that it's secure. Why do you think that's a good idea? $\endgroup$
    – CodesInChaos
    Commented Dec 19, 2013 at 15:04
  • 8
    $\begingroup$ It's regrettable that the question as-is seems to imply that it's OK to do whatever the OP suggested. A shame for future visitors who may not have the insight of actually checking the rest of the thread, and end up using a homebrewed, brittle, and perhaps profoundly insecure PRNG as though it were a CSPRNG. I also like that you dismiss the entire field of cryptanalysis as if you were too good for it and just assume all your arguments are correct. Seriously, it's cool to be creative for experiments, but for a real project, no less an ONLINE CASINO GAME, you WANT to use best practices. NOT THIS. $\endgroup$
    – Thomas
    Commented Dec 22, 2013 at 13:52
  • 6
    $\begingroup$ Please note that Stack Exchange sites are not discussion sites, but Question-and-answer sites. Repeatedly editing a question to ask different things in reaction to answers it not really useful – better create a new follow-up question (which still should be able to stand on its own). $\endgroup$
    – Paŭlo Ebermann
    Commented Dec 22, 2013 at 17:23

4 Answers 4

Reset to default
23
$\begingroup$

You don't want to use something like the Mersenne Twister for gambling. It is not cryptographically secure.

Given a small amount of output, it is relatively straightforward to compute all future outputs. These algorithms are designed for things like Monte-Carlo simulations and things of that ilk.

A better option is to select a 128-bit key at random and run AES in counter-mode. Another option is simply to pipe input from /dev/urandom.

Either of these will give you a secure stream of bits you can use for your gaming application.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ For $s$-bit security, the output of an $n$-bit cipher in counter mode should be less than about $2^{(n-s)/2}$ blocks. If we set $s=80$, that makes "AES in counter-mode" good for a mere $16$ million blocks. $\endgroup$
    – fgrieu ♦
    Commented Dec 18, 2013 at 16:53
  • 3
    $\begingroup$ @fgrieu: you might want to rethink that statement, it sounds much stronger than what I think you really meant. You appear to be worried about repeated output blocks (or the lack of them with CTR mode); With 16 million blocks, a truly random source has a probability circa $2^{-80}$ of having a collision somewhere; AES-CTR has 0 probability. While a distinguisher with advantage $2^{-80}$ may violate semantic security, I can't think of a practical security issue with it. $\endgroup$
    – poncho
    Commented Dec 19, 2013 at 17:12
  • $\begingroup$ @poncho: right, the output of AES-CTR is fine for most practical purposes, even though the distinguisher that I consider (no repeated output blocks) makes it technically not a CSPRNG. However, for certification purposes (of security devices, or one-armed bandits), who knows what kind of (admittedly pointless) red ink could be raised by not using a CSPRNG, where one is prescribed? And for data encryption, the ability for an eavesdropper to distinguish constant plaintext from changing plaintext (which could translate to: idle link from active link) is close to a practical attack. $\endgroup$
    – fgrieu ♦
    Commented Dec 19, 2013 at 18:03
8
$\begingroup$

Quoting Poncho's answer:

Well, the chief vulnerability is that if an attacker is given a large enough sample of Mersenne Twister output, he can then predict future (and past) outputs. This is a gross violation of the properties that a cryptographically secure random number generator is supposed to have (where you're supposed to not even be able to tell if the random bit string could have been produced by the RNG in question).

In other words: you should not use something like the Mersenne Twister for your project.

For a RealLife™ example of what can go wrong if you do, you might want to read the article "How We Learned to Cheat at Online Poker: A Study in Software Security" (September 28, 1999) by Brad Arkin, Frank Hill, Scott Marks, Matt Schmid, Thomas John Walls, and Gary McGraw Reliable Software Technologies Software Security Group.

What you need is a cryptographically secure random number generator. There are a multitude of those available, so there is practically no reason for you to use anything else for your “casino” purposes. Implementing a secure and fair system is not overly difficult… and your players will demand it.

EDIT as a reply to your edit

You are missing the point. MT is predictable as soon as someone observes only a tiny part of the period. After that, reconstructing the whole period merely takes a blink of an eye. Check my related question which talks about the MWC — which has a has near-record period… more than 1033000 times as long as that of the Mersenne Twister. Yet, also MWC would fail to provide the RNG security needed for your project. The main point you need is "unpredictability" & non-CSRNGs do not provide that.

Also, an attacker does not need 624 consecutive states to break the Mersenne Twister… so dropping numbers won't save you. (Also note that the provided link is showing merely one of many ways to reconstruct the period).

Addendum

Since you seem to be fixed on your decision to use nothing but the Mersenne Twister, I thought it might be interesting for you to know some pitfalls related to it's seeding.

Python seeds the Twister with 256 bits (32 bytes) of “real” randomness (read from /dev/urandom if available). This means that, theoretically, it would be enough to know a few output bytes to restore the whole state, but an attacker would need an efficient attack on the seeding algorithm since 32 bytes is pretty much for a brute-force attack.

Other implementations however use much less randomness to seed their random number generators! PHP for example seems to use only 32 bits for seeding mt_random as it's mt_srand seeding function only accepts an int. In this case an attacker might find it easier to use a brute-force attack on the seed.

As you did not specify the programming language you are planning to use, I can only give you a general warning that — depending on the programming language and implementation — you'll probably want to reseed more frequently than just once a day, to minimize the chances of successful brute-force attacks.

Improve this answer
$\endgroup$
7
  • $\begingroup$ "MT is predictable as soon as someone observes only a tiny part of the period." It's true only if the range is not limited. "Also, an attacker does not need 624 consecutive states to break the Mersenne Twister" It's also true only if the range is not limited. $\endgroup$
    – user10949
    Commented Dec 18, 2013 at 21:36
  • 2
    $\begingroup$ @Greg To be honest, I do not understand why you are willing to take any risk if there are ample secure and fast solutions available. Online poker wasn't the only casino field that failed by simply using the wrong kind of RNGs… regular RNGs instead of a CSRNGs. $\endgroup$
    – e-sushi
    Commented Dec 18, 2013 at 21:42
  • $\begingroup$ Your answer is correct that I could use CSRNGs, but I'm more confident with regular RNGs, I know how fast or slow they are and I can use them more efficiently. So if I can do with MT, I will do with that, it's simpler for me. If it's more suitable for someone else to use CSRNGs, then they can use that. It's also interesting that Mersenne twister is the number-one recommended RNG for gambling at a reputable company: itechlabs.com.au/pages/rngtesting.html I appreciate your answers. $\endgroup$
    – user10949
    Commented Dec 18, 2013 at 22:06
  • 1
    $\begingroup$ @Greg Well, when it comes to finding “recommended” RNGs , I tend to look at NIST and FIPS 140-2 style testing… just like most gaming companies (for example: PokerStars RNG certification). Btw: the link you provided merely shows “a non-exclusive list” of “well known public domain RNG algorithms”. It is neither a top-6 list, nor does it state any algorithm being better or more preferred than the other ones that are listed, and there are no specific security statements related to the listed RNGs either… (guess why) $\endgroup$
    – e-sushi
    Commented Dec 18, 2013 at 22:27
  • $\begingroup$ I like this argument:). I'm flexible, if my statement is wrong, I will admit it, but please give a mathematical explanation. "and there are no specific security statements related to the listed RNGs either… (guess why)" guess: because you can modify the RNG to make it more or less secure, hahh:) Like I modified it by dropping every second random numbers to make it more secure. $\endgroup$
    – user10949
    Commented Dec 18, 2013 at 22:45
4
$\begingroup$

I'd rather add this as a comment. Alas, I lack the reputation for that.

I'm a programmer, not a cryptography expert, but for some strange reason I like to lurk here regardless. The cryptography aspect aside (others are much better at that) I'd like to focus on the programming perspective, and why your reasoning is wrong.

  • First of all: lurking here taught me that it's exceedingly easy to create something that appears secure at first sight but is fundamentally flawed. Don't be clever, it'll probably turn out to be the opposite. You're playing Roulette with your system's security..
  • You state that you prefer MT because 'it's simpler for me'. Note that you don't need to be a mechanic to drive a car. If you take any crypto library (as Erwan points out) you'll be generating pseudo-random numbers with a few lines of code. That's simple in my book.
  • Regardless of whether dropping every other number is secure (which I highly doubt because elements in the state array are not independent) you've also halved the effective performance of MT. Thus, the 'performance benefit argument' becomes much weaker and you may as well switch to a CS algorithm.
  • In addition to the previous point: I highly doubt that a CSPRNG would be a bottleneck in the system.

To conclude: regardless of why you think it would be a good idea to use MT, there's no reason to not use a better alternative. If you are absolutely sure that your reasoning is correct, post a proof and put on a helmet.

Improve this answer
$\endgroup$
6
  • $\begingroup$ You can see people just say "you are wrong because MT is not secure", without thinking about the algorithm. I really liked your previous comment about the states of MT, because you tried to prove I am wrong and you didn't just say "Use CSPRNG". "there's no reason to not use a better alternative." true. I don't say anyone should use a modified MT instead of CSPRNG. I am just curious it can work or not. I am that kind of person who likes trying ideas and thinking about it, not just using things what other people created earlier. $\endgroup$
    – user10949
    Commented Dec 19, 2013 at 20:06
  • 1
    $\begingroup$ @Greg "...not just using things what other people created earlier." You know that the Mersenne Twister was created by "other people" too, don't you? ;p (Only teasing!) $\endgroup$
    – Trina
    Commented Dec 20, 2013 at 23:35
  • $\begingroup$ OMG, did you read what we wrote earlier??? it's not about Mersenne twister, it's about the modification of Mersenne twister. (if it's a joke, it's a bad one) $\endgroup$
    – user10949
    Commented Dec 21, 2013 at 10:45
  • $\begingroup$ @Greg Unless I missed something, you didn't ask about the modification of the Mersenne Twister — you asked when to re-seed the MT and if it's secure to truncate it's output. That indeed has nothing to do with a modification of Mersenne Twister itself. I can only guess that's what she was pointing at with that obviously joking comment. But hey, please don't get angry at me now — it's not my comment; I'm only trying to help. $\endgroup$
    – e-sushi
    Commented Dec 22, 2013 at 9:01
  • $\begingroup$ @Greg Btw.: I've just added an Addendum to my answer (which specifically considers the fact that you want to use the Mersenne Twister) giving a little heads-up on MT's seeding. Hope it helps. $\endgroup$
    – e-sushi
    Commented Dec 22, 2013 at 9:31
3
$\begingroup$

You need a CSPRNG. And yes, a good CSPRNG should mix some new random data in the pool (reseed) periodically.

Here are a few options:

  • SecureRandom in Java
  • RNGCryptoServiceProvider in .Net
  • openssl_random_pseudo_bytes() or mcrypt_create_iv() in PHP
  • RAND_bytes() from OpenSSL
  • /dev/urandom on some Unix-like systems
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.