In-depth understanding of the security of mt_rand() random numbers in PHP

mt_rand() uses the mersennetwister algorithm to return random integers. Everyone knows this, but the following article mainly introduces you to the relevant information about the security of mt_rand() random numbers in PHP. The article introduces it in very detail. Friends can refer to

Preface

I dug a lot of security vulnerabilities related to mt_rand() some time ago, and they were basically errors. Understand the usage of random numbers. Here I would like to mention another pitfall in the manual of the official website of PHP. Let’s take a look at the introduction of mt_rand(): Chinese version ^cn English version ^en. You can see that the English version has an extra yellow Caution warning

This function does not generate cryptographically secure values, and should not be used for cryptographic purposes. If you need a cryptographically secure value, consider using random_int(), random_bytes(), or openssl_random_pseudo_bytes() instead.

Many domestic developers probably read the Chinese version of the introduction and used mt_rand() in the program to generate security tokens, core encryption and decryption keys, etc., leading to serious security issues. .

Pseudo-random number

mt_rand() is not a true random number generating function. In fact, most programming languages The random number functions in all generate pseudo-random numbers. The difference between true random numbers and pseudo-random numbers will not be explained here. You only need to briefly understand a little bit

Pseudo-random is generated by a determinable function (commonly used linear congruence) through a seed (commonly used clock) of pseudo-random numbers. This means that if you know the seed, or the random number that has been generated, it is possible to obtain information about the next random number sequence (predictability).

Simply assume that the function that generates random numbers internally in mt_rand() is: rand = seed (i*10) seed is the random number seed, and i is the number of times this random number is called. function. When we know the two values ​​​​of i and rand at the same time, we can easily calculate the value of seed. For example, rand=21 and i=2 are substituted into the function 21=seed (2*10) to get seed=1. Isn't it very simple? After we get the seed, we can calculate the value of rand when i is any value.

PHP's automatic seeding

From the previous section we already know that every time mt_rand() is called, it will be based on the seed and the current Called a number of times i to calculate a pseudo-random number. And the seed is automatically seeded:

Note: Since PHP 4.2.0, there is no longer a need to use srand() or mt_srand() to seed the random number generator, because it is now done automatically by the system.

Then the question arises, when does the system automatically complete the seeding? If mt_rand() is automatically seeded every time, then there is no point in cracking the seed. The manual does not give detailed information on this point. I searched all over the Internet but couldn't find a reliable answer. I had to go through the source code^mtrand:

PHPAPI void php_mt_srand(uint32_t seed)
{
 /* Seed the generator with a simple uint32 */
 php_mt_initialize(seed, BG(state));
 php_mt_reload();

 /* Seed only once */
 BG(mt_rand_is_seeded) = 1; 
}
/* }}} */

/* {{{ php_mt_rand
 */
PHPAPI uint32_t php_mt_rand(void)
{
 /* Pull a 32-bit integer from the generator state
 Every other access function simply transforms the numbers extracted here */

 register uint32_t s1;

 if (UNEXPECTED(!BG(mt_rand_is_seeded))) {
 php_mt_srand(GENERATE_SEED());
 }

 if (BG(left) == 0) {
 php_mt_reload();
 }
 --BG(left);

 s1 = *BG(next)++;
 s1 ^= (s1 >> 11);
 s1 ^= (s1 << 7) & 0x9d2c5680U;
 s1 ^= (s1 << 15) & 0xefc60000U;
 return ( s1 ^ (s1 >> 18) );
}

You can see that every time mt_rand() is called, it will first Check to see if it has been seeded. If it has been sown, generate random numbers directly, otherwise call php_mt_srand to sow. That is to say, during each php cgi process, only the first call to mt_rand() will automatically seed. Next, random numbers will be generated based on this first sown seed. Among the several operating modes of php, except CGI (each request starts a cgi process and closes it after the request is completed. The php.ini environment variables must be re-read every time, resulting in low efficiency, and it should not be used much now) , basically, after one process processes the request, the standby waits for the next one, and it will not be recycled until multiple requests are processed (it will also be recycled after timeout).

