php_mt_seed went beyond PoC

[Nytro]

Date: Mon, 4 Nov 2013 06:11:22 +0400

From: Solar Designer <solar@...nwall.com>

To: announce@...ts.openwall.com

Subject: [openwall-announce] php_mt_seed went beyond PoC

Hi,

With the functionality added in October, our php_mt_seed PHP mt_rand()

seed cracker is no longer just a proof-of-concept, but is a tool that

may actually be useful, such as for penetration testing. It is now a

maintained project with its own homepage:

php_mt_seed - PHP mt_rand() seed cracker

Changes implemented in October, leading up to version 3.2, include

addition of AVX2 and Intel MIC (Xeon Phi) support, and more importantly

support for advanced invocation modes, which allow matching of multiple,

non-first, and/or inexact mt_rand() outputs to possible seed values.

The revised README file provides php_mt_seed usage examples (both

trivial and advanced), as well as benchmarks on a variety of systems

(ranging from quad-core CPU to 16-core server and to Xeon Phi):

php_mt_seed: README

With the new AVX2 support, php_mt_seed searches the full 32-bit seed

space on a Core i7-4770K CPU in 48 seconds. On Xeon Phi 5110P, it does

the same in 7 seconds. In advanced invocation modes, the running times

are slightly higher, but are still very acceptable.

For example, let's generate 10 random numbers in the range 0 to 9:

$ 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

and find the seed(s) based on these 10 numbers using our HPC Village

machine's CPUs (2x Xeon E5-2670):

[solar@...er php_mt_seed-3.2]$ GOMP_CPU_AFFINITY=0-31 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 8 8 0 9 4 4 0 9 5 5 0 9 8 8 0 9

Pattern: EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10

Found 0, trying 1207959552 - 1241513983, speed 222870766 seeds per second

seed = 1234567890

Found 1, trying 4261412864 - 4294967295, speed 222760735 seeds per second

Found 1

615.57user 0.00system 0:19.28elapsed 3192%CPU (0avgtext+0avgdata 3984maxresident)k

0inputs+0outputs (0major+292minor)pagefaults 0swaps

We found the correct seed (and there turned out to be only one such

seed) in under 20 seconds.

What if we did not know the very first mt_rand() output (had only 9

known values out of 10, in this example)? Let's specify "0 0 0 0" to

have php_mt_seed skip the first output:

[solar@...er php_mt_seed-3.2]$ GOMP_CPU_AFFINITY=0-31 time ./php_mt_seed 0 0 0 0 6 6 0 9 4 4 0 9 1 1 0 9 1 1 0 9 2 2 0 9 8 8 0 9 4 4 0 9 5 5 0 9 8 8 0 9

Pattern: SKIP EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10

Found 0, trying 469762048 - 503316479, speed 203360193 seeds per second

seed = 485860777

Found 1, trying 637534208 - 671088639, speed 203036371 seeds per second

seed = 641663289

Found 2, trying 1073741824 - 1107296255, speed 202975770 seeds per second

seed = 1091847690

Found 3, trying 1207959552 - 1241513983, speed 203018412 seeds per second

seed = 1234567890

Found 4, trying 3388997632 - 3422552063, speed 203177316 seeds per second

seed = 3414448749

Found 5, trying 4261412864 - 4294967295, speed 203117867 seeds per second

Found 5

675.08user 0.00system 0:21.14elapsed 3192%CPU (0avgtext+0avgdata 4000maxresident)k

0inputs+0outputs (0major+291minor)pagefaults 0swaps

We found 4 extra seeds, and the speed is slightly lower (by the way,

there's much room for optimization in handling of cases like this -

maybe later). The original seed value was found as well.

Other (and possibly more) mt_rand() outputs could be specified and/or

skipped as well, and/or ranges of possible values could be specified.

The mt_rand() output range does not have to be 0 to 9, too - any other

range supported by PHP's mt_rand() is also supported in php_mt_seed.

Enjoy, and please spread the word.

Alexander

Sursa: announce - [openwall-announce] php_mt_seed went beyond PoC