php.net |  support |  documentation |  report a bug |  advanced search |  search howto |  statistics |  random bug |  login
Bug #75667 Session GC LCG range leak helps attack mt_rand PRNG
Submitted: 2017-12-12 01:32 UTC Modified: 2020-02-12 14:53 UTC
From: Ciprian dot Pitis at microsoft dot com Assigned: cmb (profile)
Status: Not a bug Package: Session related
PHP Version: 5.6.32 OS:
Private report: No CVE-ID: None
 [2017-12-12 01:32 UTC] 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.



Patches

Add a Patch

Pull Requests

Add a Pull Request

History

AllCommentsChangesGit/SVN commitsRelated reports
 [2018-01-08 21:11 UTC] orminapod3 at gmail dot com
Hey there,

Any update on this? :)
 [2018-01-29 19:58 UTC] Ciprian dot Pitis at microsoft dot com
-: orminapod3 at gmail dot com +: Ciprian dot Pitis at microsoft dot com
 [2018-01-29 19:58 UTC] Ciprian dot Pitis at microsoft dot com
Ping - at least it would be nice to learn it won't get fixed :_)
 [2019-05-20 14:18 UTC] Ciprian dot Pitis at microsoft dot com
Hey guys any update on this? Are you interested in fixing that or not really? :)
 [2020-02-12 14:47 UTC] cmb@php.net
-Status: Open +Status: Not a bug -Type: Security +Type: Bug -Assigned To: +Assigned To: cmb
 [2020-02-12 14:47 UTC] cmb@php.net
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>
 [2020-02-12 14:53 UTC] nikic@php.net
Something relatively easy would could do is to see mt_rand from CSPRNG. It won't render mt_rand() any more suitable for cryptographic or other security-sensitive purposes, but it would help to mitigate broken code in practice.

The next step would be to use a CSPRNG (Salsa20 maybe) by default, and only switch to MT19937 if there is an explicit mt_seed() call.
 
PHP Copyright © 2001-2024 The PHP Group
All rights reserved.
Last updated: Thu Mar 28 19:01:29 2024 UTC