How to reverse engineer str_shuffle (PHP) to get its mt_rand outputs

Question

$output = str_shuffle("12345");

E.g. $output is now 25134 How do I find out what numbers came out of mt_rand() to allow for the shuffle I want to know this because I want the seed of mt_rand() and str_shuffle() uses mt_rand() which is not cryptographically secure as it uses Mersenne Twister (Wikipedia) I know shuffle for python is using the Fisher Yates shuffle (Wikipedia) but I have no idea how it works in php. you can get the seed used if you have 624 outputs using mersenne-twister-recover (GitHub) or you can brute force the seed with untwister (GitHub)

Answer 1

According to PHP 7.2.7 sources, the str_shuffle function uses php_string_shuffle which does

while (--n_left) {
    rnd_idx = php_rand();
    RAND_RANGE(rnd_idx, 0, n_left, PHP_RAND_MAX);
    if (rnd_idx != n_left) {
        temp = str[n_left];
        str[n_left] = str[rnd_idx];
        str[rnd_idx] = temp;
    }
}

So I guess you would like to know the intermediate values of rnd_idx (since php_rand() is an alias of php_mt_rand()).

But RAND_RANGE is a macro defined as #define RAND_RANGE(__n, __min, __max, __tmax) (__n) = php_mt_rand_range((__min), (__max)) so the 1st value of the php_rand() is already instantly lost.

Hence, you won't get the list of all intermediate mt_range() values.

Still, knowing that the algorithm there seems to be at each round, swap the current letter with a random letter before in the input string; the 1st round takes the last letter as the current one; the next round takes the letter previous current letter as the new current letter then you can get the mt_rand value by reasoning backward.

If ABCD is the input value and BADC is the result, then it means the values were 2;2;0 (ABCD => ABDC => ABDC => BADC) but you still don't know the value of the "lost" calls to php_mt_rand. So the sequence of mt_rand was actually ?;2;?;2;?;0 which matches the seed 4 and 25: if you do mt_srand(4); echo str_shuffle('ABCD'); then you'll get BADC and same if your seed is set to 25. You would need a pretty long chain of unique characters to get a sequence long enough to match only one seed.