If you hashed a hash an infinite number of times would you end up with a unique hash?

Question

If you took a hashing algorithm for example MD5 and repeatedly passed the output hash back into the algorithm an arbitrarily large number of times would you eventually end up with one unique hash?

My idea is that the maximum number of hashes initially is $2^{128}$ however if you feed the hash back into the algorithm there would be collisions so two or more input hashes will map to one single output hash thus reducing the entropy, if this process is repeated indefinitely would it result in one single hash? or is it possible that there would be a point after which no collisions will ever happen?

This is a thought experiment and is probably not possible but I would like to know.

Answer 1

If you repeatedly apply a generic function on its result, in a finite domain, you tend to obtain a "rho" structure: at some point, you enter a cycle whose length is (roughly) $\sqrt{N}$, where $N$ is the size of the output space for your function. In the case of MD5, $N = 2^{128}$ (MD5 outputs 128-bit values), so the cycle will have length about $2^{64}$ values. You can hash "infinitely", you will never end up on a unique value. See this answer for some details and a picture.

Well, strictly speaking, you might end on a unique value, which would be called a fixed point, but we don't know if such fixed points actually exist with MD5. For a randomly selected function, there is a probability of about $63\%$ that a fixed point exists at all. But existence of a fixed point does not mean that you will reach it. In fact it is expected that for most cases you will end in the "big inner cycle"; if there is a fixed point at all, you will ultimately hit it only with probability $1/\sqrt{N}$ or so, i.e. pretty rarely.

In all generality, when starting from some input and hashing repeatedly, you always end up walking a cycle, and that never ends. A fixed point is a special case of a cycle with only one element. For a given function, one expects that there is a "big" cycle that you ultimately reach for most inputs, and a collection of much smaller cycles that you almost never reach.

Answer 2

I believe Thomas Pornin's answer is by far superior to mine, but perhaps this answer can provide a simplification to his answer.

When you initially hash some data, the possible input is infinite/limitless. You could input "abcdefghi...", "123456...", etcetera. However, the resulting hash possibilities are finite/limited.

One of the beautiful things about most hashing functions is that their output is always a fixed length. In the case of MD5, the output is always 128-bits. This is great for handling the output programmatically and storing the hash output in a file/database, but this means there is a finite limit on the number of possible outputs. For MD5, the limit is $2^{128}$ (which is 340,282,366,920,938,463,463,374,607,431,768,211,456). This might seem so high that it would never be reached, but we are dealing with theoretically hashing an infinite number of times.

Because there are only $2^{128}$ possible outputs for md5("Anything"), the input of all subsequent rounds is finite and most hash functions will produce a collision by 2^(<Number Bits in Output>/2). ($2^{64}$ for MD5.)

Consider this code:

String nextInput = "Some initial text here";
while(true){ // Infinite loop
    nextInput = md5(nextInput);
}

Because of collisions, we can expect that this will eventually enter a pattern where $round_{1}$, $round_{2}$, $round_{3}$, ... $round_{n}$ will result in $round_{n}$'s output being equal to $round_{1}$. So, the output will eventually enter a circle-like state where initialRoundOutput == currentRoundOutput and thus the circle/pattern/cycle will repeat infinitely.

As far as a fixed point where md5(md5(<some data>)) == md5(<some data>) == <some data>, I'll primarily leave that up to Thomas Pornin's answer to explain, but hash functions are designed so the input data is not the same as the output. However, it is theoretically possible that such an input exists. See this StackOverflow answer for a good explanation of that.