Re: Password_hash salt generation refactor

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