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 <>
Subject: PHP mt_rand() seed cracking


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:

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

Here are some recent publications:

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:

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";'

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:

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:

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

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).


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.