I am looking for an easy to follow explanation, if possible, that demonstrates/proves the validity (or not!) of this assertion:
for any X, md5(X) != X (being X any string of 32 hex characters)
2
-
1$\begingroup$ It's very easy and very, very time consuming to prove it. Just create a hash of all possible MD5 values and compare with itself. $\endgroup$– ThoriumBROct 10, 2014 at 14:42
-
$\begingroup$ A note for people coming from a more general question: As MD5 is a relatively weak hash cryptographically speaking, the answer holds true even for stronger hashes like SHA-256. $\endgroup$– SEJPMApr 9, 2018 at 16:29
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
It is not known whether there is a fixed point or not. Since MD5 gives you 128 bits, you would need an input of 128 bits as well. That is you are really considering a function from the set of 128-bit strings to 128-bit strings. Assume that such a function is chosen at random. Then we can calculate the probability that the function has a fixed point. The answer is stated in this answer: https://stackoverflow.com/questions/235785/is-there-an-md5-fixed-point-where-md5x-x. To unpack just a bit more:
Say you have any of the $2^{128}$ possible inputs. Then the probability that this is a fixed point is $(1/2)^{128}$ since, for example, the first bit would have to map to the first bit and so on. So the probability that the input is not a fixed point is $1 - (1/2)^{128}$. So the probability that no input will be a fixed point is
$(1 - (1/2)^{128})^{(2^{128})}$
because there are $2^{128}$ possible input.
The probability that there is a fixed point is therefore $1 - (1 - (1/2)^{128})^{(2^{128})}$. If you calculate this probability you get approximately 63.21 %.
So it is actually likely that there is a fixed point for MD5 or any other hash function for that matter.
Note that this doesn't prove that there is a fixed point, but it just says something about the likelihood.
The only way to demonstrate/prove whether or not there is a fixed point would be to compute all hashes of all 128 bit strings and compare them to the output. But, as notes in the comments above, this is not very practical.
-
4$\begingroup$ One minor nit: the computation about a fixed point assumes a random function. MD5 isn't a random function, and might not behave as one (we don't know any specific way that it doesn't, at least, any way that appears relevant to the question), however that may be due more to our ignorance rather than the internals of MD5. However, it is an appropriate plausibility argument to say "there might be one, and there might not" $\endgroup$– ponchoOct 10, 2014 at 17:36
-
1$\begingroup$ For sufficiently large numbers (like 128) that probability approaches 1-(1/e). $\endgroup$ Jan 30, 2016 at 8:40