Hacker News Reader

Comment by gojomo | Hacker News Reader

Someone who highlights words and phrases in four different colors for various kinds of emphasis is lecturing the world about unnecessary signifiers?

View on HN

He's also looking for an MD5 fixed point. Something is madness but it's not URL syntax...

My intuition tells me there's a fair chance such a fixed-point exists, if MD5 behaves as a random oracle.

Specifically, there's a 1-in-2^128 chance that any 128-bit input will give itself as the output. Over 2^128 trials the chance that no input answers itself would be:

  (1-(2^-128))^(2^128)

...which mAlphaMatica helpfully calculates as...

http://www.wolframalpha.com/input/?i=(1-2^-128)^(2^128)

  0.367879441171442321595523770

That is, there's about a 63% chance Kember's quest to find an input whose MD5 output is itself will succeed.

Or, is there something in MD5's construction making this impossible, making the random-oracle model inapplicable?

The number you computed is nearly 1/e. Basically, (1-1/n)^n = exp(n log (1-1/n)) = exp(n (-1/n + 1/(2n^2) + O(1/n^3) )) = exp(-1 + 1/(2n) + O(1/n^2) ) = 1/e - 1/(2en) + O(1/n^2) and so your answer should agree with 1/e to, say, the first forty digits or so.

(Incidentally, Maple choked when I plugged in (1-2^-128)^(2^128), because it tried to evaluate it as a rational number, the numerator and denominator of which would have well over 2^128 digits.)

Very interesting. I had not worked out or seen the math for this. I don't doubt that such a number could exist. I do question the speed with which one could find the number and the utility once it's found.

How to find it: do MD5 on some random input. Then do MD5 on that output, and repeat until it converges. The problem is that you could end up in a cycle, instead of at a fixed point.

The speed with which it can be found: I'm going to wave my hands and claim this is in "Analytic Combinatorics" by Flajolet and Sedgewick. Seriously, though, under the assumptions we've been throwing around here this is a "random mapping" and these are reasonably well-studied objects.

No need to worry about cycles from using one output as the next input; just iterate over all possible 128-bit inputs, in any order. Unless you're trying to leverage some known deviation of MD5 from being a true random oracle, each input is just as likely as any other to be an identity input.

It would be interesting to try to map the group properties of MD5-space. Every 128-bit number would either be in a slide to a cycle or in a cycle (a fixed point is a cycle of size 1).

This still doesn't change the huge-normousness of the task, though.

Reply on news.ycombinator.com