Write a script to test it

Test results: (windows phpstudy) 
apache 1000 requests
nginx 500 requests
Of course, this test only confirms the number of requests that apache and nginx can handle in one process. Let’s verify the conclusion just now about automatic seeding. ：
##
Judged by pid , when a new process starts, randomly obtain the output of mt_rand() on one of the two pages: 
old_pid:972 new_pid:7752 1513334371 2014450250 1319669412 499559587 117728762 1465174656 1671827592 1703046841 464496438 1974338231 46646067 981271768 1070717272 571887250 922467166 606646473 134605134 857256637 1971727275 2104203195
Take the first random number 1513334371 to blast Seeds: 
smldhz@vm:~/php_mt_seed-3.2$ ./php_mt_seed 1513334371 Found 0, trying 704643072 - 738197503, speed 28562751 seeds per second seed = 735487048 Found 1, trying 1308622848 - 1342177279, speed 28824291 seeds per second seed = 1337331453 Found 2, trying 3254779904 - 3288334335, speed 28811010 seeds per second seed = 3283082581 Found 3, trying 4261412864 - 4294967295, speed 28677071 seeds per second Found 3
 Exploded 3 possible seeds, the number is very small. Manually test one by one: 
Output:
The first 20 digits are exactly the same as those obtained by the above script. The confirmed seed is 1513334371. With the seed, we can calculate the random number generated by calling mt_rand() any number of times. For example, I generated 21 digits in this script, and the last digit is 1515656265. If you have not visited the site after running the script just now, you can see the same 1515656265 by opening http://localhost/pid2.php. 
So we come to the conclusion: 
php's automatic seeding occurs when mt_rand() is called for the first time in the php cgi process. Regardless of the page visited, as long as the request is processed by the same process, they will share the same initially automatically sown seed. 
php_mt_seed##
We already know that the generation of random numbers depends on a specific function, which was assumed above to be rand = seed (i*10) . For such a simple function, we can of course directly calculate (orally) a solution (group), but the function actually used by mt_rand() is quite complex and cannot be inverted. An effective cracking method is to exhaustively enumerate all seeds, generate a random number sequence based on the seed, and then compare it with a known random number sequence to verify whether the seed is correct. php_mt_seed^phpmtseed is such a tool. It is very fast and it only takes a few minutes to run the 2^32-bit seed. It can directly explode possible seeds based on the output of a single mt_rand() (example above). Of course, it can also explode seeds that limit the MIN MAX output like mt_rand(1,100) (in the example below) useful). 
Security issues
 Having said so much, why are random numbers unsafe? In fact, there is nothing wrong with the function itself. The official also clearly states that the generated random numbers should not be used for security encryption purposes (although the Chinese version manual does not write this). The problem is that the developers don't realize that this is not a truly random number. We already know that seeds can be exploded from a known sequence of random numbers. In other words, as long as there is an output random number or its derivative value (reversible random value) in any page, then the random number in any other page will no longer be a "random number". Common examples of outputting random numbers include verification codes, random file names, etc. Common random numbers are used for security verification, such as retrieving password verification values, such as encryption keys, etc. An ideal attack scenario: 
 In the dead of night, waiting for apache (nginx) to take back all PHP processes (to ensure that the next visit will be re-seeded), visit the verification code page once, reverse the random number based on the verification code characters, and then Explode random number seeds based on random numbers. Then visit the password retrieval page, and the generated password retrieval link is based on random numbers. We can easily calculate this link and retrieve the administrator's password...XXOO
Example
PHPCMS MT_RAND SEED CRACK leads to authkey leak. Yuniu wrote it better than me, just read his. 
Discuz x3.2 authkey leak is actually similar. The official patch has been released, and those who are interested can analyze it themselves. 


The above is the detailed content of In-depth understanding of the security of mt_rand() random numbers in PHP. For more information, please follow other related articles on the PHP Chinese website!