Random numbers Take two

Recently there was a great work about the attacks on a random number generator in PHP , however, no practical examples were presented in it. We conducted our own research on this topic, which resulted in the creation of a set of tools for implementing such attacks.

Getting sid mt_rand via PHPSESSID

PHPSESSID is generated as follows.
md5 (Client IP. timestamp. microseconds1. php_combined_lcg ())

• Client IP is known to the attacker.
• Timestamp known (Date header in web server response)
• microseconds1 - value from 0 to 1,000,000
• php_combined_lcg () - example value: 0.12345678

For generating php_combined_lcg () 2 sid are used:
')
S1 = timestamp XOR (microseconds2 << 11)
S2 = pid XOR (microseconds3 << 11)

• same timestamp
• microseconds2 0-3 more than the first measurement (microseconds1)
• pid - process id of the current process (0-32768)
• microseconds3 1-4 more microseconds2

The largest entropy is in microseconds; however, with the help of two techniques, the entropy of microseconds can be significantly reduced.

Synchronization server and client

The point of the technique is to consistently send pairs of requests to determine the moment when the second in the Date header changes.

HTTP / 1.1 200 OK
Date: Wed, 08 Aug 2012 06:05:14 GMT
...
HTTP / 1.1 200 OK
Date: Wed, 08 Aug 2012 06:05:15 GMT

If this happens, then between our requests the microseconds are reset. By sending requests with dynamic delays, you can synchronize the local value of microseconds with the server value.

Request Twins

The principle is as follows. We send two requests one after another: the first to reset the password itself, the second - to reset the admin password. The difference in microseconds will be minimal.

Thus, brut md5 PHPSESSID consists in the selection of microseconds, deltas of subsequent measurements of microseconds, as well as pid. As for the pid, the authors have forgotten about such Apache thing as server-status, which shows - among other things - “pids” of processes that serve customer requests, which can be very useful.

For Brutus, a module for PasswordsPro was originally written; however, with this approach, it is impossible to take into account the correlation of deltas microseconds, so you had to rebound the full range. The rate was about 12 million sids per second.

Subsequently, a special program was written.



The speed is about 16 million sids per second, the calculation of the sid is less than an hour (3.2 GHz x 4 i5).
Having obtained the pid and php_combined_lcg () value, you can calculate the seed for mt_rand, which is generated as follows.

(timestamp x pid) XOR (106 x php_combined_lcg ())

In addition, php_combined_lcg () is used as an additional entropy for the uniqid function (when called with the second parameter = true).

Thus, when a web application uses standard PHP sessions, it is possible to predict mt_rand (), rand (), uniqid ().

Getting sid mt_rand through the output of one of the random numbers

The sid value for mt_rand () is an integer of 2 ^ 32. If there is a conclusion of a random number, it is possible to pick up a seed, which is actually quite possible with the help of rainbow tables, which allow you to find a seed in about 10 minutes.

Scenarios for the generation of tables, selection of sid and already prepared tables here: http://www.gat3way.eu/poc/mtrt/



What to look for in the code?
All calls to mt_rand (), rand (), uniqid (), shuffle (), lcg_value (), etc. The only invulnerable function is openssl_random_pseudo_bytes (), but it is almost never used. The main methods of protection:

• MySQL-function RAND () - with high probability it can also be predicted;
• Suhosin patch - by default it does not patch the functions mt_srand, srand; protection will be provided when Suhosin is installed separately as an extension;
• / dev / urandom - the iron method.

Arseny Reutov
Timur Yunusov
Dmitry Nagibin