1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Just run the program once for each possible seed and check if the output matches. Should be affordable since there are only 2^32 different seeds. $\endgroup$ – CodesInChaos Aug 6 '16 at 12:30
  • $\begingroup$ The only way to check "if the output matches" is seeing the array, no? We can only validate if a value is in the array and doing so is 'slow' say 1 second for a lookup. I did consider generating 1000 tokens with every seed value in order to check how many sets contained the start token. But some quick calculations suggest my Macbook Pro would take ~121 days to generate that many tokens using PHP. Certainly possible with modern cloud computing but not ideal. I also wondered about pre-computing the token sets and storing, but unless I messed up the Math that terabytes of data. $\endgroup$ – Peter O'Callaghan Aug 6 '16 at 14:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.