Sec Bug->Bug #75667 [Opn->Nab]: Session GC LCG range leak helps attack mt_rand PRNG

Edit report at https://bugs.php.net/bug.php?id=75667&edit=1 ID: 75667 Updated by: cmb@php.net Reported by: Ciprian dot Pitis at microsoft dot com Summary: Session GC LCG range leak helps attack mt_rand PRNG -Status: Open +Status: Not a bug -Type: Security +Type: Bug Package: Session related PHP Version: 5.6.32 -Assigned To: +Assigned To: cmb Block user comment: N Private report: Y New Comment: Sorry for the late reply – obviously this ticket has been missed. :( Anyhow, this is not a security issue according to our security classification[1]: | requires the use of code or settings known to be insecure > […] after all we all know PRNG should not be used for secure > crypto - except people do as detailed in description […] The latter is most unfortunate, but what can we do more than to prominently document that mt_rand() is unsuitable for such purpose[2]? Anybody who is aware of applications which use mt_rand() for such purposes, should better report that to the respective application maintainers. :) [1] <https://wiki.php.net/security> [2] <https://www.php.net/mt_rand> Previous Comments: ------------------------------------------------------------------------ [2019-05-20 14:18:53] Ciprian dot Pitis at microsoft dot com Hey guys any update on this? Are you interested in fixing that or not really? :) ------------------------------------------------------------------------ [2018-01-29 19:58:32] Ciprian dot Pitis at microsoft dot com Ping - at least it would be nice to learn it won't get fixed :_) ------------------------------------------------------------------------ [2018-01-08 21:11:00] orminapod3 at gmail dot com Hey there, Any update on this? :) ------------------------------------------------------------------------ [2017-12-12 01:32:18] Ciprian dot Pitis at microsoft dot com 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. ------------------------------------------------------------------------ -- Edit this bug report at https://bugs.php.net/bug.php?id=75667&edit=1