Web app passwords: bcrypt and SHA256 (and scrypt)

Question

With all the recent (e.g. LinkedIn) discussions of passwords I'm looking at password hashing implementations. After two cups of coffee and a morning reading I'm no more a cryptographer than when I started. And I really don't want to pretend that I am.

Specific Questions

1. Does using a integer unique user ID fail as an effective salt? (crypt() uses only 16 bits?)

2. If I simply run sha256() on a hash over and over until a second is used up does that defeat the brute-force attacks?

3. If I have to ask these questions should I be using bcrypt?

Discussion/Explanation:

The goal is simply if my user's hashed passwords were leaked they:

1. would not be "easy" to crack,
2. cracking one password would not expose other users that use the same password).

What I've read for #1 is the the hash computation must be expensive -- taking, say, a second or two to calculate and maybe requiring a bit or memory (to thwart hardware decryption).

bcrypt has this built in, and scrypt, if I understand correctly, is more future-proof and includes a minimum memory usage requirement.

But, is it an equally effective approach to eat time by "rehashing" the result of sha256() as many times as needed to use up a few seconds and then store the final loop count with the hash for later checking a provided password?

For #2, using a unique salt for every password is important. What's not been clear is how random (or large) the salt must be. If the goal is to avoid everyone that uses "mypassword" as their password from having the same hash is it not enough to simply do this?:

hash = sha256_hex( unique_user_id + user_supplied_password );

or even this, although I'm not sure it buys me anything:

hash = sha256_hex( sha256( unique_user_id ) + user_supplied_password );

The only benefit I can see from using the user's ID, besides I know it is unique, is avoiding having to save the salt along with the hash. Not much of an advantage. Is there a real problem with using a user's ID as the salt? Does it not accomplish #2?

I assume if someone can steal my user's hashed passwords then I must assume they can get whatever they want -- including the source code that generates the hash. So, is there any benefit to adding an extra random string (the same string) to the password before hashing? That is:

# app_wide_string = one-time generated, random 64 7-bit *character* string.
hash = sha256_hex( unique_user_id + app_wide_string + user_supplied_password );

I have seen that suggested, but I don't understand what I gain from that over the per-user salt. If someone wanted to brute-force the attack they would know that "app_wide_string" and use that when running their dictionary attack, right?

Is there a good reason to use bcrypt over rolling my own as described above? Maybe the fact that I'm asking these questions is reason enough?

BTW -- I just timed an existing hashing function I have and on my laptop and I can generate about 7000 hashes a second. Not quite the one or two seconds that are often suggested.

Some related links:

using sha256 as hashing and salting with user's ID

SHA512 vs. Blowfish and Bcrypt

What is the optimal length for user password salt?

Answer 1

Bcrypt is great because you can tune the work factor from 4 to 31, each increment creates an exponentional required time, I've actually graphed it, at a work factor of 14 it's already taking over a second, so as computers get faster and faster you only need to change one parameter, and of course update your password hashes ...

My main concern with bcrypt is that if the work factor is set to high, then it may overload your system as multiple users are trying to login so you have tune it, depending on the number of of concurrent logins and the resources of your system ...

Salts are still required, their main purpose is to deterred off-line attacks, if the salt space is to large, then the adversary won't be able to generate the look up table, 64 bit salt seems a bit low, bcrypt has 128 bit salts coupled with the work factor makes it quite a challenge for offline attacks ... and yes the salt should be random for each password, bcrypt will generate one for you, if you use the same salt for each password then you have made it eassier for the adversary to comprimised all the passwords using an online attack.

Bcrypt really shines for online attacks, if you have set the work factor properly, because even if I get the hash, meant to say if the 'adversary' gets the hash, the work factor makes it really painful to go through an entire dictionary, taking multiple days and if the password isn't in the dictionary, then I'm really in trouble cause a brute force attack will be epic, the password bit space for bcrypt is quite large though finite :)

Sha256 may be taking a bit of time now, but eventually computers will get faster and faster and it'll be fairly easy for attacks, the unix guys thought crypt was so slow it would have never being an issue, and today I have done an online attack in seconds, offline attack in days, a brute force attack (going through the entire password bit space) in weeks ...

1. you want the salt to be as large and random as possible using only numbers makes it easier for me to iterate over all the possible ids.
   
2. multiple sha256 may take a second now but down the road it won't be effective any more, computers processing power grows exponentially and so you want an algorithm that can be configured as such.
   
3. you are doing the right thing by asking questions and doing your homework if more people did this we wouldn't have so many breaches