3 ms·
I know next to nothing about crypto, but just a bit of Googling came up with: "Mersenne Twister is not cryptographically secure. (MT is based on a linear recur
by paulbaumgart 17y ago
I know next to nothing about crypto, but just a bit of Googling came up with:
"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 subsequence of the outputs, one can predict the rest of the outputs.)
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)."
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/efaq.html http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/efaq.html <-- And since that's the "Mersenne Twister Home Page", I'll take his word for it. :-)
So, looking at the PHP source code for mt_rand():
PHPAPI php_uint32 php_mt_rand(TSRMLS_D)
{
/* Pull a 32-bit integer from the generator state
Every other access function simply transforms the numbers extracted here */
register php_uint32 s1;
if (BG(left) == 0) {
php_mt_reload(TSRMLS_C);
}
--BG(left);
s1 = *BG(next)++;
s1 ^= (s1 >> 11);
s1 ^= (s1 << 7) & 0x9d2c5680U;
s1 ^= (s1 << 15) & 0xefc60000U;
return ( s1 ^ (s1 >> 18) );
}
Which doesn't seem like it qualifies as a cryptographically secure implementation; I don't see any Secure Hashing going on.
- tptacek 17y agoYou can't just hash a cryptographically insecure RNG and turn it into a cryptographically secure RNG. =) If you need secure random numbers in PHP, the best advice I have off the top of my head is to take it from /dev/urandom.
- paulbaumgart 17y agoWait, so do I misunderstand what Makoto Matsumoto is saying, or is he wrong?
- tptacek 17y agoI don't think he's wrong, but I think you may be following his logic and overshooting the right conclusion; he's saying it's possible to use MT as a component of a CSPRNG, not that MT itself can become a CSPRNG. A good place to get your bearings on this is Kelsey et al's "Yarrow" paper. My (unqualified) opinion is that the Yarrow CPSRNG is awkward, but the paper is a good survey on what design tactics go into a modern CSPRNG --- in particular, entropy collection and refreshing, both of which PHP's MT lack.
- swolchok 17y agoSurely, you meant either "secure pseudorandom numbers" or "/dev/random".</pedantry>
- there 17y agono, he meant /dev/urandom. /dev/random is reserved for hardware random generating devices on some operating systems (which may not return anything). /dev/urandom is a device that will always output pseudo random data without blocking when the entropy pool runs low.
- swolchok 17y agoYes, so /dev/urandom is not suitable if you want "secure random numbers", because its output may be pseudorandom.
- tptacek 17y agoWhat a weird little subthread. urandom and random are both CSPRNGs --- the same CSPRNG, in fact --- the only difference between them is whether the device blocks to fetch more entropy. Go ahead and use /dev/random if that question freaks you out. Either way, don't rely on mt_random.