Storing multiple hashes to prevent collisions, security risk?

Question

This is all just for curiosity's sake, so discussion on which hashing algorithm is harder/better/faster/stronger is irrelevant. But my question/thought is this..

With regards to password storage, and to prevent hash collisions, I was thinking that one possibility would be to create one hash that is basically salted and hashed, and then create any number of alternate hashes where the password is modified in some unique way (Rot-13, Reversed, etc.), then salted with a different salt and hashed. Then store and compare all the hashes when logging in.

Would this situation be easier to crack, given that the attacker has more information to get at the actual password? Or is it more difficult given that the attacker now has to crack multiple hashes to get at the password?

UPDATE: let's assume the hashing algorithm used is something ridiculous (and fast) like MD5, and that the attacker has gained access to the database through whatever means.

Also, some of the modified hashes may have been run through a hashing algorithm as part of it's "modification".

Answer 1

This is not a good idea.

The first reason is that collisions are not an issue. For password hashing, you don't rely on resistance to collisions, but on resistance to preimages. There is no need for a password hashing function to admit easy-to-build collisions, but if it does, this is not a problem either. For instance, collisions can be built with PBKDF2. And we don't mind.

The second reason is that the attacker intent on finding a password which matches a given hash has no need to compute several hashes. The attacker tries a long list of potential passwords, but that list is way smaller than the hash function output range. The consequence is that when the attacker finds a matching password, it is the password -- and this is so even when the attacker works over a single hash function. Therefore, though you spend the CPU to compute several hashes, the attacker is perfectly content to work with only one. In other words, the several hashes waste your CPU. This is important because you normally want to use a slow hash (with a configurable number of iterations) so that attacks are made slower. By doing the job several times, you force yourself to lower the iteration count, thereby automatically giving an advantage to the attacker.

The third reason is a generalization of the previous one: the attacker only needs to work on one hash value. If you provide several, then this can only help the attacker: he will choose the one which makes things easiest for him.

Summary: your "several hashes" idea does not solve an actual problem, but it may help the attacker. So don't do it. As @Iserni explains, use bcrypt. For a more detailed treatment on how password hashing should be done, read this.

Answer 2

In short: best not do it. A better solution would be to use something like BCrypt. You can use a higher number of rounds to ensure that attacking that is computationally infeasible.

As for added or diminished security: it depends on whether the hashes leak. In both cases the difference in security isn't so great, so that all that's happening is that you're burning CPU cycles that might have been used for bcrypt.

If the hashes aren't leaked to the attacker, then your system is negligibly more secure, because even if by any chance a hash collision was found, it is improbable in the extreme that the collision would extend to the alternate hashes. So this solution defends against collisions. But since the chance of a collision is very small in the first place, making it even smaller has an advantages-over-costs ratio which is practically zero.

If the hashes do leak to the attacker, then he has that many more hashes to attack. The system becomes proportionally less secure, if discovering the source of a variant hash gives hints on what the real password might be. For that reason, the variant hash ought to be itself a hash (and just in case, a binary hash, and obtained by a different algorithm). Then the attacker has no way of knowing what he has found. The security of the system stays the same, and we just burned some CPU cycles.

UPDATE: let's assume the hashing algorithm used is something ridiculous (and fast) like MD5, and that the attacker has gained access to the database > through whatever means.

Okay, in that case our hypothetical attacker can try and mount a preimage attack or collision attack, or he might just google them all. And he finds, say, f7eedbcbee1453935bc9b36870810f58 on Google.

The probability of finding a hash on Google is loosely (since we're dealing with trivial modifications, but modifications nonetheless) proportional to the number of hashes to attack.

Granted, f7eedbcbee1453935bc9b36870810f58 is not the hash of the "real" password. However, at that point the real password (for which he has a hash to confirm it having being indeed found) is just milliseconds away.

Salting and/or manipulating the hashes changes little. What it does is, increase the security X-fold. But having four hashes instead of one is still roughly, say, up to four times less secure. Salting just makes it so instead of having a fourth of a small number, you have a fourth of a huge number. By using no extra hashes, you would still increase the overall security.