# Improving mt_rand() seed - Thread: https://externals.io/message/97774 - Original archive: https://news-web.php.net/php.internals/97774 - Started by Yasuo Ohgaki on 2017-01-16T07:04:21+00:00 - Messages: 32 - Page 1 of 2: messages 1 to 25 (25 per page, add `?page=N` to the URL) - Next page: https://externals.io/message/97774.md?page=2 - Reply by email to internals@lists.php.net - More for agents: search with https://externals.io/search.md?q={query} · JSON API at https://externals.io/api · documentation at https://externals.io/llms.txt --- ## #97774 — Yasuo Ohgaki — 2017-01-16T07:04:21+00:00 URL: https://externals.io/message/97774#97774 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 --- ## #97775 — Yasuo Ohgaki — 2017-01-16T07:16:37+00:00 URL: https://externals.io/message/97774#97775 · In reply to: #97774 > 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 --- ## #97792 — lauri.kentta@gmail.com — 2017-01-16T17:34:25+00:00 URL: https://externals.io/message/97774#97792 · In reply to: #97775 On Mon, Jan 16, 2017 at 4:04 PM, Yasuo Ohgaki 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. > 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ä --- ## #97796 — Yasuo Ohgaki — 2017-01-17T00:34:16+00:00 URL: https://externals.io/message/97774#97796 · In reply to: #97792 Hi Lauri, On Tue, Jan 17, 2017 at 2:34 AM, Lauri Kenttä wrote: > > > > […] > > Maybe you should fix session id instead of (or in addition to) mt_rand. > It is fixed. I should have written "was compromised". > > > > > […] > > 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 --- ## #97808 — lauri.kentta@gmail.com — 2017-01-17T14:18:01+00:00 URL: https://externals.io/message/97774#97808 · In reply to: #97796 > Set state somewhere between MT rand's 2^19937−1 cycle. This is exactly what my patch does. -- Lauri Kenttä --- ## #97811 — Leigh — 2017-01-17T14:48:55+00:00 URL: https://externals.io/message/97774#97811 · In reply to: #97774 > 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? > > 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 --- ## #97813 — lauri.kentta@gmail.com — 2017-01-17T14:59:24+00:00 URL: https://externals.io/message/97774#97813 · In reply to: #97808 > > > […] > > 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ä --- ## #97845 — Yasuo Ohgaki — 2017-01-18T00:27:39+00:00 URL: https://externals.io/message/97774#97845 · In reply to: #97811 Hi Leigh, > 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 --- ## #97846 — Yasuo Ohgaki — 2017-01-18T00:44:31+00:00 URL: https://externals.io/message/97774#97846 · In reply to: #97813 Hi Lauri, On Tue, Jan 17, 2017 at 11:59 PM, Lauri Kenttä wrote: > > > > […] > > 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 --- ## #97847 — Nikita Popov — 2017-01-18T01:22:20+00:00 URL: https://externals.io/message/97774#97847 · In reply to: #97846 > Hi Lauri, > > On Tue, Jan 17, 2017 at 11:59 PM, Lauri Kenttä > wrote: > > > […] > > > 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 --- ## #97848 — Yasuo Ohgaki — 2017-01-18T06:04:02+00:00 URL: https://externals.io/message/97774#97848 · In reply to: #97847 > > > > […] > > 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 --- ## #97852 — Leigh — 2017-01-18T09:20:45+00:00 URL: https://externals.io/message/97774#97852 · In reply to: #97848 > 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) --- ## #97860 — lauri.kentta@gmail.com — 2017-01-18T16:06:50+00:00 URL: https://externals.io/message/97774#97860 · In reply to: #97848 On Wed, Jan 18, 2017 at 10:22 AM, Nikita Popov > 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. > 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ä --- ## #97861 — Leigh — 2017-01-18T17:27:33+00:00 URL: https://externals.io/message/97774#97861 · In reply to: #97860 > > 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. You don't need to use the random_int functions, 4 bytes from php_random_bytes_silent cast into a uint32_t will give you an unbiased seed. (powers of 2 are unbiased) --- ## #97862 — Yasuo Ohgaki — 2017-01-19T01:10:32+00:00 URL: https://externals.io/message/97774#97862 · In reply to: #97860 Hi Lauri, On Thu, Jan 19, 2017 at 1:06 AM, Lauri Kenttä wrote: > > > > […] > > 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 Thank you. I have to be able to modify patch, so I'll fetch your change to my repo and make PR. BTW, I don't think we have to care for failing CSPRNG. If it failed, application should fail properly, i.e. should terminate process/code. PHP apps are not OS nor DBMS, they have freedom to terminate/exit when fatal event happened. Regards, -- Yasuo Ohgaki yohgaki@ohgaki.net --- ## #97871 — Leigh — 2017-01-19T11:25:57+00:00 URL: https://externals.io/message/97774#97871 · In reply to: #97862 > > Thank you. I have to be able to modify patch, so I'll fetch your change to > my repo > and make PR. BTW, I don't think we have to care for failing CSPRNG. If it > failed, > application should fail properly, i.e. should terminate process/code. > PHP apps are not OS nor DBMS, they have freedom to terminate/exit when fatal > event happened. > You _do_ have to care if it fails. This is a breaking change if it is not handled. mt_rand is _not_ a CSPRNG, and therefore the absence of a CSPRNG should not make mt_rand unusable. --- ## #97872 — Yasuo Ohgaki — 2017-01-19T11:46:23+00:00 URL: https://externals.io/message/97774#97872 · In reply to: #97871 Hi Leigh, > > You _do_ have to care if it fails. This is a breaking change if it is > not handled. mt_rand is _not_ a CSPRNG, and therefore the absence of a > CSPRNG should not make mt_rand unusable. If we consider mt_rand only, your statement is true. However, PHP as a whole cannot work reliable way w/o CSPRNG and today's standard requires working CSPRNG, doesn't it? If PHP cannot work properly, I don't see the point to make mt_rand work. I don't mind too much about falling back to very weak mt_rand result, but I just don't see the point allowing very weak result than it should/can be. How many of us are willing to allow very weak mt_rand fallback? This could be RFC vote option, if there are few. Regards, P.S. Please note that number of E_ERRORs were added recently when something goes wrong in fatal way . Compare to these, very rarely raised security concerned fatal exception is nothing. IMHO. -- Yasuo Ohgaki yohgaki@ohgaki.net --- ## #97875 — lauri.kentta@gmail.com — 2017-01-19T13:37:32+00:00 URL: https://externals.io/message/97774#97875 · In reply to: #97872 > However, PHP as a whole cannot work reliable way w/o CSPRNG and > today's > standard requires working CSPRNG, doesn't it? No. Why do you think that PHP can't work without CSPRNG? PHP is a general-purpose programming language. It can be used in a closed environment, even on machines without any network. CSPRNG is not required and should not be required. -- Lauri Kenttä --- ## #97877 — Leigh — 2017-01-19T14:14:57+00:00 URL: https://externals.io/message/97774#97877 · In reply to: #97872 > How many of us are willing to allow very weak mt_rand fallback? > This could be RFC vote option, if there are few. Everyone who cares about stability. I agree, if you want to introduce breaking changes, this needs to go to RFC. Therefore the simplest option seems to be DON'T introduce breaking changes. Wouldn't you agree? --- ## #97906 — Yasuo Ohgaki — 2017-01-21T02:12:30+00:00 URL: https://externals.io/message/97774#97906 · In reply to: #97875 Hi Lauri and Leigh, On Thu, Jan 19, 2017 at 10:37 PM, Lauri Kenttä wrote: > > > > […] > > No. > > Why do you think that PHP can't work without CSPRNG? > > PHP is a general-purpose programming language. It can be used in a closed > environment, even on machines without any network. CSPRNG is not required > and should not be required. When things failed, program should fail properly. There are number of examples that failed to make thing secure enough. e.g. SSL > > Everyone who cares about stability. > > I agree, if you want to introduce breaking changes, this needs to go to > RFC. > > Therefore the simplest option seems to be DON'T introduce breaking > changes. Wouldn't you agree? The nature of MT rand is non CSPRNG, so I don't mind to much about the fallback. I'm just uncomfortable with not following the "When things failed, program should fail properly" principle. Not following this principle caused unexpected results in many softwares. This specific case does not matter much, though. Anyway, unusable CSPRNG is very unlikely to happen. I may just use UNEXPECTED macro for the if branch. Regards, -- Yasuo Ohgaki yohgaki@ohgaki.net --- ## #97909 — Yasuo Ohgaki — 2017-01-21T02:55:39+00:00 URL: https://externals.io/message/97774#97909 · In reply to: #97906 Hi, > On Thu, Jan 19, 2017 at 10:37 PM, Lauri Kenttä > wrote: > > > […] > > > When things failed, program should fail properly. > There are number of examples that failed to make thing secure enough. e.g. > SSL > > > > > > […] > > > The nature of MT rand is non CSPRNG, so I don't mind to much about the > fallback. I'm just uncomfortable with not following the "When things > failed, program should fail properly" principle. Not following this > principle caused unexpected results in many softwares. This specific case > does not matter much, though. > > Anyway, unusable CSPRNG is very unlikely to happen. I may just use > UNEXPECTED macro for the if branch. > I changed my mind due to comment for `uniqid()` CSPRNG usage. IMO, there is no benefit for CSPRNG failure fallback. We shouldn't add fackback for every CSPRNG usage. It's just does not make sense. Are we going to add poor fallbacks for every CSPRNG usage? I strongly against it. CSPRNG failure is like BUS error, i.e. hardware error. CSPRNG shouldn't fail with healthy hardware/OS. Therefore, we should not add poor fallback code for it. Regards, -- Yasuo Ohgaki yohgaki@ohgaki.net --- ## #97911 — Christoph M. Becker — 2017-01-21T12:34:06+00:00 URL: https://externals.io/message/97774#97911 · In reply to: #97774 > 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 --- ## #97912 — Niklas Keller — 2017-01-21T14:40:58+00:00 URL: https://externals.io/message/97774#97912 · In reply to: #97909 > > > […] > > I changed my mind due to comment for `uniqid()` CSPRNG usage. > > IMO, there is no benefit for CSPRNG failure fallback. We shouldn't add > fackback for every CSPRNG usage. Right, we absolutely should not. Most usages of a CSPRNG require a CSPRNG, while mt_rand and uniqid do not, so it's a different case here. > It's just does not make sense. Are we > going to add poor fallbacks for every CSPRNG usage? I strongly against it. > > CSPRNG failure is like BUS error, i.e. hardware error. CSPRNG shouldn't > fail with healthy hardware/OS. Therefore, we should not add poor fallback > code for it. A CSPRNG is not necessarily a hardware error. PHP might run on weird platforms, no? Anyway, the "issue" with mt_rand is not the seed being predictable but the internal state being recoverable from the output. But mt_rand is predictable by design, so why should we even seed it with a CSPRNG by default? Regards, Niklas --- ## #97921 — Leigh — 2017-01-22T09:40:41+00:00 URL: https://externals.io/message/97774#97921 · In reply to: #97912 > Anyway, the "issue" with mt_rand is not the seed being predictable but the > internal state being recoverable from the output. But mt_rand is > predictable by design, so why should we even seed it with a CSPRNG by > default? > > > For the record, when I was making RNG changes for 7.1, I did look at the mt_rand seed mechanism, and decided it was _good enough_ for the purposes of mt_rand. State recovery can actually be done with as few as 624 sequential outputs, you will never be able to get away from that. Even with a fully CSPRNG generated state, if an attacker gets 624 outputs after the state is twisted, the RNG is compromised. --- ## #97981 — Yasuo Ohgaki — 2017-01-27T02:52:34+00:00 URL: https://externals.io/message/97774#97981 · In reply to: #97921 Hi Leigh, > > > > […] > mt_rand seed mechanism, and decided it was _good enough_ for the purposes > of mt_rand. > > State recovery can actually be done with as few as 624 sequential outputs, > you will never be able to get away from that. Even with a fully CSPRNG > generated state, if an attacker gets 624 outputs after the state is > twisted, the RNG is compromised. > Nice comment! Since mt_rand is predictable PRNG, there is possibility to be known to attackers always. What I would like to change is - there is only 2^32 initial states Think of a code that generates "random password string" from mt_rand. (We know nobody should do this, but there are many codes do this) If password is alpha numeric+#$ and 10 chars long, there could be 64^10 = 2^60 patterns with pure random. but with current mt_rand could generate only 2^32 patterns due to `mt_rand()` limited state. This is a lot less random than it could be. Hardening `mt_rand()` w/o salt value beneficial to general `mt_rand()` usage also. i.e. PHP app runs short periods of time and only use beginning of MT rand cycle. More than 99% random cycle is wasted currently. Regards, -- Yasuo Ohgaki yohgaki@ohgaki.net --- Next page: https://externals.io/message/97774.md?page=2