README

	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>