john-users - PHP mt_rand() seed cracking

Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [day] [month] [year] [list]
Date: Fri, 21 Sep 2012 00:16:21 +0400
From: Solar Designer <solar@...nwall.com>
To: john-users@...ts.openwall.com
Subject: PHP mt_rand() seed cracking

Hi,

This is not exactly a JtR topic, but it is related.

There's a lot of talk lately about PHP applications and PHP proper
often suffering from insufficient randomness, using PRNGs (often with
small and/or predictable seeds and/or internal state) for purposes where
cryptographically secure random numbers would be needed.  Here's the
start of the relevant thread on oss-security:

http://www.openwall.com/lists/oss-security/2012/08/09/7

(click "thread-next" for a lot more of it).

Here are some recent publications:

https://www.usenix.org/conference/usenixsecurity12/i-forgot-your-password-randomness-attacks-against-php-applications
http://blog.ptsecurity.com/2012/08/not-so-random-numbers-take-two.html

In this context, I got curious of whether and why PHP's mt_rand() is
really significantly more difficult to "crack" (find the seed given a
series of "random" numbers) than an LCG PRNG (which was "crackable" in
under a second on one CPU back in 1990s).  Well, yes, it appears that
mt_rand() is in fact hundreds of times "stronger", yet is "crackable" on
one modern CPU chip in one minute (without use of precomputation yet).
Here's a program I wrote:

http://download.openwall.net/pub/projects/php_mt_seed/

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 (php_mt_seed version 2.1 here):

$ 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 63310249 seeds per second
seed = 658126103
Found 1, trying 1207959552 - 1241513983, speed 63343447 seeds per second
seed = 1234567890
Found 2, trying 4261412864 - 4294967295, speed 63347894 seeds per second
Found 2

real    1m7.798s
user    9m1.942s
sys     0m0.008s

In one minute of real time (on an FX-8120 CPU, using 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 in this case).

Gifts implemented the same thing in OpenCL:

https://github.com/Gifts/pyphp_rand_ocl
https://github.com/Gifts/pyphp_rand_ocl/tree/SpeedyOCL

His SpeedyOCL branch achieves similar performance (and even 10% better
than mine in his test of both on a Core i5-2500) on CPUs (with Intel's
OpenCL SDK) and several times better performance on GPUs.

Finally, here's a far more generic cracker (but slower - 20 minutes on
CPU?) by George Argyros:

http://www.openwall.com/lists/oss-security/2012/09/20/8
https://github.com/GeorgeArgyros/Snowflake

(I think it'd be possible to bring the time down to 1 minute if the
generality is implemented by different means.)

<obvious>
Once the PRNG seed is known, further "random" numbers may be predicted
reliably.  Additionally, the seed itself might reveal information
(depending on what was used as the seed).
</obvious>

Alexander
Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.