12

As we know, the Mersenne Twister is not crytographically secure:

Mersenne Twister is not cryptographically secure. (MT is based on a linear recursion. Any pseudorandom number sequence generated by a linear recursion is insecure, since from sufficiently long subsequencje of the outputs, one can predict the rest of the outputs.)

But many sources, like Stephan T. Lavavej and even this website. The advice is almost always (verbatim) to use the Mersenne Twister like this:

auto engine = mt19937{random_device{}()};

They come in different flavors, like using std::seed_seq or complicated ways of manipulating std::tm, but this is the simplest approach.

Even though std::random_device is not always reliable:

std::random_device may be implemented in terms of an implementation-defined pseudo-random number engine if a non-deterministic source (e.g. a hardware device) is not available to the implementation. In this case each std::random_device object may generate the same number sequence.

The /dev/urandom vs /dev/random debate rages on.

But while the standard library provides a good collection of PRNGs, it doesn't seem to provide any CSPRNGs. I prefer to stick to the standard library rather than using POSIX, Linux-only headers, etc. Can the Mersenne Twister be manipulated to make it cryptographically secure?

user5287986
  • 121
  • 1
  • 4
  • To downvoter, how can I improve my question? – user5287986 Sep 01 '15 at 10:33
  • Not downvoter (actually upvoted), but I think you should make the links clickable. – dandan78 Sep 01 '15 at 10:36
  • 12
    *Can the Mersenne Twister be manipulated to make it cryptographically secure?* No. – David Hammen Sep 01 '15 at 10:44
  • 1
    @dandan78 Ok. I even throw in protocol-less URLs for good measure – user5287986 Sep 01 '15 at 10:49
  • 1
    Links were broken since most of them don't work with https. Fixed now – user5287986 Sep 01 '15 at 11:18
  • 1
    @DavidHammen The link I used says: "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)." Can you elaborate or counterpoint? – user5287986 Sep 01 '15 at 11:24
  • Have you see this post? http://stackoverflow.com/questions/18323738/fast-pseudorandom-number-generator-for-cryptography-in-c – NathanOliver Sep 01 '15 at 12:00
  • @user5287986 The sequence "1 2 3 4 5 6" is almost secure after a Secure Hashing Algorithm (well, not really, because someone might guess that one). However, start at some unpredictable seed, and do the same, and determining which of `+1` or "apply mt" is more secure would require actual research (the answer might be both, neither, or either one.) Saying that "applying a secure hash makes it secure" is a bit of a misnomer: the security is independent of the mt. – Yakk - Adam Nevraumont Sep 01 '15 at 12:59
  • 1
    Whichever sequence of `mt` calls and hashes you choose to employ, I can pre-compute that sequence offline for every possible seed. Then, I can observe the output of your RNG, compare it to my tables, and figure out the seed you are starting with. After that, I can predict future outputs of your RNG. In other words, applying a deterministic function to a predictable sequence results in a predictable sequence. – Igor Tandetnik Sep 01 '15 at 14:38
  • 1
    You've probably seen this [Wikipedia article](https://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator#Designs_based_on_cryptographic_primitives) which mentions: "A cryptographically secure hash of a counter might also act as a good CSPRNG in some cases." – Buddy Sep 02 '15 at 03:47
  • You may have to implement your own if you want a good CSPRNG. For one example, see the [ISAAC](https://en.wikipedia.org/wiki/ISAAC_(cipher)) cipher. – owacoder Oct 07 '15 at 12:07
  • 2
    @owacoder "implement your own" is almost antithetical to "cryptographically secure" – Panagiotis Kanavos Oct 08 '15 at 09:08
  • @PanagiotisKanavos - By "implement your own" I meant "use something other than the STL." – owacoder Oct 08 '15 at 12:58

1 Answers1

6

Visual Studio guarantees that random_device is cryptographically secure and non-deterministic: https://msdn.microsoft.com/en-us/library/bb982250.aspx

If you want something faster or cross platform, you could for example use GnuTLS: http://gnutls.org/manual/html_node/Random-number-generation.html It provides random numbers of adjustable quality. GNUTLS_RND_RANDOM is what you want I think.

As several people already said, please forget about MT in cryptographic contexts.

user1531083
  • 750
  • 6
  • 15