bugspotting

Exploiting mt_rand()


It's well known that mt_rand() is not a cryptographically secure function. It's fairly trivial to crack a seed when enough input is provided. But what do you do when there's no visibility of the output?


Implementation

Implemented using the Mersenne Twister algorithm, mt_rand() exists within PHP's standard library.

The fatal flaw of this algorithm is that it's 32 bit seed. A seedspace this small can be brute-forced using tools like php_mt_seed. In addition, its entropy is low, meaning the values used to generated the seed are not very 'random'.



The following is the seed generation algorithm:

long GENERATE_SEED() {    return (time(0) * getpid()) ^ (1000000.0 * php_combined_lcg())}


Traditional Exploitation

Typically, in CTFs and similar scnearios you will see a scenario like the following:



Leaking μs and PIDs

Seeding

x = 10x++