[<prev] [next>] [day] [month] [year] [list]
Message-ID: <20131104021121.GA27143@openwall.com>
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:
http://www.openwall.com/php_mt_seed/
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):
http://www.openwall.com/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
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
