39

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:

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

Community
  • 1
  • 1
Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
  • 1
    The random part is important it prevents prediction attacks – Jacco Dec 26 '09 at 13:19
  • you could add http://stackoverflow.com/questions/1645161/salt-generation-and-open-source-software/1645190#1645190 to your article list – Jacco Dec 27 '10 at 09:13
  • Also add http://dba.stackexchange.com/questions/7492/password-hashes-fixed-length-binary-fields-or-single-string-field as a good lead in to the [dba.se] site – jcolebrand Nov 02 '11 at 15:36
  • 2
    Adding the username to the salt requires the password plaintext to be available to reset the password hash if you ever want to change the username. If that's an issue. – blueshift Dec 09 '11 at 04:59
  • 1
    From all the comments bellow I did not see an answer in regards to where the salt should go (before or after)? I was wonder if it was harder to brute-force a hash if the salt is located before, after or possibly both, or maybe it doesn't really matter where its put? – Jeach Jun 12 '12 at 17:39
  • @Jeach: I don't think it makes a lot of difference, but I'd put the salt at the start so it has maximum chance to affect the hash computed from the following password. However, it should randomize OK at the end too. Even better, perhaps, put some of the salt before and some after. Do it differently from other people. That means that the attacker has to custom target your salted hashed passwords, rather than being able to use work done on other people's passwords. (See the LinkedIn attack.) It increases the amount of work that has to be done on average. The attacker might get lucky, even so. – Jonathan Leffler Jun 12 '12 at 18:08
  • 2
    @blueshift I'm no cryptographer, but…couldn't you get around this by requiring the password to be provided in order to change the username? – Blacklight Shining Nov 22 '12 at 13:12
  • @BlacklightShining: Yes. – blueshift Nov 22 '12 at 16:18

4 Answers4

31

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.

Skotch
  • 3,072
  • 2
  • 23
  • 43
Colin Mackay
  • 18,736
  • 7
  • 61
  • 88
  • 5
    Salting also protects us from a rainbow table based attack – Kane Wallmann Jul 27 '09 at 23:11
  • 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 Jul 28 '09 at 07:10
  • 13
    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.) – Glenn Maynard Mar 05 '12 at 16:06
  • "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. – Colin Mackay Mar 06 '12 at 12:45
  • 3
    @ColinMackay I suggest that you read http://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). – btilly May 29 '12 at 17:41
  • @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'. – Jeach Jun 12 '12 at 17:36
  • 3
    @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! – DeveloperChris May 09 '13 at 23:03
  • 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. – Joe R. Nov 08 '18 at 00:16
  • "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." – Colin Mackay Nov 14 '18 at 13:15
19

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.

Sam Saffron
  • 128,308
  • 78
  • 326
  • 506
  • 1
    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 Jul 28 '09 at 07:03
7

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?

Peter Recore
  • 14,037
  • 4
  • 42
  • 62
  • @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 Jul 28 '09 at 07:15
  • 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'; ... – Jonathan Leffler Jul 28 '09 at 07:17
  • Continuing (2): ... or maybe it needs to pad 'salt plus password' to 64 bytes (or 32 bytes, or some other number) with fixed string? Or maybe this is all a grand goose chase; it really doesn't matter. – Jonathan Leffler Jul 28 '09 at 07:21
6

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.

Paul van Brenk
  • 7,450
  • 2
  • 33
  • 38
  • 2
    +1 for mentioning that a user is no longer free to change their user name ! – Sam Saffron Jul 28 '09 at 00:50
  • @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 Jul 28 '09 at 07:07
  • 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. – wprl Dec 03 '10 at 20:31