PHP predicting array_rand

manpreet Best Answer 2 years ago

Given the following PHP code (assuming PHP 5.6.x):

$chars = array_merge(range('A','Z'), range(0,9));
$tokens = array();
for ($i = 0; $i < 1000; $i++) {
    $token = '';
    for($j = 0; $j < 12; $j++) {
        $token .= $chars[array_rand($chars)];
    }
    $tokens[] = $token;
}

If I have one token from the array, but don't know from which index nor what the seed was, I'm trying to understand the probability of predicting other values in the array.

I've got very little experience with the c programming language, but looking at the src it appears the randomness comes from php_rand, which in turn proxies php_mt_rand, which as I understand it is an implementation of Mersenne Twister. I managed to find another question on here with an answer that explains quite well some details on mt_rand, including the fact that with 2496 bytes of consecutive data, we can recover the state. I've actually seen several articles about attacking mt_rand in this manner, but unfortunately I haven't come across any that dealt specifically with 'truncated' random values (i.e. with applied min / max bounds discarding bits from the returned value) and I'm not sure how that interacts with the probability. The articles I've read have also dealt specifically with cracking the state, rather than whether we can reduce probability of predicting a set of consecutive return values without actually fully cracking the state (maybe this is just a dumb question, and you can't).

Assuming I can validate if a 'guess' is in the array, does knowing one token actually significantly narrow the probability below testing the complete C(36,12) set?

Apologies if any of my use of mathematical terminologies are incorrect, I've not studied Math since I finished my Computing Science degree 10 years ago. Consequently the use of Layman's terms in any answers will be appreciated.