Will hashing over and over eventually give the same hash?

Question

There are many cases in maths where doing the same thing over and over again will bring you closer to a value. Derivation of polynomials is the striking example: no matter what you start with, you end up with 0. In a series expansion, the longer you continue the sequence the closer you get to the real value.

This concept applies in areas other than math (Wikipedia's everything-leads-to-philosophy phenomenon, for example). It's a little unrelated but it just proves the concept.

Hashing algorithms are just special math. Following logically, hash entropy supposedly decreases the more you hash a value. So is there a point at which any input value will give the same hash as any other?

(Let me just specify that we're not re-injecting any new data every time we hash, as if we're trying to increase the security of the hash by salting and re-hashing. It's strictly a matter of md5(md5(md5(... if that's the algorithm we're using.

I can see some problems with this already. Algorithms like md5 are designed to change their output radically when the input changes only by one bit of information. So even if a common hash for two values appears along the way, it itself will start changing. But then, does the fact that the output appears to be very different actually mean the possibilities are still many?

Answer 1

In general, collisions in a hash function are a bad thing: if you have different $M_1$ and $M_2$ for which $hash(M_1)=hash(M_2)$, the situation will require special handling.

In cryptography, hash functions can be seen as "summary" functions, that reduce a message of arbitrary length to messages of fixed length. Since the message space (all the possible messages) is usually way larger than the hash space (all the possible hashes), you are bound to have collisions.

There are several ways for an attacker to violate a hash function, but for this scenario, let us take a random value $H_1$ in the hash space. It could be a hashed password you retrieved from a server, for instance. What matters is that it is fixed.

In most cases, like the hashed password, the attacker does not need to know the original password. He only needs to know a random password $P$ such that $hash(P)=H_1$. That is definitely undesirable, and that is why cryptographic hashing functions are designed to be collision resistant. That means that, for an attacker with the most efficient polynomial algorithm to attack the hash function, it would take ages (a longer time than the time of existence of humanity) to find a collision.

All that said, what you want to find is some $M$ for which $H(H(H(...H(m)...)))$ some amount of times, gives again $H(M)$. That is mathematically possible (and certain to obtain), but your lineage will probably not live to see it.

As a final note: the password example is clearly flawed, since there are more specific attacks against it (like dictionary attacks and rainbow tables), but it is enough for the sake of your scenario.