samedi 23 mai 2020

Is it possible to predict the next output for the str_shuffle function in PHP?

I'm doing a bit of a research on the str_shuffle() function and i was wondering can i predict the next output of the function if i know the seed?

Internals of str_shuffle()

 while (--n_left) {
     rnd_idx = php_rand();
     RAND_RANGE(rnd_idx, 0, n_left, PHP_RAND_MAX); // <-- on some versions of php i couldn't find this here
     if (rnd_idx != n_left) {
         temp = str[n_left];
         str[n_left] = str[rnd_idx];
         str[rnd_idx] = temp;
     }
 }

Where RAND_RANGE is:

#define RAND_RANGE(__n, __min, __max, __tmax) (__n) = php_mt_rand_range((__min), (__max))

With this information i concluded that it uses the Fisher-Yattes algorithm, so i wrote a little test script:

mt_srand(101); // seed it with a random value
echo str_shuffle("testcase"); // gives "acetsets"

By working backwards i concluded that the values of the rnd_idx were 2, 3, 2, 3, 0, 1, 0.

But when i try to print them to make sure using:

mt_srand(101);
$a = "testcase";
$c = strlen($a);
for($i = $c - 1;$i > 0;--$i)
    echo mt_rand(0,$i) . '<br>';

It gives me 0, 0, 3, 0, 0, 1, 1 which is not the same. What am i missing? I know it's possible to "break" the str_shuffle() because it uses the Mersenne Twister which doesn't produce cryptographically safe random numbers, but how?




Aucun commentaire:

Enregistrer un commentaire