Random numbers. Take two

Recently, a remarkable work on attacks on a random number generator in PHP was published , 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 this kind of attack.

Receiving mt_rand sid via PHPSESSID

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

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

2 sids are used to generate php_combined_lcg ():

S1 = timestamp XOR (microseconds2 << 11)
S2 = pid XOR (microseconds3 << 11)

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

The highest entropy is in microseconds, however, using two techniques, the entropy of microseconds can be significantly reduced.

Server and client synchronization

The point of the technique is to send pairs of requests sequentially to determine 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 microseconds value with the server value.

Request Twins

The principle is this. We send two requests one by one: the first to reset the password to ourselves, the second to reset the admin password. The difference in microseconds will be minimal.

Thus, the md5 PHPSESSID brute is to select microseconds, deltas of subsequent microseconds measurements, as well as pid. As for pid, the authors have forgotten about such an Apache thing as server-status, which shows, among other information, the "pids" of processes that serve client requests, which can be very useful.

For Brutus, the module for PasswordsPro was originally written, however, with this approach it is impossible to take into account the correlation of deltas microseconds, so I had to brute the full range. The speed was approximately 12 million seeds per second.

Was subsequently written special program .

Speed ​​- about 16 million seeds per second, sid calculation - less than an hour (3.2 GHz x 4 i5).
Having received the pid and the php_combined_lcg () value, we 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 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 mt_rand sid by outputting one of random numbers

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

Scenarios for generating tables, selecting sid and ready-made tables are 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 a high degree of probability it can also be predicted;
  • Suhosin patch - by default it does not patch functions mt_srand, srand; protection will be provided when Suhosin is installed separately as an extension;
  • / dev / urandom - iron method.

Arseny Reutov
Timur Yunusov
Dmitry Nagibin