Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:88880
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain thefsb.org designates 173.203.187.123 as permitted sender)
To: Scott Arciszewski <scott@paragonie.com>,
 Anthony Ferrara <ircmaxell@gmail.com>,
 "internals@lists.php.net" <internals@lists.php.net>
References: <CAAyV7nGLiGC_E1YYc21chGSKdUJm1KpZV9V3_rZn5eHOmyEarA@mail.gmail.com>
 <56242DC5.7010306@gmail.com> <56250A9C.3050304@thefsb.org>
 <CABHuAWxiwH5HLnMTPUR26b8RgBdTMJv8BRgNX9qNEk10iELXPw@mail.gmail.com>
 <CAKws9z2PHdEuz7mhdNm020emOrW-MQrLj4-vZUoUPQpAR9xpTw@mail.gmail.com>
Message-ID: <562555FD.5020102@thefsb.org>
Date: Mon, 19 Oct 2015 16:43:41 -0400
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.10; rv:38.0)
 Gecko/20100101 Thunderbird/38.1.0
MIME-Version: 1.0
In-Reply-To: <CAKws9z2PHdEuz7mhdNm020emOrW-MQrLj4-vZUoUPQpAR9xpTw@mail.gmail.com>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Subject: Re: [PHP-DEV] Password_hash salt generation refactor
From: fsb@thefsb.org (Tom Worster)

On 10/19/15 3:43 PM, Scott Arciszewski wrote:
> 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, Ángel González 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 seeded).
>>>
>>
>>
>> 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 = 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.

I don't follow the logic of this hypothetical. php_rand() is *only* 
relevant to this discussion if PHP can't read /dev/random or 
CryptGenRandom, in which case we know that the state of php_rand()'s LCG 
is not randomized (it's open to tampering) so this statistical analysis 
is not possible.

I've verified that password_hash() without /dev/urandom can produce 
systematically predictable salts, repeating a sequence of just two 
salts. There's nothing statistical involved. Reported in bug 70743.

Seems crypt() is similarly afflicted.

Tom