Everything
php
Learn Community Releases The PHP Project
Home » Project » Newsgroups » php.internals » Improving mt_rand() seed »

Improving mt_rand() seed

php.internals

Yasuo Ohgaki

9 years ago
Hi all, Since I was about to improve uniqid()'s entropy by replacing php_combined_lcg() to php_random_int(), I spent time to check other places that could be a problem. mt_rand()'s is seeded as follows by default. ext/standard/php_rand.h #ifdef PHP_WIN32 #define GENERATE_SEED() (((zend_long) (time(0) * GetCurrentProcessId())) ^ ((zend_long) (1000000.0 * php_combined_lcg()))) #else #define GENERATE_SEED() (((zend_long) (time(0) * getpid())) ^ ((zend_long) (1000000.0 * php_combined_lcg()))) #endif We know this kind of seed is guessable. i.e. Our session id is compromised by this kind of code. Although it would be rare that raw mt_rand() value is exposed, but guessable value is guessable. I'm going to replace the seeding code by simple php_random_int() call. Any comments? Regards,
-- Yasuo Ohgaki yohgaki@ohgaki.net

Yasuo Ohgaki

9 years ago
On Mon, Jan 16, 2017 at 4:04 PM, Yasuo Ohgaki <yohgaki@ohgaki.net> wrote:
> Since I was about to improve uniqid()'s entropy by replacing > php_combined_lcg() to php_random_int(), I spent time to check other places > that could be a problem. > > mt_rand()'s is seeded as follows by default. > > ext/standard/php_rand.h > #ifdef PHP_WIN32 > #define GENERATE_SEED() (((zend_long) (time(0) * GetCurrentProcessId())) ^ > ((zend_long) (1000000.0 * php_combined_lcg()))) > #else > #define GENERATE_SEED() (((zend_long) (time(0) * getpid())) ^ ((zend_long) > (1000000.0 * php_combined_lcg()))) > #endif > > We know this kind of seed is guessable. i.e. Our session id is compromised > by this kind of code. > > Although it would be rare that raw mt_rand() value is exposed, but > guessable value is guessable. I'm going to replace the seeding code by > simple php_random_int() call. > > Any comments? >
Read a bit more mt_rand code.It is better to exploit extremely long MT rand cycle. Therefore patch will be a little more complex than simply replacing the seeding code. Comments are appreciated. Regards,
-- Yasuo Ohgaki yohgaki@ohgaki.net

Lauri Kenttä

9 years ago
On Mon, Jan 16, 2017 at 4:04 PM, Yasuo Ohgaki <yohgaki@ohgaki.net> wrote:
> We know this kind of seed is guessable. i.e. Our session id is > compromised > by this kind of code.
Maybe you should fix session id instead of (or in addition to) mt_rand. On 2017-01-16 09:16, Yasuo Ohgaki wrote:
> Comments are appreciated.
Simply set BG(state)[0] to 0x80000000U and fill the rest with random. That's practically like the MT reference implementation init_by_array. See the attached patch. Feel free to commit.
-- Lauri Kenttä

Yasuo Ohgaki

9 years ago
Hi Lauri, On Tue, Jan 17, 2017 at 2:34 AM, Lauri Kenttä <lauri.kentta@gmail.com> wrote:
> On Mon, Jan 16, 2017 at 4:04 PM, Yasuo Ohgaki <yohgaki@ohgaki.net> wrote: > >> We know this kind of seed is guessable. i.e. Our session id is compromised >> by this kind of code. >> > > Maybe you should fix session id instead of (or in addition to) mt_rand. >
It is fixed. I should have written "was compromised".
> > On 2017-01-16 09:16, Yasuo Ohgaki wrote: > >> Comments are appreciated. >> > > Simply set BG(state)[0] to 0x80000000U and fill the rest with random. > That's practically like the MT reference implementation init_by_array. > See the attached patch. Feel free to commit.
Thanks. I didn't bother about efficiency, but it is more efficient than php_random_int(). This will do half of my idea. Attackers can guess random strings generated by MT rand by checking only 2^32 combinations because there are only 2^32 initial states. MT rand is not CSPRNG, so users must not use MT rand to generate random string, but there are many codes do this. To mitigate risk of such code, randomizing initial state could be done. i.e. Set state somewhere between MT rand's 2^19937−1 cycle. I haven't started research how to do this yet. I appreciate if you have patch for this, too. Regards,
-- Yasuo Ohgaki yohgaki@ohgaki.net

