Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:100232
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain gmail.com designates 209.85.223.174 as permitted sender)
MIME-Version: 1.0
In-Reply-To: <CAPwsocE+8_4J9ZFtWbExH4mKG1haMs1c0OsTXUijn_+rNUN5wQ@mail.gmail.com>
References: <20170816191247.GA12324@openwall.com> <CAPwsocE+8_4J9ZFtWbExH4mKG1haMs1c0OsTXUijn_+rNUN5wQ@mail.gmail.com>
Date: Wed, 16 Aug 2017 22:06:02 +0200
Message-ID: <CAF+90c82H_4z5TGmKJGS1_Md0c15DvMBngPxUp=Upsx3mb0_2g@mail.gmail.com>
To: Leigh <leight@gmail.com>
Cc: Solar Designer <solar@openwall.com>, PHP internals <internals@lists.php.net>
Content-Type: multipart/alternative; boundary="001a11409da2dd8c6e0556e46cb7"
Subject: Re: [PHP-DEV] PHP 7.1.0 to 7.2.0beta2 mt_rand() modulo bias bug
From: nikita.ppv@gmail.com (Nikita Popov)

--001a11409da2dd8c6e0556e46cb7
Content-Type: text/plain; charset="UTF-8"

On Wed, Aug 16, 2017 at 9:47 PM, Leigh <leight@gmail.com> wrote:

> On Wed, 16 Aug 2017 at 20:13 Solar Designer <solar@openwall.com> wrote:
>
> > Also, why even bother to support ranges beyond 32-bit?  Sounds like a
> > misfeature to me, considering it won't(?) be universally available on
> > all PHP builds anyway (not on 32-bit ones, right?) and thus shouldn't(?)
> > be relied upon by applications (although it might become reasonable for
> > application developers not to care about 32-bit soon).  I also see few
> > use cases for it, even if it were universally available.
> >
>
> It was possible (on 64 bit builds) to specify min and max such that the
> size of the output required from mt_rand was the full 64 bit range.
>
> Prior to 7.1 this full output was created by stretching a single 32 bit
> output up to the required range using floating point arithmetic, which
> caused other biases in the output.
>
> Unfortunately when fixing this bias, a new bias was introduced. I took
> known working code from the CSPRNG and didn't account for the variable
> length of the sample.
>
> My proposed fix would be to add a "limit_max" variable, initialise it to
> UINT32_MAX, and in the first range check where we decide to add an extra
> output or not, set it to ZEND_ULONG_MAX. Then the statement creating the
> ceiling value can use limit_max instead of the constant value.
>

I'd suggest to split the 32-bit and 64-bit code codepaths entirely, as the
interleaved #ifs are somewhat hard to follow. Something like
https://gist.github.com/nikic/64e7ec58ebb6121d350fb80927a65082 (not
thoroughly tested).

Nikita

--001a11409da2dd8c6e0556e46cb7--