0
$\begingroup$

If one were to take a message, say "Hello world!", and compute the MD5 hash:

86fb269d190d2c85f6e0468ceca42a20

Then, taking the MD5 hash of this, and repeating that procedure:

d522231cf8bd5bd3bceb31c640bcab9a
64bb07c8a424dbb918495fa428702998
ed64b3e94672013dd88c415b8575dede
95119774bf93c232892b4f3071348abd
0d1fff8e1426591625a888451ed893c2
3e858eba431292825240db61628a817a
055609b11d0a06b46eff40bcb52eca09
8860c0fbffff97c16f1aa617e3b243e5
518ca0b27a1990b5bac51799c2c1b636
b62fd7e949b2995312b9fbddccd6b19f
b1d831a1d1c6ed8a81e4cb908f5aa36e
dd4e0883a48b1fd3a3a08e26cbc6adc4
3f4a12f0cdc506141badd00bf498dbad
be536872dde5b558975fd3a7dfec4884
402b32bb6839f17028deb13e60dd32ad
...

Given an infinite number of repetitions of the above, is it possible that all possible hashes will be computed an infinite number of times? Is it possible that given some initial message, there may be a revisiting of the initial hash just shortly after the start of the procedure, ie. if the MD5 of 402b32bb6839f17028deb13e60dd32ad was 86fb269d190d2c85f6e0468ceca42a20 again.

$\endgroup$
0
1
$\begingroup$

Given an infinite number of repetitions of the above, is it possible that all possible hashes will be computed an infinite number of times?

Yes, it is possible; however it is (to the best of our knowledge) extremely unlikely. Not only would MD5 (on 16 byte inputs) be a permutation, it would also need to be a single cycle permutation.

Is it possible that given some initial message, there may be a revisiting of the initial hash just shortly after the start of the procedure

That is also possible, but again, unlikely (just not as blindingly unlikely as the previous scenario); for a random function, the probability of this happening would be circa $2^{-64}$

The most likely scenario would be that we would fall into a loop that does not contain the initial hash.

All this can be shown if MD5 is assumed to act like a random function. Now, MD5 is not a random function, and it might have some unknown behavior that would change things. However, from what we know about MD5, that looks unlikely.

$\endgroup$

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