Lauri Kenttä

9 years ago
On 2017-01-17 02:34, Yasuo Ohgaki wrote:
> Set state somewhere between MT rand's 2^19937−1 cycle.
This is exactly what my patch does.
-- Lauri Kenttä

Lauri Kenttä

9 years ago
On 2017-01-17 16:18, Lauri Kenttä wrote:
> On 2017-01-17 02:34, Yasuo Ohgaki wrote: >> Set state somewhere between MT rand's 2^19937−1 cycle. > > This is exactly what my patch does.
Or, to be honest, my patch provides 2^19936 possible states, which should be more than enough. To get all 2^19937−1, you would need to get one more bit of entropy (2^19936 to 2^19937) and then check that the state is not all zeros (which is the −1 in 2^19937−1). That's certainly not worth the trouble, so I just set that one "extra" bit to 1. (MT doesn't work if the state is all zeros.)
-- Lauri Kenttä

Yasuo Ohgaki

9 years ago
Hi Lauri, On Tue, Jan 17, 2017 at 11:59 PM, Lauri Kenttä <lauri.kentta@gmail.com> wrote:
> On 2017-01-17 16:18, Lauri Kenttä wrote: > >> On 2017-01-17 02:34, Yasuo Ohgaki wrote: >> >>> Set state somewhere between MT rand's 2^19937−1 cycle. >>> >> >> This is exactly what my patch does. >> > > Or, to be honest, my patch provides 2^19936 possible states, > which should be more than enough. > > To get all 2^19937−1, you would need to get one more bit of > entropy (2^19936 to 2^19937) and then check that the state is > not all zeros (which is the −1 in 2^19937−1). That's certainly > not worth the trouble, so I just set that one "extra" bit to 1. > (MT doesn't work if the state is all zeros.)
Sorry for sloppy patch reading. Your patch initialize whole BG(state) buffer by php_random_bytes(). This should be good enough. I'll merge this patch. This better automatic initialization should be included 7.0 and up. mt_rand() will at a lot stronger against dictionary attacks. Any comments, RMs? Regards,
-- Yasuo Ohgaki yohgaki@ohgaki.net

Nikita Popov

9 years ago
On Wed, Jan 18, 2017 at 1:44 AM, Yasuo Ohgaki <yohgaki@ohgaki.net> wrote:
> Hi Lauri, > > On Tue, Jan 17, 2017 at 11:59 PM, Lauri Kenttä <lauri.kentta@gmail.com> > wrote: > > > On 2017-01-17 16:18, Lauri Kenttä wrote: > > > >> On 2017-01-17 02:34, Yasuo Ohgaki wrote: > >> > >>> Set state somewhere between MT rand's 2^19937−1 cycle. > >>> > >> > >> This is exactly what my patch does. > >> > > > > Or, to be honest, my patch provides 2^19936 possible states, > > which should be more than enough. > > > > To get all 2^19937−1, you would need to get one more bit of > > entropy (2^19936 to 2^19937) and then check that the state is > > not all zeros (which is the −1 in 2^19937−1). That's certainly > > not worth the trouble, so I just set that one "extra" bit to 1. > > (MT doesn't work if the state is all zeros.) > > > Sorry for sloppy patch reading. > Your patch initialize whole BG(state) buffer by php_random_bytes(). > This should be good enough. > I'll merge this patch. > > This better automatic initialization should be included 7.0 and up. > mt_rand() will at a lot stronger against dictionary attacks. > Any comments, RMs? >
The patch initializes the full MT state vector, approximately 2.5KB of memory, from a CSPRNG. To put this into perspective, 16 bytes are generally considered to be sufficient for cryptographic keying material. Does this seem somewhat disproportionate? Additionally, the patch has the same concern that has already been mentioned in the uniqid() thread more than once: If a CSPRNG is not available, this will make mt_rand() throw. While this is an unusual situation that should not occur in a well-configured system, this is still not acceptable. If you wish to introduce this change, please follow the usual procedure of submitting a PR, getting it reviewed by the relevant people and only merging it once it has been approved (or even better, just leave merging to someone else). I recommend doing this for any non-trivial change. For the record, I am generally in favor of seeding MT rand from CSPRNG. It doesn't really cost us anything and it will make it significantly harder to exploit code that uses mt_rand() inappropriately, especially for cases where mt_rand() is only called rarely within a single request. Nikita

Yasuo Ohgaki

9 years ago
On Wed, Jan 18, 2017 at 10:22 AM, Nikita Popov <nikita.ppv@gmail.com> wrote:
> On Wed, Jan 18, 2017 at 1:44 AM, Yasuo Ohgaki <yohgaki@ohgaki.net> wrote: > >> Hi Lauri, >> >> On Tue, Jan 17, 2017 at 11:59 PM, Lauri Kenttä <lauri.kentta@gmail.com> >> wrote: >> >> > On 2017-01-17 16:18, Lauri Kenttä wrote: >> > >> >> On 2017-01-17 02:34, Yasuo Ohgaki wrote: >> >> >> >>> Set state somewhere between MT rand's 2^19937−1 cycle. >> >>> >> >> >> >> This is exactly what my patch does. >> >> >> > >> > Or, to be honest, my patch provides 2^19936 possible states, >> > which should be more than enough. >> > >> > To get all 2^19937−1, you would need to get one more bit of >> > entropy (2^19936 to 2^19937) and then check that the state is >> > not all zeros (which is the −1 in 2^19937−1). That's certainly >> > not worth the trouble, so I just set that one "extra" bit to 1. >> > (MT doesn't work if the state is all zeros.) >> >> >> Sorry for sloppy patch reading. >> Your patch initialize whole BG(state) buffer by php_random_bytes(). >> This should be good enough. >> I'll merge this patch. >> >> This better automatic initialization should be included 7.0 and up. >> mt_rand() will at a lot stronger against dictionary attacks. >> Any comments, RMs? >> > > The patch initializes the full MT state vector, approximately 2.5KB of > memory, from a CSPRNG. To put this into perspective, 16 bytes are generally > considered to be sufficient for cryptographic keying material. Does this > seem somewhat disproportionate? >
It could be. I haven't read and research MT rand initialization code carefully yet.
> > Additionally, the patch has the same concern that has already been > mentioned in the uniqid() thread more than once: If a CSPRNG is not > available, this will make mt_rand() throw. While this is an unusual > situation that should not occur in a well-configured system, this is still > not acceptable. >
For the record, "uniqid()'s php_random_*() exception issue" is came from "Userland random_byte() compatibility lib issue which reads /dev/urandom from PHP script". Since PHP script could be affected by open_basedir, some systems cannot read PRNG and throw exception. Internal functions are not affected by open_basedir. If internal functions cannot read /dev/urandom (or like), then the system wouldn't work in fatal way. Therefore, it's irrelevant for internal functions. If you wish to introduce this change, please follow the usual procedure of
> submitting a PR, getting it reviewed by the relevant people and only > merging it once it has been approved (or even better, just leave merging to > someone else). I recommend doing this for any non-trivial change. > > For the record, I am generally in favor of seeding MT rand from CSPRNG. It > doesn't really cost us anything and it will make it significantly harder to > exploit code that uses mt_rand() inappropriately, especially for cases > where mt_rand() is only called rarely within a single request. >
Lauri, You wrote the patch. Could you make Pull Request to github's php-src repo? If you prefer not to, I'll make the PR. I think your patch should be applied from PHP-7.0 branch. Regards,
-- Yasuo Ohgaki yohgaki@ohgaki.net

Leigh

9 years ago
On Wed, 18 Jan 2017 at 06:05 Yasuo Ohgaki <yohgaki@ohgaki.net> wrote:
> It could be. I haven't read and research MT rand initialization code > carefully yet.
I have, it stretches 4 bytes of seed material into 624 * 4 bytes of material. There are only 2^32 possible initial states from direct seeding. After the state has been consumed it does a "twist"-pass on the existing state, this is where the "^19937-1 period comes from. I would recommend taking 4 bytes from php_random_bytes_silent() cast to uint32_t and passed to php_mt_srand(), if php_random_bytes_silent() fails fall back to the original seeding generation mechanism (it is unlikely an adversary can know which method was used)

Lauri Kenttä

9 years ago
On Wed, Jan 18, 2017 at 10:22 AM, Nikita Popov <nikita.ppv@gmail.com>
> The patch initializes the full MT state vector, approximately 2.5KB > of memory, from a CSPRNG. To put this into perspective, 16 bytes are > generally considered to be sufficient for cryptographic keying > material. Does this seem somewhat disproportionate?
It's a lot, but it's also a simple and clean solution. Randomizing only 16 bytes doesn't really work, because the randomness is twisted so slowly in MT19937. Any randomness needs to be stretched over the whole state immediately. If it's not acceptable to randomize the whole state, I'd recommend using php_random_int_silent() to generate a single seed. This would be easy to implement by simply changing GENERATE_SEED() into a function which first tries php_random_int_silent() but has the current method as a fallback. This would fix other use cases of GENERATE_SEED() as well. On 2017-01-18 08:04, Yasuo Ohgaki wrote:
> Lauri, > You wrote the patch. Could you make Pull Request to github's php-src > repo?If you prefer not to, I'll make the PR. > > I think your patch should be applied from PHP-7.0 branch.
I've revised my patch (added GENERATE_SEED() fallback), see [1]. I can send that against master if the approach is accepted here. If you want it in PHP-7.0 or PHP-7.1, please merge it yourself, thank you. [1] https://github.com/Metabolix/php-src/tree/mt_srand_auto-pr
-- Lauri Kenttä

Yasuo Ohgaki

9 years ago
Hi all, On Wed, Jan 18, 2017 at 3:04 PM, Yasuo Ohgaki <yohgaki@ohgaki.net> wrote:
> The patch initializes the full MT state vector, approximately 2.5KB of >> memory, from a CSPRNG. To put this into perspective, 16 bytes are generally >> considered to be sufficient for cryptographic keying material. Does this >> seem somewhat disproportionate? >> > > It could be. I haven't read and research MT rand initialization code > carefully yet. >
According to reference implementation referred by MT rand author, state buffer initialization by CSPRNG should be safe. See init_by_array(). http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/C-LANG/mt19937ar-nrl.c Basically, this code is trying to randomize state buffer w/o real RNG. Therefore, replacing it by CSPRNG is OK. Regards,
-- Yasuo Ohgaki yohgaki@ohgaki.net

Leigh

9 years ago
On 16 January 2017 at 07:04, Yasuo Ohgaki <yohgaki@ohgaki.net> wrote:
> Hi all, > > Since I was about to improve uniqid()'s entropy by replacing > php_combined_lcg() to php_random_int(), I spent time to check other places > that could be a problem. > > mt_rand()'s is seeded as follows by default. > > ext/standard/php_rand.h > #ifdef PHP_WIN32 > #define GENERATE_SEED() (((zend_long) (time(0) * GetCurrentProcessId())) ^ > ((zend_long) (1000000.0 * php_combined_lcg()))) > #else > #define GENERATE_SEED() (((zend_long) (time(0) * getpid())) ^ ((zend_long) > (1000000.0 * php_combined_lcg()))) > #endif > > We know this kind of seed is guessable. i.e. Our session id is compromised > by this kind of code.
mt_rand is not advertised as crypto-quality. Where do you think mt_rand is used in session id generation?

Yasuo Ohgaki

9 years ago
Hi Leigh, On Tue, Jan 17, 2017 at 11:48 PM, Leigh <leight@gmail.com> wrote:
> mt_rand is not advertised as crypto-quality. > > Where do you think mt_rand is used in session id generation? >
I don't mention session module uses mt_rand, but older versions used php_combined_lcg() . Regards,
-- Yasuo Ohgaki yohgaki@ohgaki.net

Christoph Becker

9 years ago
On 16.01.2017 at 08:04, Yasuo Ohgaki wrote:
> Since I was about to improve uniqid()'s entropy by replacing > php_combined_lcg() to php_random_int(), I spent time to check other places > that could be a problem. > > mt_rand()'s is seeded as follows by default. > > ext/standard/php_rand.h > #ifdef PHP_WIN32 > #define GENERATE_SEED() (((zend_long) (time(0) * GetCurrentProcessId())) ^ > ((zend_long) (1000000.0 * php_combined_lcg()))) > #else > #define GENERATE_SEED() (((zend_long) (time(0) * getpid())) ^ ((zend_long) > (1000000.0 * php_combined_lcg()))) > #endif > > We know this kind of seed is guessable.
But where's the problem? mt_rand() is not suitable for cryptographic purposes anyway.
> i.e. Our session id is compromised > by this kind of code.
Does the session ID rely on mt_rand() or GENERATE_SEED()? If so, that would of course be an issue, but that should be fixed by not using mt_rand()/GENERATE_SEED() for the session ID at all, IMHO.
-- Christoph M. Becker