Detailed explanation of safe examples of mt_rand() random numbers in PHP

I discovered a lot of security vulnerabilities related to mt_rand() some time ago, which were basically caused by misunderstanding the usage of random numbers. Here I would like to mention another pitfall of the PHP official website manual. Take a look at the introduction to mt_rand(): Chinese version ^cn English version ^en. You can see that the English version has an extra yellow Caution warning. 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 introduction in the article is very detailed. Friends who need it can refer to it. For reference, let’s learn with the editor below.

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., causing serious security problems.

Pseudo-random number

mt_rand() is not a true random number generating function. In fact, the random number functions in most programming languages ​​generate pseudo-random numbers. number. 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) where seed is the random number seed, and i is the number of times this random number function is called. 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

We already know from the previous section that every time mt_rand() is called, a pseudo-random number will be calculated based on seed and the current number of calls i. And the seed is automatically seeded:

Note: Since PHP 4.2.0, there is no 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 could only look at 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 > 18) );
}

You can see that every time mt_rand() is called, it will first check whether it has been sown. 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

<?php //pid.php
echo getmypid();

<?php //test.php
$old_pid = file_get_contents(&#39;http://localhost/pid.php&#39;);
$i=1;
while(true){
 $i++;
 $pid = file_get_contents(&#39;http://localhost/pid.php&#39;);
 if($pid!=$old_pid){
 echo $i;
 break;
 }
}

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:

<?php //pid1.php
if(isset($_GET[&#39;rand&#39;])){
 echo mt_rand();
}else{
 echo getmypid();
}

<?php //pid2.php
echo mt_rand();

<?php //test.php
$old_pid = file_get_contents(&#39;http://localhost/pid1.php&#39;);
echo "old_pid:{$old_pid}\r\n";
while(true){
 $pid = file_get_contents(&#39;http://localhost/pid1.php&#39;);
 if($pid!=$old_pid){
 echo "new_pid:{$pid}\r\n";
 for($i=0;$i<20;$i++){
  $random = mt_rand(1,2);
  echo file_get_contents("http://localhost/pid".$random.".php?rand=1")." ";
 }

 break;
 }
}

Judged by pid, when a new process starts, two randomly obtained The output of mt_rand() on one of the 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 explode the 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 one by one Test:

<?php mt_srand(735487048);//手工播种
for($i=0;$i<21;$i++){
 echo mt_rand()." ";
}

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 get 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 (set of) solution, 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) (useful in the examples below).

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 causing authkey leakage Yu Niu writes better than me , it’s enough to look at his

Discuz x3.2 authkey leak is actually similar. The official patch has been released, and those who are interested can analyze it themselves.

Related recommendations:

PHP’s true and false random numbers

php’s rand() function for random number generation

Example of JavaScript implementation of random number deduplication generator

The above is the detailed content of Detailed explanation of safe examples of mt_rand() random numbers in PHP. For more information, please follow other related articles on the PHP Chinese website!