Description:
------------
Hi everyone,

First of all - it's a pretty atypical ,,bug", we might be even discussing whether its a bug at all ( after all we all know PRNG should not be used for secure crypto - except people do as detailed in description ), truth be told - I found this attack while playing a CTF game on an application and I actually performed it on an application ran under FPM - and because I think effects are quite adverse I thought you might wanna know.

Every running a PHP request, there's a slight probability that sessions will be GCed, by default set to 1%:

		nrand = (int) ((float) PS(gc_divisor) * php_combined_lcg(TSRMLS_C));
		if (nrand < PS(gc_probability)) {
			PS(mod)->s_gc([...]);


mt_rand uses GENERATE_SEED() macro to seed in case it wasn't seeded before, and seeding looks as follows:
#define GENERATE_SEED() (((zend_long) (time(0) * getpid())) ^ ((zend_long) (1000000.0 * php_combined_lcg())))


This means, that a determined attacker can do the following ( and just in case - I actually did that on the test app ):
a) Spray some sessions

b) Wait for maximum session lifetime ( in our attack scenario it was 1440s )

c) Start hitting a vulnerable endpoint* but where he can actually get the result ( like, generate password token for his own account ) and save it.

* - by vulnerable, I mean an endpoint which will 
use mt_rand for an important purpose, like generating a password reset token.

d) Check if one of his sprayed session died out. If it died, it means the LCG generated in this request is guaranteed to be between <0,0.01> and this LCG was used for mt_rand seeding, lowering the attacking surface 100x. If not, just start hitting vulnerable endpoints again until you hit the 1% window.

e) At this point, attacker knows the request PRNG result, LCG part: <0,10000> , time(0) of the request and does not know PID. Attacker bruteforces PID locally by calculating seeds and comparing against the data he received from point c), Complexity of the attack being 10000 * 32768 ( maxpid ). This takes around 20-25 min on my machine ( as opposed to required 2500~ minutes without the LCG trick ). Attacker at this point knows the PID.

f) We perform the LCG trick again - spray sessions again as before, sleep for the maximum session duration again

g) This time, we will be hitting the vulnerable endpoint but for the actual attack ( lets say, reset password token for admin account ). Again we check if our spray sessions died and log when it actually did.

h) At this point, attacker knows the LCG <1,10000> part, knows the time() part AND knows the PID. That way, he dramatically lowers the bruteforce surface needed to be done remotely - instead of bruteforcing 4294967296 requests ( amount of seeds possible ), he will only have to do 10000 requests.( only 1/429496 part! ) as he knows everything except for the small part of the LCG calculation.

There are some mitigations to this attack - if PID changes in-between, or theres many PIDs listening, it might hinder ( but not stop ) the attacker. Similarly, high amount of traffic may make it difficult for an attacker to reliably leak LCG, however I found out that on a CTF application ( which was bombarded with requests from other CTF teams ) we've been somewhat reliable in leaking it.

I know it sounds complicated and I know PRNG shouldn't be used for security purposes, but people actually do it - for example, FOSUserBundle 1.3.7, one of most popular User-management bundles has still 10k daily downloads as of November 2017, is still using mt_rand and is suspectible to this attack. 

The important part about this attack is that as opposed of known publicly mt_rand attacks in PHP ( like http://www.openwall.com/php_mt_seed/ ), this one does not require you to have the actual mt_rand result - it can be transformed, changed, hashed etc etc - it doesn't really matter, as long as we know the algorithm used we can still attack it.

I still have my attack scripts, if you need those I can upload them too.