Re: Password_hash salt generation refactor

On 19/10/15 21:43, Scott Arciszewski wrote:

(...) 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. That assumes that:

(a) rand() has the same internal state on each password generation. Given that it is seeded once per minit, that suggests they are using something like cgi. Which is not too suitable for large systems. (b) You have people sharing the same password *and* colliding in the same salt bucket. Supposing that you have an equiprobable 4-byte salt (which is actually the case to which we fall if (a) holds), and 152 million users (the amount of the adobe leak, biggest to date) we would only have collisions on the top-13 passwords… not even colliding on 1234 (maybe relax it to the top-16 or top-25 to account for not being completely fairy distributed).Which are passwords in the really really bad zone, and would be cracked even with no help of collisions. And that's another point, a salt used by two users (ie. finding one collision) won't speed you much in terms of cracking their respective passwords. Undesirable? Sure. Broken? Not really. Tom Worster wrote:

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. Only providing two hashes *would* be very worrisome. Note however that you are crippling rand() by always resetting the seed (those two different outputs appear because it is xoring with the same sequence). It's also reading unitialized memory in line 155, which is probably accounting for the salts being different every time. And a change in allocations for the first run being different.

Whereas on a real world usage, even if a new php instance was used every time, you would need a GENERATE_SEED() collision. It initializes the seed using the timestamp, pid, microseconds and thread id (plus any state change caused if different php scripts were run). You have a very good point in that it would fail only if /dev/urandom does not exist at all, my initial concerns came from thinking that it could fail on a low-entropy case, but that won't happen on Linux (urandom always works), and even a urandom blocking OS (eg. on FreeBSD) wouldn't make it use the fallback code. Seems it would only be used if (a) you don't have a /dev/urandom at all or (b) it isn't the special file it is supposed to be (eg. it's a regular file). In which case you are running a broken OS :) So, changing my previous opinion, it'd be acceptable to drop it (I'd prefer it being done in the point release, though). Best regards