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.

up vote 35 down vote accepted

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.

  • 3
    For most secure hash functions with big enough output, you need a pretty big amount of times to get into a cycle. Not quite infinite (nothing is), but big enough for it not to be an issue in practice. – Maarten Bodewes Apr 25 '15 at 22:17
  • What's the expected difference in length between the longest cycle and the next smaller cycle / all smaller cycles or fixed points combined? – Random832 Apr 26 '15 at 11:41
  • note that MD5 will provide a collision after sqrt(2^128) because of the way it is designed – David 天宇 Wong Jun 3 '15 at 3:54
  • If I had a hash which inevitably ended up at one unique string for each message, how would I crack it? – Vedaad Shakib Nov 6 '15 at 21:24

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.

  • Your answer is good and simple too, I now understand why there will probably not be a fixed point. – AceLewis Apr 26 '15 at 0:05
  • Well good. I'm glad it could somewhat help haha Thomas Pornin definitely explains it better though ;) – Spencer Doak Apr 26 '15 at 0:50

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.