Won't all hashes collide after enough iterations with a static salt?

When iterating a hash function, space reduction occurs, but not down to a single point. For a randomly chosen function (that your "amazing_hash" is supposed to approach), with a n-bit output, you may expect to ultimately reach a cycle of size 2n/2 or so, i.e. still big enough if you use a decent output size (say, n = 256).

See this answer for more detailed explanations. I reproduce here the scheme from that answer, because it is a good eye-catcher:

The "rho" diagram for an iterated hash function

Of course, a "static salt" is not a salt; it just means that you are using a custom hash function. The salt is meant to deter parallel attacks: when the attacker tries to crack 10 passwords, it costs him 10 times the cost of cracking one. With a "static salt", cracking 10 passwords costs no more than cracking 1, i.e. a total failure of the salting.

Salts are not about avoiding collisions, notably because collisions are not a problem for password hashing. It is preimage resistance that you should worry about.


I don't think so, just because the hash would almost certainly reach "common_thing" at different points. One password might has to "common_thing" at step 10,000, and another at step 100,000. The chains will track each other in parallel, but they won't necessarily be at the same point when the algorithm ends.

Whether the cycles are large or small, the probability is still low. If there are many small cycles, a value is less likely to end up in any particular one of them; if there are a few large cycles, the value is less likely to end the chain at the same point.

As other people have said, the reason you don't use a static salt is to keep attackers from creating rainbow tables. I'm not sure that the static salt has any effect on the number of collisions over time, other than that of course identical values will hash to the same value.

Take all this with a grain of salt, though; I'm a crypto enthusiast, but not an expert. I'd love to hear more about cycles in hash algorithms if other people are more informed in this area.


The issue related to the static salt, is not that there are increased chances of collision (there is not). Running the same algorithm repeatedly will not lead to an increase in collisions (with a good hashing function) just so long as all passwords have the same number of iterations.

The real issue is a game of odds.

If an attacker knows the code used to generate the hashed password (the mechanism used to inject the salt, and the number of iterations through the hash loop), then the attacker can reproduce your algorithm. Assume that the attacker also knows your actual hashed result. Can they work out your actual password?

With the algorithm, the attacker can then feed a dictionary of common passwords in to the algorithm, and look for matches to your hashed result. Admittedly, it may take a long time, but, eventually the attacker could guess your password.

The thing is, that you may have a 'hard to guess' password.... but, what about everyone else in the system. Your hashed password is just one of many. If the site is 'stack exchange', then there are thousands of users. If they all use the same salt, then, a dictionary attack like this can check for the match against all the users' hashed passwords. If they get a match, then they have also guessed that user's password. It's a numbers game. If there are 10,000 users in a system, then the odds of finding an easy password are improved by 10,000, likely much more than that.

Now, if you use a unique salt for each user, getting a matching hash for a user is useless unless that user also has the same salt you have in your algorithm.

In other words, with a unique salt, you can only attack one user account at a time. With a static salt, you can attack them all at once.... and the chances of a hit are much greater.

Tags:

Hash