Password hashing, salt and storage of hashed values

Question

Suppose you were at liberty to decide how hashed passwords were to be stored in a DBMS. Are there obvious weaknesses in a scheme like this one?

To create the hash value stored in the DBMS, take:

• A value that is unique to the DBMS server instance as part of the salt,
• And the username as a second part of the salt,
• And create the concatenation of the salt with the actual password,
• And hash the whole string using the SHA-256 algorithm,
• And store the result in the DBMS.

This would mean that anyone wanting to come up with a collision should have to do the work separately for each user name and each DBMS server instance separately. I'd plan to keep the actual hash mechanism somewhat flexible to allow for the use of the new NIST standard hash algorithm (SHA-3) that is still being worked on.

The 'value that is unique to the DBMS server instance' need not be secret - though it wouldn't be divulged casually. The intention is to ensure that if someone uses the same password in different DBMS server instances, the recorded hashes would be different. Likewise, the user name would not be secret - just the password proper.

Would there be any advantage to having the password first and the user name and 'unique value' second, or any other permutation of the three sources of data? Or what about interleaving the strings?

Do I need to add (and record) a random salt value (per password) as well as the information above? (Advantage: the user can re-use a password and still, probably, get a different hash recorded in the database. Disadvantage: the salt has to be recorded. I suspect the advantage considerably outweighs the disadvantage.)

There are quite a lot of related SO questions - this list is unlikely to be comprehensive:

• Encrypting/Hashing plain text passwords in database
• Secure hash and salt for PHP passwords
• The necessity of hiding the salt for a hash
• Clients-side MD5 hash with time salt
• Simple password encryption
• Salt generation and Open Source software
• Password hashes: fixed-length binary fields or single string field?

I think that the answers to these questions support my algorithm (though if you simply use a random salt, then the 'unique value per server' and username components are less important).

Answer 1

The salt just needs to be random and unique. It can be freely known as it doesn't help an attacker. Many systems will store the plain text salt in the database in the column right next to the hashed password.

The salt helps to ensure that if two people (User A and User B) happen to share the same password it isn't obvious. Without the random and unique salt for each password the hash values would be the same and obviously if the password for User A is cracked then User B must have the same password.

It also helps protect from attacks where a dictionary of hashes can be matched against known passwords. e.g. rainbow tables.

Also using an algorithm with a "work factor" built in also means that as computational power increases the work an algorithm has to go through to create the hash can also be increased. For example, bcrypt. This means that the economics of brute force attacks become untenable. Presumably it becomes much more difficult to create tables of known hashes because they take longer to create; the variations in "work factor" will mean more tables would have to be built.

Answer 2

I think you are over-complicating the problem.

Start with the problem:

1. Are you trying to protect weak passwords?
2. Are you trying to mitigate against rainbow attacks?

The mechanism you propose does protect against a simple rainbow attack, cause even if user A and user B have the SAME password, the hashed password will be different. It does, seem like a rather elaborate method to be salting a password which is overly complicated.

• What happens when you migrate the DB to another server?
  • Can you change the unique, per DB value, if so then a global rainbow table can be generated, if not then you can not restore your DB.

Instead I would just add the extra column and store a proper random salt. This would protect against any kind of rainbow attack. Across multiple deployments.

However, it will not protect you against a brute force attack. So if you are trying to protect users that have crappy passwords, you will need to look elsewhere. For example if your users have 4 letter passwords, it could probably be cracked in seconds even with a salt and the newest hash algorithm.