Executive Summary

The function make_keys() calls make_prime() which in turn invokes entropyarray() to get the initial seed for finding a prime.

entropyarray() does not utilize enough sources to be cryptographically secure, and the sources it does use are not independent variables: they rely either on the same shared underlying PHP random number generator (rand(), mt_rand(), str_shuffle()), or on the system clock.

These values can be guessed by an attacker in brute-force, in less time than to brute-force the actual key (thus reducing the security of a 4096-bit or higher key to the small entropy in this function), or can be exposed to or even manipulated by active attackers.

Explanation

The function uses these sources:

$a = base_convert(md5(microtime()), 16, 10);

microtime(): At least on Windows 7 64-bit (w/PHP 5.5 64-bit) and Linux 64-bit, microtime() returns a string of the form "0.uuuuuu00 sssssssss" where "u" is the microseconds since the last second (000000-999999) and "s" is the number of seconds since epoch (1/1/1970 UTC). There are only 94.7 million possible values for epoch between now and 3 years ago. If we further constrain the range to keys generated in the past year, then there are only 31.5 million possibilities. Either range is trivial to try by naive brute force in an offline attack. There are one million possibilities for the microtime portion, which again through a naive brute force, merely multiplies the 31.5 million epoch values, resulting in 31,536,000,000,000 possibilities, or an upper bound of 44 bits of entropy.

Worst-case: If the attacker has the timestamp of the created public key, that is likely close to the exact time of the key derivation, drastically limiting the possible values for epoch and microtime.

$b = base_convert(sha1(@exec('uptime')), 16, 10);

Windows: uptime is not available on Windows platforms, and the exec() call returns an empty string. sha1("") will always return the value "da39a3ee5e6b4b0d3255bfef95601890afd80709". It does not contribute toward entropy if the platform is known to be Windows.

Linux: uptime returns the current time in 24-hour format (hh:mm:ii), the system uptime in days (likely between 0-365), in hours:minutes, users logged in, and load average. Current time only yields 86400 possible values, uptime can be likely constrained to the past year (365 days) plus 1440 possible values for the uptime in hours:minutes. The user count is usually small (0-10-ish) on dedicated costs, or larger on shared hosts. Load averages are usually small for well-provisioned systems; let's assume three independent values of 0.0-0.99. These aren't actually independent variables though, so the real distribution will be more constrained. Additionally. they can be attacked in a side-channel by forcing high or low utilization through denial-of-service attacks (depending on the type of attack chosen).

Worst-case: Windows, which doesn't support uptime, or a shared-host environment, where the uptime() can be sampled directly by the user.

$c = mt_rand();

The mt_rand() and rand() functions have very limited periods and it is possible to determine the generator's state. See I Forgot Your Password: Randomness Attacks Against PHP
Applications, George Argyros & Aggelos Kiayias, which was also submitted to Black Hat 2012 as PRNG: Pwning Random Number Generators.

A break in the underlying LCG causes a cascade that breaks the rest of the system (rand(), shuffle(), etc.).

$d = disk_total_space("/");

This is the total amount of space (the docs say "disk_total_space — Returns the total size of a filesystem or disk partition" but the example on PHP.net says "available bytes"; in this case, the example is wrong, the docs are right). As such, this value is static and will not change between keys. Possible values are small - it will likely be aligned along 4KB boundaries, and many applications on a system may leak this information.

All keys generated on the system will have the same value.

Worst-case: Executing any code on the system (shared host, hack) will reveal this value explicitly.

$e = rand();

See notes under mt_rand(), above.

$f = memory_get_usage();

Another small-range number, which is constant within any given application. This can either be sampled by an attacker, or guessed. Will always be between 0 and PHP's memory limit, if enabled (default: 8MB prior to PHP 5.2, 16MB in PHP 5.2, currently 128MB).

All keys generated by the same script will have the same value.

Worst-case: PHP before 5.2.0 (still in use today!) compiled without the "--enable-memory-limit" option will not have this function. Executing any code on the system (shared host, hack) will reveal this value explicitly.

str_shuffle(preg_replace("[^0-9]", '', $a . $b . $c . $d . $e));

str_shuffle() uses rand() at its core, so if the LCG has been exposed/compromised, this mutation is rendered useless as well. (See notes under mt_rand().)

Solution

Use the entropy sources you already have, but gather additional entropy.

• Use /dev/random or /dev/urandom on Linux platforms.
• Use Microsoft's Utilities.GetRandom method on Windows platforms, available in PHP by instantiating the CAPICOM.Utilities.1 COM class: $com = new COM('CAPICOM.Utilities.1');
• Use openssl_random_pseudo_bytes() on all platforms (although there is a bug on Windows before PHP 5.3.5 which makes it very slow).
• Use mcrypt_create_iv()
• Combine as many of these sources as possible, and use them with a semantically-secure pseudorandom function to "whiten" the values. This will generate as many semantically-secure pseudorandom values as you need. For example, use SHA256 on the entirety of the gathered entropy (the seed), then use the hash output of that operation with a counter value to keep running SHA256 until you get sufficient pseudorandom bytes back out.

Mitigate (somewhat) other attacks

You can try to mitigate mt_rand() and rand()'s deficiencies by reseeding often (mt_srand()/srand()) and munging the amount of time taken in the script (and between reseeds), e.g. with random-wait (usleep()) FOR loops. This also helps to protect against timing attacks against the key derivation algorithm if the attacker is able to witness (or cause) new keys being generated.

_Timing and other attacks:_ Really this deserves its own issue. During encryption, you can very handily derive the exponent by timing the server's response. There are plenty of published attacks in the literature along these lines. Introducing randomness into the cipher loops is a means of protecting against this sort of attack. But then, beware power-usage or CPU-usage side-channel attacks, so try to utilize the CPU or do some wasted exponentiation during your random waits (but make sure the dummy work isn't optimized out by the Zend Opcache in PHP 5.5!). I can't possibly cover the entirety of the material here; these are just some ideas for further reading to secure the library.

Mentioned a few times on http://stevish.com/rsa-encryption-in-pure-php