3 ms·

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

gojomo 17y ago
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) 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?
- madcaptenor 17y ago
  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.)
- silentOpen 17y ago
  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.
  - madcaptenor 17y ago
    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.
    - gojomo 17y ago
      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.
    - silentOpen 17y ago
      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.

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) 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?

madcaptenor 17y ago
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.)
silentOpen 17y ago
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.
- madcaptenor 17y ago
  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.
  - gojomo 17y ago
    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.
  - silentOpen 17y ago
    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.