27

Many recommendations for storing passwords recommend hash(salt + password) rather than hash(password + salt).

Doesn't putting the salt first make it much faster for the attacker to bruteforce the password, because they can precompute the state of the hashing function with the bytes of the salt, and then each time of their billions and trillions attempts they only need to finish calculating the hash using the bytes of the password.

In other words, each bruteforce iteration needs to calculate only the hash of the password intermediateHashState(password) instead of the whole hash(salt + password).

And if the salt was placed after the password, the attacker wouldn't have this shortcut.

Does this advantage exist and is it significant?

4 Answers4

35

Actually, you are tackling it the opposite way.

It is true that doing hash(salt + password) would allow you to precompute the salt (but see note below) and only hash each password candidate for all those trials. The cost be the same you would bear if you were not using a salt at all.

However, the goal of the salt is not to make bruteforcing a single hash harder, but to ensure that the hashes for different users are different even if they chose the same password and so the cracking effort can't be applied for multiple users.

Let's assume you dumped a PayPal database hashes where they were using MD5 hashes. You want to check passwords 'paypal', 'PayPal', 'PayPal123'...

  1. If they used MD5(password), you can trivially hash any of them and find out if anyone is using such weak password.

  2. If they used MD5(salt + password), you could precompute the partial MD5(salt) for everyone, but still need to hash each password candidate for each user.

  3. If they used MD5(password + salt), you could precompute the partial MD5(password) for each candidate password, and then apply their salt for each user.

#1 is clearly the worst here. You could argue between #2 and #3 based on the different lengths of passwords and salts, as well as the number of users, but I would consider #2 to be preferable. Based on length alone, the enforced minimum length for your passwords is probably higher than the salt size. But I suspect there could be other weakness with the #3 construct, too.

Is it a significant advantage?

Not really.

First of all, many hash functions work in blocks, and the precomputation for values smaller than the block size simply store a copy of the "precomputed bytes". In 99% of the cases the length of both salt and password will be shorter than the block size, so actually there would be no real precomputation being performed. You would need to be using really long strings there for that to be of use.

Additionally, any modern password hash function will at the very minimum use many iterations, if not using more advanced means to make bruteforcing expensive, and your optimization is only applicable the initial iteration.

In any case, rather than simply concatenating salt and password, the most secure way to combine them would be to do an HMAC over them, which mixes them in a better way.

Ángel
  • 17,578
  • 3
  • 25
  • 60
  • 5
    Are you sure about the ability to precompute MD5(password) and later add the salt (or vice versa)? If the password is the size of an MD5 block I wouldn't doubt it, but MD5 uses a 512 bit block and most passwords (or salts) aren't exactly 64 characters. – AndrolGenhald Jun 08 '19 at 00:10
  • @AndrolGenhald it would partially precompute, up to the working register that requires salt bytes – Richie Frame Jun 08 '19 at 00:12
  • @AndrolGenhald Yes. I used MD5 as an example as I knew it allowed this (just like eg. SHA-1) while that wouldn't be available with others such as PBKDF2. MD5 construct allows you to add bytes or even bits. You would simply do MD5_Update() with the bytes you have, updating the internal state. The piece you wouldn't do is to skip the MD5_Final(), so you can continue adding bytes (the final operation "closes" the hash computation by performing some final steps such as adding a bit length). – Ángel Jun 08 '19 at 00:20
  • 1
    @Ángel MD5_update() will not precompute unless you have a full block, anything less and it will just keep it in a buffer – Richie Frame Jun 08 '19 at 00:28
  • @RichieFrame the MD5_CTX)is what holds the precomputation. But you are right, until it reaches the block size for MD5 it simply memorizes the provided bytes. – Ángel Jun 08 '19 at 00:36
  • 1
    @Ángel Then don't you think it's a _little_ bit misleading to say you can precompute the partial MD5(salt)? A salt or password by itself is almost never going to be large enough to compute the first block. – AndrolGenhald Jun 08 '19 at 00:45
  • 2
    @AndrolGenhald you are completely right. My answer was in a different line, and I didn't take into account this. I have edited the answer adding a paragraph about this on the part discussing if it would be a significant advantage. – Ángel Jun 08 '19 at 00:59
  • Do you mean salt length rather than "length size"? – nsandersen Jun 09 '19 at 17:26
  • @nsandersen Indeed. "length size" didn't make sense there. Fixed. Thanks! – Ángel Jun 10 '19 at 00:31
  • +1 this is the real answer. The purpose of the salt was never to make a single password harder to hash, but to help with multiple passwords. – user541686 Jun 10 '19 at 20:20
25

Many recommendations for storing passwords recommend hash(salt + password) rather than hash(password + salt).

Those recommendations are evidently bad, because what they should be telling you is to use a password hashing function that's been specially designed for the purpose, like (in rough order of newer and betterish to older and worse-ish):

  • Argon2 (best)
  • scrypt
  • bcrypt (not bad but beginning to look dated)
  • PBKDF2 (far from ideal but much better than homebrew password hashing)

