Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:97984
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain gmail.com designates 209.85.215.53 as permitted sender)
MIME-Version: 1.0
In-Reply-To: <CAGa2bXaAYE2=R+m0YbpSLJD4goWFz9tbZXU_nPdczpUUcq-=AQ@mail.gmail.com>
References: <CAGa2bXbFST=5DkhiJ6zJ1hJ5vZYUo7CnCDp+VXcyvSU-bWcyMg@mail.gmail.com>
 <CAGa2bXak3tZ+kC6EeiA=ZCeynGSZbO-4Hpd1v_1oZVDHpSAvsA@mail.gmail.com>
 <71c26cd6df6f59e76dafd31647852c2e@koti.fimnet.fi> <CAGa2bXY0djrgpbC_wNGeRyciNygS59hmuaUaZG-=vAt0dZoxxA@mail.gmail.com>
 <142a3537a99809cf23d78e0eaadc3aef@gmail.com> <7a359bb08b0ad8b046534c15492cec91@gmail.com>
 <CAGa2bXZgbsHM-PZcSUoyA8VZ22rmMmjy41tGPUszC2Acr7Zjyw@mail.gmail.com>
 <CAF+90c9jC0r22NEPbeYXMgL8F_qm0rtJ-nXTeqj_PgjhcY6RRw@mail.gmail.com>
 <CAGa2bXaSux=Pq8+9N4wT9gaqjY--N=D9WwH0560=JEUjutd5LA@mail.gmail.com>
 <8cfe7a3ea5a05fc3e5347e9af848ada0@gmail.com> <CAGa2bXZzpfEuQDEcQM=eLRit8BRieW5KY5h-H59+1-P0Ehmomw@mail.gmail.com>
 <CAPwsocFypb4m7sA0An0CmJ=izZW_07PzyFVN7bN9A+q81aTEvw@mail.gmail.com>
 <CAGa2bXbn4d7tT_NG2EHzFKvMDWAr=TCPw1L26QJv7jyKE5of+w@mail.gmail.com>
 <a4a9e600b364c9cc70a4f8fcca11cdc7@gmail.com> <CAGa2bXZ7sOsJWkNpSRaBD-6i4mk0d4hxEmHSknf_1CT0iZ8+3g@mail.gmail.com>
 <CAGa2bXZyD4qxRpo-pKuYnpt6A2mjedKgC9_xTvSL2Ojs8y_e6Q@mail.gmail.com>
 <CANUQDChFDB604HyT4f3-FvAmbd5BjoQngT1FKG9JOtDceOv7-Q@mail.gmail.com>
 <CAPwsocEwNxskcOpX2n_t=oNCT1ntg8owmncA=NaCgTo6UqKjVw@mail.gmail.com> <CAGa2bXaAYE2=R+m0YbpSLJD4goWFz9tbZXU_nPdczpUUcq-=AQ@mail.gmail.com>
Date: Fri, 27 Jan 2017 10:58:09 +0000
Message-ID: <CAPwsocFUcODbpjFQsaK3V9c9Ck=LMtk5_g_9H_DdeuyvX+t1qQ@mail.gmail.com>
To: Yasuo Ohgaki <yohgaki@ohgaki.net>
Cc: Niklas Keller <me@kelunik.com>, =?UTF-8?Q?Lauri_Kentt=C3=A4?= <lauri.kentta@gmail.com>, 
	Nikita Popov <nikita.ppv@gmail.com>, "internals@lists.php.net" <internals@lists.php.net>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Subject: Re: [PHP-DEV] Re: Improving mt_rand() seed
From: leight@gmail.com (Leigh)

On 27 January 2017 at 02:52, Yasuo Ohgaki <yohgaki@ohgaki.net> wrote:
> 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)=E2=88=921. Offset within the stream is as important as the str=
eam
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 =3D 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 to mt_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 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.

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.