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).

Solution 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.

Solution 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.

Solution 3

I think you need to ask yourself "What are you hoping to gain by making this more complicated than just generating a random salt value and storing it?" The more complicated you make your algorithm, the more likely you are to introduce a weakness inadvertently. This will probably sound snarky no matter how I say it, but it's meant helpfully - what is so special about your app that it needs a fancy new password hashing algorithm?

Solution 4

Why not add a random salt to the password and hash that combination. Next concatenate the hash and salt to a single byte[] and store that in the db?

The advantage of a random salt is that the user is free to change it's username. The Salt doesn't have to be secret, since it's used to prevent dictionary attacks.

View more solutions

Comments

[Kane Wallmann]

Salting also protects us from a rainbow table based attack

[Sam Saffron]

+1 for mentioning that a user is no longer free to change their user name !

[Jonathan Leffler]

I think you may well be right - as I wrote the question, I realized the random salt was necessary; I didn't take the time to note that it was sufficient, too. Having said that, one concern is to give the hash algorithm more data to work on - and user name helps a bit, as does the salt. Recovery to another DBMS server instance is a valid concern - one I'd not thought of. Username and salt would be fine under that, and user name is not 100% necessary. Thanks.

[Jonathan Leffler]

@pb: in this context, I don't want users changing their name, thanks. In some contexts, that might be valuable, but as far as this app is concerned, a user's name is fixed (or, more accurately, if someone changes their name they become a new, different user). Just using random salt and password is probably OK; I'm a little concerned to ensure that there is enough material for the hash algorithm to get its teeth into - that is another part of the reason for adding more than just the salt. As I wrote the question, I realized the random salt was necessary; I didn't notice it was sufficient too.

[Jonathan Leffler]

Yes; as I've noted in comments to other answers, my question morphed as I wrote it, and I realized the random salt was necessary, but didn't take the time to reflect that it was also sufficient. Adding the user name to the mix mainly lengthens the data that the hash algorithm has to work on, helping protect short passwords. How real that extra protection is, I'm not sure.

[Jonathan Leffler]

@Peter: no offense taken - I understand what you're saying. One aspect of "what's different" as I was writing was "make sure different servers with the same password store different keys". As noted in other comments, I realized near the end of the question that the random salt was necessary; I didn't spot that it was sufficient. And the extra data in the hash helps protect short and poor passwords. What I can't assess is how much difference that makes.

[Jonathan Leffler]

Continuing: If the salt is an 8-byte integer and the password is a single letter, does an SHA-256 hash really protect it enough? If the user name is 3 characters and the 'server unique' data was, say, a 32 character randomly determined (but fixed) string, does that help protect the data - 44 bytes of data to work on instead of just 9. It seems like it should be safer (9 bytes could be rainbow attacked; 44 bytes probably couldn't as easily be attacked). Maybe the 'server unique' just needs to be a 'fixed 32-byte string'; ...

[wprl]

the user would still be able to change their username, but you would have to rehash their password at that time. On the other hand, using a random salt has the same or greater benefits as using a non-random salt.

[Glenn Maynard]

This answer is wrong. The purpose of salts is not so "shared passwords aren't obvious". The purpose is to make dictionary attacks much harder. (Allowing dangerously incorrect responses like this to be marked as an "answer" is a fatal design flaw of this site.)

[Colin Mackay]

"Dangerously wrong"? It may be incomplete (it does help protect in the case of two users that happen to share the same password), but where is the danger in this answer? If I know, I'll gladly correct the answer.

[btilly]

@ColinMackay I suggest that you read codahale.com/how-to-safely-store-a-password to find out why your answer is dangerously wrong. The long and short of it is, "brute force is faster than you think". Having the salt is necessary - without it people can just use a precomputed lookup table - but not sufficient to protect users with weak passwords (that would be most of them).

[Dan]

@GlennMaynard: I agree with your last portion of your statement. There should be a Vetoable icon bellow the checkmark icon, once an answer is accepted as to: a) Provide the user time to update their answer, or b) To force the answer as 'vetoed'.

[DeveloperChris]

@btilly The link you provide is pure (dangerous) bunkum. bcrypt is no more effective at preventing brute force attacks than salting a password. The aim of an attacker is to gain access. Therefore all he needs to do is bruteforce possible passwords, not hashes. The bcrypt alternative moves the computational expense to the server and is therefore a waste of resources, nothing more. If you use a password 12345 and I brute force that password, no matter what weird computationally expensive encryption technique you use you are pwned. A random salt is just fine and don't allow weak passwords!

[FrankRuperto]

Glenn Maynard and DeveloperChris make compelling arguments. No matter how much you disguise a stored password, a brute force attack will succeed in cracking it if user chose a weak one.

[Colin Mackay]

"No matter how much you disguise a stored password, a brute force attack will succeed in cracking it if user chose a weak one." So, how is this the fault of the algorithm used to disguise the password? Going by your response, we might was well just throw our hands in the air and say "sod it! There's no point, the users are too stupid and they're going to get cracked anyway."