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