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
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())))
#endifWe 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
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.
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ä
Hi Lauri,
On Tue, Jan 17, 2017 at 2:34 AM, Lauri Kenttä lauri.kentta@gmail.com
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".
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
Set state somewhere between MT rand's 2^19937−1 cycle.
This is exactly what my patch does.
--
Lauri Kenttä
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ä
Hi Lauri,
On Tue, Jan 17, 2017 at 11:59 PM, Lauri Kenttä lauri.kentta@gmail.com
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
Hi Lauri,
On Tue, Jan 17, 2017 at 11:59 PM, Lauri Kenttä lauri.kentta@gmail.com
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
Hi Lauri,
On Tue, Jan 17, 2017 at 11:59 PM, Lauri Kenttä lauri.kentta@gmail.com
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 theuniqid()thread more than once: If a CSPRNG is not
available, this will makemt_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 usesmt_rand()inappropriately, especially for cases
wheremt_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
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)
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.
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ä
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)
Hi Lauri,
On Thu, Jan 19, 2017 at 1:06 AM, Lauri Kenttä lauri.kentta@gmail.com
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
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
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.
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
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ä
Hi Lauri and Leigh,
On Thu, Jan 19, 2017 at 10:37 PM, Lauri Kenttä lauri.kentta@gmail.com
wrote:
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.
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
Hi,
On Thu, Jan 19, 2017 at 10:37 PM, Lauri Kenttä lauri.kentta@gmail.com
wrote: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.When things failed, program should fail properly.
There are number of examples that failed to make thing secure enough. e.g.
SSLEveryone 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.
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
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.
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
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.
Hi Leigh,
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.
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
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
This needs to be thought of as 2^32 possible streams with a period
of (2^19937)−1. Offset within the stream is as important as the stream
variation itself.
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.
Statistical testing of MT shows it to be pretty good. The ability to
recover the state from full outputs doesn't subtract from the quality
of the randomness. It is absolutely not a cryptographic quality
generator, but it is a high quality source of entropy.
In fact state recovery is made harder in PHP because we only ever emit
31 of the 32 bits of output. This compounds over 624 outputs, and
while it doesn't make it impossible to recover it adds some difficulty
(especially when you don't know when the state will twist).
Another factor to consider is that people discard most of the output
when they do things like using mt_rand to generate character strings,
so an observer only sees 8 out of 32 bits per call, making state
recovery exceptionally more difficult (again not knowing when the
state will be mutated).
but with current mt_rand could generate only
2^32 patterns due tomt_rand()limited state.
The 2^32 vs 2^60 is a false equivalence. 2^32 is the theoretical
number of unique passwords that can be generated from a freshly
initialised state, while 2^60 represents the "bit strength" of a
single password. Even with 2^32 possible initial states every
password generated will still have a bit strength of 2^60
This is a lot less random than it could be.
Hardening
mt_rand()w/o salt value beneficial to generalmt_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.
You can force this kind of scenario if you have for example a CLI
script that generates a single password and then exits. In this case
you only have 2^32 possible unique outcomes, but this is rarely the
case.
The MT state is per-process, not per request. If you do not explicitly
re-seed it then you will continue down that 2^19937 period. So in fact
it is far safer to not re-seed MT explicitly from user-land code.
In most applications you cannot guarantee that your request is being
served by the same process, you will never get a full outputs, and you
never know your position within the state. State recovery is generally
going to be infeasible, even right now without any changes.
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
This needs to be thought of as 2^32 possible streams with a period
of (2^19937)−1. Offset within the stream is as important as the stream
variation itself.
This is not true. There is one stream of period (2^19937)−1, and
the initial state defines the current position in that stream.
Statistical testing of MT shows it to be pretty good. The ability to
recover the state from full outputs doesn't subtract from the quality
of the randomness. It is absolutely not a cryptographic quality
generator, but it is a high quality source of entropy.
Do not confuse entropy and randomness. Entropy is true randomness,
as can be seen in /dev/random. There is no deterministic algorithm
for generating more entropy, so MT or even a CSPRNG has exactly
as much entropy as the seed contains.
Even with 2^32 possible initial states every
password generated will still have a bit strength of 2^60
If the attacker knows the algorithm, the bit strength is only 2^32.
The remaining 2^28 comes from security through obscurity, which is
not a generally valid real security thing.
Anyway, a password should be better generated with CSPRNG, not MT,
so "hardening" MT is totally irrelevant.
--
Lauri Kenttä
This needs to be thought of as 2^32 possible streams with a period
of (2^19937)−1. Offset within the stream is as important as the stream
variation itself.This is not true. There is one stream of period (2^19937)−1, and
the initial state defines the current position in that stream.
I'm not sure about this, the LCG constant used in the initial
generator seems completely unrelated to the rest of the algorithm, so
I don't see how this offsets the stream position.
If it is truly the case, I stand corrected.
Even with 2^32 possible initial states every
password generated will still have a bit strength of 2^60If the attacker knows the algorithm, the bit strength is only 2^32.
The remaining 2^28 comes from security through obscurity, which is
not a generally valid real security thing.
Fair point.
Anyway, a password should be better generated with CSPRNG, not MT,
so "hardening" MT is totally irrelevant.
Obviously.
I still maintain that pulling 2.5k from the CSPRNG to power MT is
overkill though. I agree we shouldn't waste time "hardening" it just
because some people misuse it. We can make the initial seeding less
deterministic but I don't think we should do more than that.
On 27 January 2017 at 14:30, Lauri Kenttä lauri.kentta@gmail.com
wrote:This needs to be thought of as 2^32 possible streams with a period
of (2^19937)−1. Offset within the stream is as important as the
stream
variation itself.This is not true. There is one stream of period (2^19937)−1, and
the initial state defines the current position in that stream.I'm not sure about this, the LCG constant used in the initial
generator seems completely unrelated to the rest of the algorithm, so
I don't see how this offsets the stream position.If it is truly the case, I stand corrected.
I'm sorry, I oversimplified a bit in a hurry.
MT has (2^19937)−1 possible internal states, and I understand that
it's supposed to go through all these, hence the (2^19937)−1 period.
In each state, mt_rand returns 624 values of 32 bits before
"twisting" to the next state. Initializing with a different state
offsets the stream position just as it would in a LCG, but because
of the huge state and with the current MT initialization method,
it's very difficult to say what that offset actually would be.
But still, starting with mt_srand(0) and looping trough mt_rand,
you should eventually end up in the same state as mt_srand(1).
It might take around 2^(19937-32) * 624 mt_rand calls, though.
--
Lauri Kenttä
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?
Hi all,
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
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())))
#endifWe 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
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
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())))
#endifWe 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