These functions either:

  1. Take the password and the salt as separate arguments, and thus take care of your question internally;
  2. Give you a higher-level API that takes care of salt generation and management internally:
    • An "enrollment" function that takes a password, generates a salt, and outputs a verification string that encapsulates both salt and hash (e.g., password_hash() in PHP);
    • A "verification" function that takes a password and verification string, and verifies that the password matches the latter (e.g., password_verify() in PHP).

If you're manually concatenating passwords and salts, you're doing it wrong.

That said, it's generally better for a password hashing function to absorb the salt first and the password after. Why? Because that order is generically better at resisting precomputation attacks. In the password-first order, the attacker can precompute the intermediate states that correspond to common passwords, and perhaps there is some clever way of building some sort of big table that exploits this to compute their salted hashes quicker than they could otherwise. Whereas the salt-first order makes this impossible, more so if salts are random.

Doesn't putting the salt first make it much faster for the attacker to bruteforce the password, because they can precompute the state of the hashing function with the bytes of the salt, and then each time of their billions and trillions attempts they only need to finish calculating the hash using the bytes of the password.

No, because the point is that the attacker is not supposed to learn the salts before they steal the password database. That bit of precomputation you mention only gives a tiny speedup relative to the cost of a well-designed password hashing function, and the precomputed state is only good for attacking one individual password entry (assuming no duplicate salts, which is a requirement anyway).

In contrast, with the password-first order, they can:

  • Precompute and store hash function states for large numbers of common passwords before they ever steal the password database;
  • Reuse the precomputed tables across password entries hashed with different salts, even across multiple password databases.
