lepiaf / Php_mt_seed

This is a PHP mt_rand() seed cracker. In the most trivial invocation mode, it finds possible seeds given the very first mt_rand() output after possible seeding with mt_srand(). With advanced invocation modes, is also able to match multiple, non-first, and/or inexact mt_rand() outputs to possible seed values.

Here's a sample run. First, generate a sample "random" number (using PHP 5.3.x in this case):

$ php5 -r 'mt_srand(1234567890); echo mt_rand(), "\n";' 1328851649

Now build and run the cracker:

$ make gcc -Wall -march=native -O2 -fomit-frame-pointer -funroll-loops -fopenmp php_mt_seed.c -o php_mt_seed $ time ./php_mt_seed 1328851649 Found 0, trying 637534208 - 671088639, speed 64855972 seeds per second seed = 658126103 Found 1, trying 1207959552 - 1241513983, speed 64874304 seeds per second seed = 1234567890 Found 2, trying 4261412864 - 4294967295, speed 64861687 seeds per second Found 2

real 1m6.218s user 8m49.165s sys 0m0.020s

In one minute of real time on an FX-8120 CPU, using AMD XOP's vectorized fused multiply-add instructions, it found the original seed, another seed that also produces the same mt_rand() output, and it searched the rest of the 32-bit seed space (not finding other matches).

Intel AVX2 (no integer fused multiply-add, but 256- rather than 128-bit vectors) provides a slightly higher speed, on a Core i7-4770K CPU:

$ time ./php_mt_seed 1328851649 Found 0, trying 637534208 - 671088639, speed 89667258 seeds per second seed = 658126103 Found 1, trying 1207959552 - 1241513983, speed 89811119 seeds per second seed = 1234567890 Found 2, trying 4261412864 - 4294967295, speed 89808490 seeds per second Found 2

real 0m47.826s user 6m19.100s sys 0m0.008s

Testing on a bigger machine (two E5-2670 CPUs, using 128-bit AVX):

$ OMP_NUM_THREADS=16 time ./php_mt_seed 1328851649 Found 0, trying 637534208 - 671088639, speed 237885898 seeds per second seed = 658126103 Found 1, trying 1207959552 - 1241513983, speed 238256321 seeds per second seed = 1234567890 Found 2, trying 4261412864 - 4294967295, speed 238200830 seeds per second Found 2 287.87user 0.00system 0:18.03elapsed 1596%CPU (0avgtext+0avgdata 3296maxresident)k

Somehow 32 threads (to match the logical CPU count) results in a lower speed with this specific build on this specific machine; YMMV.

Matching of multiple outputs, including inexact:

$ php5 -r 'mt_srand(1234567890); for ($i = 0; $i < 10; $i++) { echo mt_rand(0, 9), " "; } echo "\n";' 6 6 4 1 1 2 8 4 5 8

On the same machine as above:

$ OMP_NUM_THREADS=16 time ./php_mt_seed 6 6 0 9 6 6 0 9 4 4 0 9 1 1 0 9 1 1 0 9 2 2 0 9 7 8 0 9 4 4 0 9 0 0 0 0 8 8 0 9 Pattern: EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 RANGE-FROM-10 EXACT-FROM-10 SKIP EXACT-FROM-10 Found 0, trying 1207959552 - 1241513983, speed 205435297 seeds per second seed = 1234567890 Found 1, trying 1409286144 - 1442840575, speed 205435297 seeds per second seed = 1414163717 Found 2, trying 1879048192 - 1912602623, speed 205585141 seeds per second seed = 1893625793 Found 3, trying 2785017856 - 2818572287, speed 205536373 seeds per second seed = 2804485451 Found 4, trying 3791650816 - 3825205247, speed 205509529 seeds per second seed = 3810276440 Found 5, trying 4261412864 - 4294967295, speed 205567431 seeds per second Found 5 333.60user 0.00system 0:20.90elapsed 1596%CPU (0avgtext+0avgdata 3472maxresident)k

Notice how "7 8 0 9" specifies a range of possible values (7 to 8), and "0 0 0 0" means to skip (ignore) this one mt_rand() output value. In our case, this uncertainty results in several additional possible seeds being found.

To build php_mt_seed for Xeon Phi, install Intel's C compiler and run "make mic". To run php_mt_seed on Xeon Phi, copy Intel C compiler's OpenMP runtime library (such as libiomp5.so) to the Xeon Phi card, e.g. using scp. Then SSH in to the card and run a command like:

$ LD_LIBRARY_PATH=. time ./php_mt_seed 1328851649 Found 0, trying 536870912 - 805306367, speed 440058124 seeds per second seed = 658126103 Found 1, trying 1073741824 - 1342177279, speed 511305630 seeds per second seed = 1234567890 Found 2, trying 4026531840 - 4294967295, speed 579357099 seeds per second Found 2 real 0m 7.60s user 28m 45.01s sys 0m 3.78s

This is on a Xeon Phi 5110P, running 240 threads (as it should).

Advanced invocation modes work too, but the performance impact of the non-vectorized portions of code is higher than on regular CPUs:

$ LD_LIBRARY_PATH=. time ./php_mt_seed 6 6 0 9 6 6 0 9 4 4 0 9 1 1 0 9 1 1 0 9 2 2 0 9 7 8 0 9 4 4 0 9 0 0 0 0 8 8 0 9 Pattern: EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 RANGE-FROM-10 EXACT-FROM-10 SKIP EXACT-FROM-10 Found 0, trying 1073741824 - 1342177279, speed 348617475 seeds per second seed = 1234567890 Found 1, trying 1342177280 - 1610612735, speed 356015193 seeds per second seed = 1414163717 Found 2, trying 1879048192 - 2147483647, speed 365573578 seeds per second seed = 1893625793 Found 3, trying 2684354560 - 2952790015, speed 372309925 seeds per second seed = 2804485451 Found 4, trying 3758096384 - 4026531839, speed 377318914 seeds per second seed = 3810276440 Found 5, trying 4026531840 - 4294967295, speed 378078107 seeds per second Found 5 real 0m 11.40s user 44m 38.16s sys 0m 1.67s

All of the above benchmarks are on CPUs running at stock clocks, with turbo boost and HT enabled (where applicable). Compiler versions vary (gcc 4.6.x to pre-4.9.0 snapshots; icc 14.0.0), and so do Linux distributions and kernel versions (which affects how threads are scheduled across the logical CPUs). And yes, all of these are on Linux.