Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:88879
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: error (pb1.pair.com: domain paragonie.com from 209.85.217.177 cause and error)
MIME-Version: 1.0
In-Reply-To: <CABHuAWxiwH5HLnMTPUR26b8RgBdTMJv8BRgNX9qNEk10iELXPw@mail.gmail.com>
References: <CAAyV7nGLiGC_E1YYc21chGSKdUJm1KpZV9V3_rZn5eHOmyEarA@mail.gmail.com>
	<56242DC5.7010306@gmail.com>
	<56250A9C.3050304@thefsb.org>
	<CABHuAWxiwH5HLnMTPUR26b8RgBdTMJv8BRgNX9qNEk10iELXPw@mail.gmail.com>
Date: Mon, 19 Oct 2015 15:43:51 -0400
Message-ID: <CAKws9z2PHdEuz7mhdNm020emOrW-MQrLj4-vZUoUPQpAR9xpTw@mail.gmail.com>
To: Chris Riley <t.carnage@gmail.com>
Cc: Tom Worster <fsb@thefsb.org>, =?UTF-8?B?w4FuZ2VsIEdvbnrDoWxleg==?= <keisial@gmail.com>, 
	Anthony Ferrara <ircmaxell@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] Password_hash salt generation refactor
From: scott@paragonie.com (Scott Arciszewski)

On Mon, Oct 19, 2015 at 1:00 PM, Chris Riley <t.carnage@gmail.com> wrote:
> On 19 October 2015 at 16:22, Tom Worster <fsb@thefsb.org> wrote:
>
>> On 10/18/15 7:39 PM, =C3=81ngel Gonz=C3=A1lez wrote:
>>
>>> Korvin wrote:
>>>
>>>> +1 for 7.0.x security patch release, best effort sounds scary.
>>>>
>>> This is a salt. It doesn't need to be cryptographically secure. Using
>>> php_rand()
>>> there should pose no problem.
>>> I would actually include that into the patch (move old lines 154-156
>>> into the
>>> FAILURE if).
>>>
>>
>> A password salt needs to be unique. It does not need to be drawn from a
>> CSPRNG but that is one of the few ways we can be reasonably confident of
>> uniqueness (since, as usual, we assume the platform RNG is properly seed=
ed).
>>
>
>
> A password salt should not be predictable, allowing a salt to potentially
> become predictable is a bad idea. Solution is to use a CSPRNG for
> generation of salts.

Hi all,

I'd like to weigh in by quantifying the predictability of rand(). If
you're well aware of statistics or versed in cryptography, you might
be able to skip this email. (You might still want to read it to help
verify or challenge my conclusion.)

First, for the sake of generosity, let's assume that rand() is
properly seeded, e.g. by 4 bytes from /dev/urandom, on each invocation
so that the pid + time() issue doesn't come into play. (In reality,
this is very important.)

After seeding rand, there are 2^32 possible outputs. That's a little
over 4 billion, and it's highly unlikely that your website has 4
billion user accounts with a hashed password, so that's good enough
right? Well, not quite.

For a moment, imagine you are in a room with 22 other people born in
the same year as you. What is the probability that any two people in
the room share the exact same birthday? Well, it turns out that the
answer is 50%. We call this the Birthday Problem.

From studying this problem, we can estimate the number of random
samples to generate a collision from an n-bit keyspace by a simple
formula: G =3D 2^(n/2). This is called the Birthday Bound.

If you have a keyspace of 2^32 possible output sequences like we do
from rand(), we can say that after 65,536 there is a 50% probability
of finding at least one collision.

It should go without saying, but if users have weak/common password
choices and their salts collide, they will end up with duplicate
bcrypt hashes.

My conclusion is thus: Yes, we do need a CSPRNG here, especially if we
want to encourage the use of the password_* API for any large system.

https://en.wikipedia.org/wiki/Birthday_problem
https://en.wikipedia.org/wiki/Birthday_attack
http://eprint.iacr.org/2005/004

Scott Arciszewski
Chief Development Officer
Paragon Initiative Enterprises <https://paragonie.com>