Luis Casillas
  • 10,181
  • 2
  • 27
  • 42
  • 3
    PBKDF2 should be retired. If a developer has the freedom to choose what algorithm to use then they shouldn't use it. Or any function that only stretches passwords by iterating an easily parallelized hash many times. Bcrypt is a step up - it's a simple algorithm iterated many times, but it's not one that GPUs can do easily - but many-core computers and FPGAs can attack it [much more efficiently](https://www.openwall.com/presentations/Passwords13-Energy-Efficient-Cracking/) – Future Security Jun 08 '19 at 02:01
  • 1
    @FutureSecurity I disagree. The ability to choose the hash function in PBKDF2 is useful for optimization purposes. For example, a 32-bit system would be better off with SHA-256, whereas a 64-bit system would be better with SHA-512. If they have hardware SHA-1 acceleration, then that would be preferable. – forest Jun 08 '19 at 05:50
  • 1
    The only bad thing about this answer is that it promotes PHP. Not a friendly language for security. But +1 anyway. – jpmc26 Jun 08 '19 at 13:43
  • 2
    @forest Even if you have SHA-1 acceleration, you should not use SHA-1. The objective here is to minimize the ratio of (attacker's hash rate)/(your hash rate). A memory-hard hash scores better than SHA-1 no matter what hardware acceleration you have. Recall that you're hashing one password at a time while the attacker isn't. – Navin Jun 08 '19 at 15:30
  • 2
    @jpmc26: [I don't actually disagree with your take on PHP](https://security.stackexchange.com/questions/128581/hosting-company-advised-us-to-avoid-php-for-security-reasons-are-they-right/128601#128601), but strangely enough its modern password hashing API **is** exemplary and making more people aware of it does the world a lot of good. – Luis Casillas Jun 09 '19 at 04:55
  • 1
    @FutureSecurity: I've made an edit with a nod to your concerns about PBDKF2, but I do kind of think that PBKDF2 (especially with SHA-512) is a meaningful step up from the homebrew fast hashing code I still too often see. – Luis Casillas Jun 09 '19 at 05:02
  • 2
    @Navin You're absolutely correct, and a proper memory-hard KDF beats hardware-accelerated SHA-1 any day. I was just pointing out that I disagree with the idea that one of PBKDF2's problems is its flexibility. While normally I do agree that flexibility is a bad thing in cryptography and developers shouldn't be given access to complex APIs, in this specific case, I think PBKDF2's flexibility is actually a positive for the aforementioned reasons. Also _technically_ you could probably make PBKDF2 memory-hard since it works with _any_ keyed PRF, not just HMAC. Consider a memory-hard keyed PRF. – forest Jun 09 '19 at 07:24
  • 3
    One key advantage that PBKDF2 still has is that it's the only one that's NIST approved, which is relevant in orgs where compliance is important. Hopefully they'll publish a new recommendation soon, though. – James_pic Jun 10 '19 at 10:34
  • 1
    I would recommend PBKDF2 over bcrypt (or even omit bcrypt from the recommendations entirely). While neither of the two is memory-hard, PBKDF2 does everything that bcrypt does and avoids some of its drawbacks (such as [semi-arbitrary password length limits](https://security.stackexchange.com/q/39849)). And even if the only password hashing function your crypto library provides is bcrypt, [PBKDF2 is easy to implement](https://crypto.stackexchange.com/a/24933) as long as you have access to a suitable PRF such as HMAC (which itself is easy to implement using any cryptographic hash like SHA-2). – Ilmari Karonen Jun 10 '19 at 17:02
14

Hash functions recommended for password use do not have this advantage - I'm not sure that any non-trivial hashing functions do, in fact, but wouldn't want to make a blanket statement there.

Instead, hashing functions mix parts from the whole input in each stage. For example, given the input ABCDEFGHIJKLMNOPQRSTUVWXYZ, the first step could be something like pairing the first character with the last, and iterating until no input is left. This would give AZBYCXDWEVFUGTHSIRJQKPLOMN. Assume the "salt" was ABCDEF, and the password was the rest, then change the password to PASSWORD - the output of this example first step would be ADBRCODWESFSPA, which wouldn't help you with the original hash in the slightest.

This is just an example - real hash functions work on binary values, and perform more complex mixing, for a couple of differences - but you can see that it doesn't matter where the salt is for the output to change at a very early point.

There is even a principle (the Avalanche Effect) which suggests that a single bit being changed in the input to a hash function should change about 50% of the output bits, and most hash functions, even ones which are now considered unsafe such as MD5, follow this (while my example above does not!).

Essentially, you can't pre-compute part of a hash in the way you suggest, unless there are other flaws in the system. If you, for some reason, hashed the salt, took the first half of the output, and bolted it onto the second half of the hash of the password for storage, that would introduce the theoretical weakness so you'd only need to compute the hashes of passwords.

Matthew
  • 27,233
  • 7
  • 87
  • 101
  • 24
    I don't quite agree with the explanation. Hash functions do usually work in blocks, so they don't mix parts from the whole input in each stage. If you have two plaintexts that share a common prefix of blocks, the hash state of the common blocks can be re-used. However, the block size of even SHA-256 is 64 bytes, so this is not an issue for this application. – wrtlprnft Jun 07 '19 at 21:27
  • 13
    The explanation in paragraph two is nothing like real world hash functions. Plus it doesn't follow from a hash function exhibiting the avalanche effect that there is no way to use partial evaluation to optimize brute force. – Future Security Jun 08 '19 at 01:48
  • Aha. So a 64-byte salt could actually make it easier to bruteforce. –  Jun 08 '19 at 05:43
  • Agree with the other two commenters here, the explanation of how hash functions work is patently wrong\. You can look at the [pseudo code](https://en.wikipedia.org/wiki/SHA-2#Pseudocode) for proof positive that the most popular current hash algorithm linearly goes through the message. I also don't see how the avalanche effect applies here. Looking at the pseudo code it's quite obvious that if two messages share the first K*64 bytes you can very easily precompute the hash. – Voo Jun 08 '19 at 08:02
  • 3
    @Voo, that’s just one of the reasons why you shouldn’t be using any SHA variant for hashing passwords. You want a specialized password hashing algorithm which doesn’t have that problem. – cjm Jun 09 '19 at 00:12
  • @cjm The point is the first claim does not hold for all cryptographic hashes and the avalanche effect is irrelevant. This answer does not provide any evidence that scrypt or similar algorithms would not be susceptible to this if the salt was at least one block size. It might very well be the case, but given the complexity of the topic I'd like some actual reference first. – Voo Jun 09 '19 at 01:57
  • 4
    @cjm : PBKDF2 is not a perfect password hashing function, but the fact it is based on SHAx is not seen as one of its weaknesses. – Martin Bonner supports Monica Jun 10 '19 at 09:02
2

While the above answers do raise some valid points they do not seem to be entirely correct and it should be noted that there do in fact exist weaknesses in certain hash functions that make a significant difference in the cracking speeds for "$pass.$salt" or "$salt.$pass".

See for example md5. According to atom (https://hashcat.net/forum/thread-8365.html), creator of the hashcat password cracking software:

The way how hashcat exploits some weakness in MD5 to get additional acceleration requires it to change only the first 4 bytes of the input data. Since this part is fixed (because of the salt) it cannot use the acceleration.

That does reflect significantly in the cracking speed.
On a Titan RTX the speed for md5($pass.$salt) is with 63819.9 MH/s almost double the speed as for md5($salt.$pass) with "only" 34696.2 MH/s.

Similar differences exist for other hash algorithms. The developers and community of password cracking software spend a significant amount of time to find weaknesses and shortcuts to improve speed. So from a cracking perspective it can be a good idea to look at current hashcat benchmarks like this one https://gist.github.com/Chick3nman/5d261c5798cf4f3867fe7035ef6dd49f and compare the speeds for the different Salt-Password-Variants.
If that link goes missing, you can also generate your own benchmark with the following command:

hashcat -b
Denis
  • 3,653
  • 2
  • 17
  • 16