Существует ли Фиксированная точка MD5 где md5 (x) == x?

Так как сумма MD5 128 битов длиной, любая фиксированная точка должна была бы обязательно также быть 128 битов длиной. При предположении, что сумма MD5 любой строки равномерно распределена по всем возможным суммам, тогда вероятность, что любая данная 128-разрядная строка является фиксированной точкой, <глоток> 1 / _{2 <глоток> 128} .

Таким образом, вероятность, что никакая 128-разрядная строка не является фиксированной точкой, (1 в€’ <глоток> 1 / _{2 <глоток> 128} ) <глоток> 2 <глоток> 128 , таким образом, вероятность, что существует фиксированная точка, 1 в€’ (1 в€’ <глоток> 1 / _{2 <глоток> 128} ) <глоток> 2 <глоток> 128 .

Начиная с предела, поскольку n переходит к бесконечности (1 в€’ <глоток> 1 / _n) <глоток> n <глоток> 1 / _{, e}, и 2 <глоток> 128 является несомненно очень большим количеством, эта вероятность - почти точно 1 в€’ <глоток> 1 / _{% e} в‰ за 63,21€.

, Конечно, нет никакой случайности, на самом деле включил – или существует фиксированная точка или нет. Но, мы можем быть на 63,21% уверены, что существует фиксированная точка. (Кроме того, заметьте, что это число не зависит от размера ключевого пространства – если бы суммы MD5 составляли 32 бита или 1 024 бита, ответ был бы тем же, пока это больше, чем приблизительно 4 или 5 битов).

Так как хеш необратим, это было бы очень трудно выяснить. Единственный способ решить это, состоял бы в том, чтобы вычислить хеш на каждый возможный вывод хеша и видеть, придумали ли Вы соответствие.

Для разработки в хеше MD5 существует 16 байтов. Это означает, что существует 2^ (16*8) = 3.4 * 10 ^ 38 комбинаций. Если бы потребовалась 1 миллисекунда для вычисления хеша на 16-байтовом значении, потребовалось бы 10 790 283 070 806 014 188 970 529 154,99 года для вычисления всех тех хешей.

Вероятно, но нахождение его заняло бы больше времени, чем мы имеем или включили бы заключение компромисса MD5.

Существуют две интерпретации, и если одна из них разрешает выбирать любую, вероятность нахождения фиксированной точки возрастает до 81,5%.

• Интерпретация 1: выводит ли MD5 вывода MD5 в двоичный совпадает с его входом?
• Интерпретация 2: совпадает ли MD5 выхода MD5 в hex с его входом?

Строго говоря, поскольку входной сигнал MD5 имеет длину 512 бит, а выходной - 128 бит, я бы сказал, что это невозможно по определению.

While I don't have a yes/no answer, my guess is "yes" and furthermore that there are maybe 2^32 such fixed points (for the bit-string interpretation, not the character-string intepretation). I'm actively working on this because it seems like an awesome, concise puzzle that will require a lot of creativity (if you don't settle for brute force search right away).

My approach is the following: treat it as a math problem. We have 128 boolean variables, and 128 equations describing the outputs in terms of the inputs (which are supposed to match). By plugging in all of the constants from the tables in the algorithm and the padding bits, my hope is that the equations can be greatly simplified to yield an algorithm optimized to the 128-bit input case. These simplified equations can then be programmed in some nice language for efficient search, or treated abstractly again, assigning single bits at a time, watching out for contraditions. You only need to see a few bits of the output to know that it is not matching the input!